본문 바로가기

알고리즘 문제 풀이89

[백준 2776] 암기왕 문제 출처 : https://www.acmicpc.net/problem/2776 수첩 1에 있는 정수가 수첩 2에 있으면 1을, 없으면 0을 출력하는 문제 입니다.문제 이해하기수첩 1의 순서가 중요한 것이 아니기 때문에 수첩 1을 정렬한 다음, 수첩 2의 숫자로 이분탐색을 하여 결과를 출력하면 됩니다.이 방법보다 더 쉬운 방법은 수첩 1을 set 자료구조로 저장하여 찾는 것입니다. 간단한 문제이기 때문에 이분 탐색, set 두 가지 방법 모두 해보겠습니다.코드작성이분 탐색의 입력부터 알아보겠습니다.입력 받기mii = lambda : map(int, input().split())T = int(input())for _ in range(T): N = int(input()) arr = list(mii.. 2024. 5. 3.

[백준 2295] 세 수의 합 문제 출처 : https://www.acmicpc.net/problem/2295 집합에 포함된 세 수를 더한 결과가 집합 내에 있는 가장 큰 수가 되는 경우를 찾는 문제 입니다. 세 수 x, y, z와 그 결과로 가장 큰 수 k를 찾아야 합니다. 이 때 꼭 기억해야 하는 부분은 x, y, z, k의 값이 서로 같아도 된다는 부분 입니다. 저는 세 수가 같을수는 없다고 생각하고 아무리 풀어도 틀리다고 나와 문제를 다시 제대로 읽어보니 숫자가 중복되어도 상관 없다는 부분을 찾을 수 있었습니다. 저와 같은 실수를 하지 마시기 바랍니다.아이디어세 개의 수를 더하기 때문에 시간복잡도가 높을 것으로 생각이 듭니다. 하지만 조금만 더 생각해보면 시간복잡도를 줄일 수 있는 아이디어가 있습니다. 우리가 구해야 하는 공식.. 2024. 5. 2.

[백준 2512] 예산 문제 출처 : https://www.acmicpc.net/problem/2512 렌선 자르기 문제와 비슷한 느낌이 드는 문제 입니다. 다빈치코딩 알고리즘에 넣기에는 중복적인 내용이라 블로그에 추가하였습니다.문제 이해하기예산이 낮은곳은 그대로 두고, 예산이 높은곳만 줄여나가며 총액보다 작게 만드는 문제 입니다.이 문제는 일반적인 이분 탐색 문제와 다른점이 있습니다. 바로 예산을 증액할 필요는 없다는 것입니다. 예산의 총액이 신청한 예산보다 크다면 더이상 예산을 늘릴 필요 없이 최대값을 출력하면 됩니다. 이 부분만 주의하면 문제를 해결할 수 있습니다.코드 작성그럼 코드를 작성하며 문제를 해결해 보겠습니다.입력 받기N = int(input())arr = list(map(int, input().split())).. 2024. 5. 1.

[백준 18185] 라면 사기 (Small) 문제 출처 : https://www.acmicpc.net/problem/18185문제 이해하기라면을 최대한 싸게 사면 되는 문제 입니다. 1개를 살 때에는 3원, 2개를 살 때에는 5원, 3개를 살 때에는 7원을 주고 사야 합니다. 최대한 많이 사는 것이 이득이기 때문에 그리디로 문제를 해결할 수 있습니다.하지만 그리디 문제는 반례를 찾기가 힘듭니다. 반례를 잘 찾아 문제를 해결해야 합니다. 반례는 3개를 살펴볼 때 나오는 것이 아니라 4개 이상일 때 발생 합니다. 라면이 위와 같이 있다고 하겠습니다. 그리디 알고리즘으로 한꺼번에 많이 사는것이 이득이기 때문에 처음에 3개를 사보겠습니다.3개를 한꺼번에 샀기 때문에 3 * 7 로 21의 돈이 들었습니다. 그리고 2번째 2개, 4번째 3개가 남았습니다. 각.. 2024. 4. 29.

[백준 13023] ABCDE 문제출처 : https://www.acmicpc.net/problem/13023 A → B → C → D → E 의 관계가 성립하는 그래프가 있는지 확인하는 문제 입니다.깊이 우선 탐색을 이용하여 4단계까지 깊이가 생성된다면 1을 출력하고, 생성되지 않는다면 0을 출력하면 됩니다.문제 이해하기아래와 같은 친구 관계가 있습니다.1번에서부터 친구 관계를 찾아보면 4단계의 깊이를 내려갈 수 없습니다. 2번에서 시작해도 마찬가지로 4단계의 깊이로 내려갈 수 없습니다. 4번이나 5번에서 시작해야만 4단계의 깊이로 내려갈 수 있습니다. 따라서 이 문제는 모든 친구를 A로 가정하고 다 확인해봐야 합니다.코드작성함정이 없고, 이해하기 쉽기 때문에 바로 코드를 작성하겠습니다.입력 받기mii = lambda : map(i.. 2024. 4. 27.

[백준 1328] 고층 빌딩 문제 출처 : https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 문제 이해하기 빌딩을 왼쪽에서 보았을 때, 오른쪽에서 보았을 때를 가지고 빌딩의 순서를 출력하는 문제 입니다. 어려운 문제이지만 차근차근 생각하면 해결할 수 있습니다. 이 문제를 풀 때에는 모든 빌딩이 바닥에서부터 쏟아오른다고 생각하면 좀 더 쉽습니다. 문제의 예로 나온 N = 5, L = 3, R = 2를 생각해 보겠습니다. 총 5개의 건물이 있고 왼쪽에서는 3개의 빌딩이 보이고,.. 2024. 4. 1.

[백준 30090] 백신 개발 문제 출처 : https://www.acmicpc.net/problem/30090 30090번: 백신 개발 평소 정보 보안에 관심이 많은 진흥이는 최근 들어 유행하고 있는 컴퓨터 바이러스에 대한 백신을 개발하려고 한다. 바이러스는 $N$개의 문자열로 이루어져 있다고 한다. 진흥이가 열심히 연구 www.acmicpc.net 이 문제는 제 1회 청소년 IT 경시대회 초등부 B번, 고등부 A번 문제 입니다. 겹치는 문자열을 이어 붙여 가장 짧은 문자열을 만드는 문제 입니다. 예제를 확인해보면 3개의 입력이 주어집니다. RUST, VIRUS, STAND 입니다. 이 3개의 문자를 겹치는 부분을 하나로 만들어 잘 이어주면 VIRUSTAND 라는 문자열이 가장 짧은 문자열이 되고 이 문자열의 길이인 9를 출력하는 .. 2024. 3. 13.

[백준 30089] 새로운 문자열 만들기 문제 출처 : https://www.acmicpc.net/problem/30089 30089번: 새로운 문자열 만들기 $T$개의 줄마다 영어 대문자로만 이루어진 문자열 $S$가 주어질 때, 각 줄마다 아래 조건을 모두 만족하는 문자열 $X$를 출력하여라. $X$는 $S$로 시작하여야 한다. $X$를 뒤에서부터 읽은 문자열 $X'$ www.acmicpc.net 이 문제는 제 1회 청소년 IT 경시대회 초등부 A번, 중등부 A번으로 출제되었습니다. 문자열 S가 주어졌을 때 뒤집어도 문자열 S가 나오는 가장 짧은 문자열 X를 출력하는 문제 입니다. 테스트 케이스가 100개 이하이고, 문자열 길이가 20 이하이기 때문에 시간 복잡도에 구애받지 않고 어렵게 생각하지 않고 풀어도 됩니다. 문제 이해하기 이렇게 앞으.. 2024. 3. 12.

[백준 17619]2019 정올 2차 중등부 "개구리 점프" 문제 출처 : https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 이 문제는 2019년 정보올림피아드 2차 대회 중등부 2번 문제 입니다. 문제 이해하기 이 문제는 점프를 얼마나 해서 이동할 수 있는지 묻는 문제가 아닙니다. 오직 이동이 가능한지, 불가능한지 묻는 문제 입니다. 즉 높이는 아무 상관 없이 길이가 겹쳐지는지를 따져서 연결 여부만 알 수 있으면 됩니다. 문제에서는 이렇게 길이와 높이가 나와 있.. 2024. 3. 7.

[백준 17615] 2019 정올 2차 초등부 "볼 모으기" 문제 출처 : https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 이 문제는 2019년 정보 올림피아드 2차 대회 초등부 2번 문제 입니다. 알고리즘 이해하기 문제에는 제약 조건이 많기 때문에 잘 읽어봐야 합니다. 한가지 색깔만 옮길 수 있습니다. 처음에 빨간색을 옮기면 계속 빨간색만 옮겨야 합니다. 하나씩 옮기되, 최대한 멀리 옮겨야 최소 값을 얻을 수 있습니다. 이 두가지를 생각하면서 시뮬레이션 해보면 결국 우리가 .. 2024. 3. 6.

[백준 17618] 2019 정올 2차 중등부 "신기한 수" 문제 출처 : https://www.acmicpc.net/problem/17618 17618번: 신기한 수 평소에 수에 대한 관심이 많은 아이인 민철이는 오늘도 노트에 연필로 수를 더하거나 빼거나 곱하거나 나눠보면서 시간을 보내고 있다. 그러다가 18이라는 수는 신기한 성질을 가진다는 것을 알 www.acmicpc.net 이 문제는 2019년 정보올림피아드 2차 대회 중등부 1번 문제 입니다. 문제 난이도가 높지 않아 다빈치코딩 알고리즘에도 똑같이 작성해 놓았습니다. https://wikidocs.net/232738 02. 신기한 수(정올 2019)[백준 17618] 문제 출처 : [신기한 수](https://www.acmicpc.net/problem/17618) 이 문제는 2019년 정보올림피아드 2차.. 2024. 3. 5.

[백준 19940] 2020 정올 1차 초등부 "피자 오븐"(2) 문제 출처 : https://www.acmicpc.net/problem/19940 19940번: 피자 오븐 각각의 테스트 케이스마다 5개의 정수를 한 줄에 공백으로 구분해서 출력한다. 이 정수는 입력으로 주어진 시간을 만들기 위해서 ADDH, ADDT, MINT, ADDO, MINO 버튼을 누르는 횟수를 출력한 것이다. 최 www.acmicpc.net 피자 오븐 문제를 수학적으로 푸는 방법을 이전 포스팅을 통해 알아보았습니다. https://davincicoding.tistory.com/103 [백준 19940] 2020 정올 1차 초등부 "피자 오븐"(1) 문제 출처 : https://www.acmicpc.net/problem/19940 19940번: 피자 오븐 각각의 테스트 케이스마다 5개의 정수를 .. 2024. 3. 4.

[백준 19940] 2020 정올 1차 초등부 "피자 오븐"(1) 문제 출처 : https://www.acmicpc.net/problem/19940 19940번: 피자 오븐 각각의 테스트 케이스마다 5개의 정수를 한 줄에 공백으로 구분해서 출력한다. 이 정수는 입력으로 주어진 시간을 만들기 위해서 ADDH, ADDT, MINT, ADDO, MINO 버튼을 누르는 횟수를 출력한 것이다. 최 www.acmicpc.net 이 문제는 2020년 정보 올림피아드 초등부 2번 문제 입니다. 문제 이해하기 버튼을 어떻게 누르는 것이 더 적은 횟수로 누를 수 있는지 찾는 문제 입니다. 이런 문제는 직접 계산을 하던가, 알고리즘을 통해 최소 버튼 횟수를 찾는 방법이 있습니다. BFS를 사용하면 버튼의 최소 횟수를 찾을 수 있지만 여기서는 직접 계산하는 방법을 생각해 보겠습니다. 6분 .. 2024. 3. 3.

[백준 19942] 2020 정올 1차 중등부 "다이어트" 문제 출처 : https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 이 문제는 2020년 정보올림피아드 1차 중등부 2번 문제 입니다. 문제 이해하기 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 넘어서는 최소 가격을 찾으면 되는 문제 입니다. N의 크기가 15로 비교적 작기 때문에 브루트 포스나 백트래킹으로 쉽게 결과를 찾을 수 있습니다. 백트래킹을 통해 문제를 해결해 보겠습니다. 백트래킹에 대해 잘 모른다면 아래 링크를 통해 백트래킹 기법.. 2024. 3. 3.

[백준 17611] 2019 정올 1차 중등부 2번 "직각다각형" 문제 출처 : https://www.acmicpc.net/problem/17611 17611번: 직각다각형 입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 n(4 ≤ n ≤ 100,000)이 주어지고, 이어지는 n개 줄 각각에 단순직각다각형 꼭지점의 좌표 (xi, yi)가 차례대로 주어진다. 주어지 www.acmicpc.net 이 문제는 2019년 정보올림피아드 1차 대회 중등부 2번 문제 입니다. 문제 이해하기 수평, 수직을 체크하며 가장 겹치는 부분이 많은 곳을 찾는 문제 입니다. 예제 2번을 보며 같이 생각해 보겠습니다. 예제 2번의 좌표를 찾아 표시하면 다음과 같습니다. 가장 겹치는 점이 많은 것은 수평 선분일 때 6개이고, 수직 선분은 2개 입니다. 따라서 출력값은 max(6, .. 2024. 3. 1.

[백준 17613] 2019 정올 1차 고등부 "점프" 문제 출처 : https://www.acmicpc.net/problem/17613 17613번: 점프 T개의 줄에 각각 하나의 정수를 출력한다. 각 줄에 출력되는 정수는 구간 [x, y]안의 수들의 점프넘버들 중 최댓값이다. 각 정수는 입력으로 주어지는 구간의 순서에 맞게 출력되어야 한다. 즉, 첫 www.acmicpc.net 이 문제는 2019년 정보올림피아드 1차 고등부 2번 문제 입니다. 점프를 하면서 해당 위치에 갈 수 있는 가장 짧은 점프 횟수를 찾는 문제 입니다. 여기 까지는 쉽지만 범위 안에 있는 모든 짧은 점프 횟수를 찾아 그중 가장 큰 수를 출력해야 합니다. 문제 이해하기 예제 입력에 있는 3번째 경우를 보겠습니다. 12부터 16사이에 가장 큰 점프 횟수를 찾아야 합니다. 먼저 12에 도.. 2024. 2. 29.

[백준 17610] 2019 정올 1차 중등부 "양팔저울" 문제 출처 : https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 이 문제는 2019년 정보 올림피아드 1차 중등부 1번 문제 입니다. 양팔 저울을 가지고 만들 수 있는 모든 무게를 찾아 불가능한 경우의 수를 출력하는 문제 입니다. 따라서 1부터 모든 추의 무게를 따져가며 만들 수 있는지, 없는지 확인해야 합니다. 이런 문제는 DP를 통해 풀 수 있습니다. DP의 배낭 문제를 통해 이 문제의 해결 방안을 생각해 볼 수 있습니다. 경우의 수를 따져.. 2024. 2. 23.

[백준 17612] 2019 정올 1차 고등부 "쇼핑몰" 문제 출처 : https://www.acmicpc.net/problem/17612 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net 이 문제는 2019년 정보 올림피아드 1차 고등부 1번 문제 입니다. 문제 이해하기 이 문제는 어렵지는 않지만 복잡한 문제 입니다. 쇼핑몰에 들어가는 순서 따로, 그 고객의 id를 알아야 하고 고객이 사는 물건의 개수만큼 시간을 계산하여 계산대에 넣어주어야 합니다. 예제 입력을 가지고 생각해 보겠습니다. 예제에는 10명의 고객이 있고 계산대는 총 3개.. 2024. 2. 22.

[백준 17609] 2019 정올 초등부 1차 "회문" 문제 출처 : https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 이 문제는 2019년 정보 올림피아드 1차 초등부 2번 문제였습니다. 회문이란? 회문 또는 팰린드롬이라 불리는 문자열은 드라마 이상한 변호사 우영우를 생각하면 됩니다. 기러기, 토마토, 스위스, 인도인, 별똥별… 이런 단어들처럼 똑바로 읽어도 거꾸로 읽어도 같은 문자열을 회문 이라고 합니다. 유사 회문? 이 문제는 회문을 한 단계 넘어 유사회문이라는 것을 찾아야 합니다. 유사회문은 문자열에서 한 문자를 삭제해서 .. 2024. 2. 20.

[백준 28323] 2023 정올 2차 초등부 "불안정한 수열" 문제 출처 : https://www.acmicpc.net/problem/28323 28323번: 불안정한 수열 $N$개의 자연수가 좌우 일렬로 놓여 있다. 왼쪽에서 $i$ ($1 \le i \le N$)번째에 놓여 있는 자연수는 $A_i$다. 여러분은 이 중 몇 개의 자연수를 원하는 만큼 고를 수 있다. 단, 아무 자연수도 고르지 않 www.acmicpc.net 이 문제는 2023년 정보올림피아드 초등부 2차 1번 문제 였습니다. 수열 A에서 이웃한 자연수의 합을 구했을 때 항상 홀수인 수열 B를 구하는 문제 입니다. 문제를 어떻게 풀어야 할지 감이 잘 잡히지 않는다면 조합을 구하고 그 중 답이 있는지 확인하면 됩니다. 그럼 100점은 맞지 못하더라도 부분 점수를 얻을 수 있습니다. 정보 올림피아드는 시.. 2024. 2. 19.

[백준 28324] 2023 정올 초중고 2차 스케이트 연습 문제 출처 : https://www.acmicpc.net/problem/28324 28324번: 스케이트 연습 여러분은 주어진 스케이트 코스에서 스케이트를 연습하려고 한다. 이 코스는 시작 지점, $N$개의 중간 지점, 그리고 도착 지점으로 구성되어 있다. 이 연습은 시작 지점에서 $0$의 속력으로 출발 www.acmicpc.net 이 문제는 2023년 정보올림피아드 2차 대회 초등부 2번, 중등부 1번, 고등부 1번으로 출제된 문제 입니다. 문제를 읽어보면 왠지 DP의 냄새가 나는 문제 입니다. 하지만 잘 생각해보면 굳이 DP를 사용하지 않고도 문제를 해결할 수 있습니다. 그리디로 탐욕적으로 문제를 해결해 보겠습니다. 문제 이해하기 이 문제를 해결하기 위해서 알아야 하는 것은 크게 두가지 입니다. 속력.. 2024. 2. 13.

[백준 28216] 2023 정올 초등부 1차 아이템 획득 문제 출처 : https://www.acmicpc.net/problem/28216 28216번: 아이템 획득 $N ≤ 2\,000$, $Q ≤ 2\,000$, $x_i ≤ 1\,000$, $y_i ≤ 1\,000$, $w_i ≤ 10$, 매 순간 자동차의 $x$, $y$좌표는 $1\,000$ 이하이다. www.acmicpc.net 이 문제는 2023년도 정보 올림피아드 1차 초등부 3번 문제로 출제 되었던 문제 입니다. 문제 이해하기 2차원 지도에서 아이템을 모으는 문제로 인접 행렬로 구현하면 될 것 같은 문제 입니다. 하지만 지도의 크기가 20만 입니다. 또한 이동하는 횟수인 Q 역시 20만 입니다. 쉽게 시간복잡도가 20만 * 20만이라는 것을 알 수 있고 시간초과가 예상되기 때문에 인접 행렬로 문제.. 2024. 1. 30.

[백준 28218] 2023 정올 중등부 1차 격자 게임 문제 출처 : https://www.acmicpc.net/problem/28218 28218번: 격자 게임 첫 번째 줄에 세 정수 $N$, $M$, $K$가 공백을 사이에 두고 주어진다. 이후 $N$개의 줄에 걸쳐 #과 .으로만 구성된 길이 $M$의 문자열이 한 줄에 하나씩 주어진다. $1 ≤ i ≤ N$ 과 $1 ≤ j ≤ M$에 대해, $i$ www.acmicpc.net 이 문제는 2023 정보올림피아드 중등부 1차 2번 문제로 출제 되었습니다. 말의 위치가 정해지면 아래로 한칸 가던가, 오른쪽으로 한칸 가던가, K만큼 대각선으로 움직일 수 있습니다. 두 명이 번갈아 이동해 마지막 칸에 누가 먼저 이동하는지를 대결하는 게임 입니다. 게임 이해하기 두 명 모두 최선을 다하기 때문에 매 번 승리할 수 있.. 2024. 1. 28.

[백준 13418] 학교 탐방하기 문제 출처 : https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 이 문제는 최소 신장 트리를 두 번 구성해야 하는 문제 입니다. 최소 신장 트리에 대해 잘 모른다면 아래 링크를 통해 최소 신장 트리에 대해 이해하시기 바랍니다. https://wikidocs.net/207011 05. 최소 신장 트리 MST(Minimum Spanning Tree) 라고 불리는 최소 신장 트리를 이해하기 위해서는 먼저 신장 트리(.. 2024. 1. 27.

[백준 28217] 2023 정올 1차 두 정삼각형 문제 출처 : https://www.acmicpc.net/problem/28217 28217번: 두 정삼각형 첫 번째 줄에는 $1$개의 수를, 두 번째 줄에는 $2$개의 수를, $\dots$, $N$번째 줄에는 $N$개의 수를 아래 그림과 같이 배치한 정삼각형 $A$, $B$가 주어진다. 각 위치에 있는 수는 $0$ 또는 $1$이다. 당신은 www.acmicpc.net 이 문제는 2023년 정보 올림피아드 중등부 1차 1번 문제로 출제된 두 정삼각형이라는 문제 입니다. 정 삼각형을 회전시키거나, 대칭으로 만들어 값을 비교하는 문제 입니다. N의 크기도 크지 않아 특별한 알고리즘을 사용하지 않아도 문제가 해결될 것 같습니다. 다만 회전시키거나 대칭을 만드는 것이 쉽지 않아 보입니다. 이런 문제를 해결하기 .. 2024. 1. 25.

[백준 11779] 최소 비용 구하기 2 문제 출처 : https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 확인 이 문제는 제목에서 알 수 있듯이 최소 비용 구하기 문제와 거의 비슷합니다. 다른점 이라면 이동한 경로를 표시해야 한다는 점입니다. 이동하는 경로를 어떻게 표시 하는지에 어려워 하는 친구들이 있어 그 부분에 대해 알려주기 위해 글을 남깁니다. 다익스트라 알고리즘으로 이 문제를 해결하기 위한다면 최소 비용 구하기부터 확인 하시기 바랍니다. 0.. 2024. 1. 23.

[백준 10844] 쉬운 계단 수 문제 출처 : 쉬운 계단 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 숫자가 계단수인지 아닌지 확인하며 개수를 센다면 시간초과가 발생할 수밖에 없습니다. 이런 문제를 만나면 직접 경우의 수를 따져보며 문제를 어떻게 풀어야 할지 고민하는게 좋습니다. 예제 입력 확인해보기 예제 입력을 보면 1을 입력 하였을 때 9가 출력 됩니다. 0으로 시작하는 수는 계단수가 아니기 때문에 1부터 9까지의 숫자 아무거나 계단수가 됩니다. 따라서 9가 되는 것입니다. 다음으로 2를 입력하면 17이 됩니다. 왜 17이 되는지 따라가보면 앞서 1을 입력한 숫자들이 계단수가 되기 위해 어떻게 바뀌는지 생각하면 알 수 있습니다. 1은 10이나 1.. 2024. 1. 22.

[백준 13308] 2016 정올 고등부 "주유소" 문제 출처 : 주유소 2023년도 정보올림피아드에도 주유소란 이름의 문제가 있어 혼란스러울 수 있으나 두 문제는 다른 문제 입니다. 2023년도 주유소 문제는 아래 링크에서 확인 가능 합니다. https://davincicoding.tistory.com/9 [백준 28219] 2023 정올 1차 주유소 문제 출처 : https://www.acmicpc.net/problem/28219 28219번: 주유소 KOI 국가는 $N$개의 마을로 이루어져 있다. 각 마을에는 $1$번 마을, $2$번 마을, $\cdots$, $N$번 마을과 같이 번호가 붙어 있다. 그리고 도로가 $ davincicoding.co.kr 2016년도 주유소 문제는 다익스트라 알고리즘으로 해결할 수 있는 문제 입니다. 다만 문제가 기름을.. 2024. 1. 21.

[백준 1219] 오민식의 고민 문제 출처 : https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 관련 문제 확인 이 문제는 골목길 문제의 확장판이라고 할 수 있습니다. 골목길에 대한 해설은 아래 링크를 타고 들어가면 확인해 볼 수 있습니다. https://wikidocs.net/225235 03. 골목길[백준 1738] 문제 출처 : [골목길](https://www.acmicpc.net/problem/1738) 민승이가 지나가는 길에 깡패가 있거나 금품이 떨어져 있습니다. 깡.. 2024. 1. 1.

[백준 1865] 웜홀 - 플로이드 워셜 풀이 문제 출처 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 이 문제는 벨만 포드로 풀어야 하는 문제 입니다. 벨만 포드 풀이법은 다빈치코딩 알고리즘 책에 작성 하였습니다. https://wikidocs.net/225180 02. 웜홀[백준 1865] 문제 출처 : https://www.acmicpc.net/problem/1865 이 문제를 잘 살펴보면 최단 경로를 구하는 문제가 아닙니다. 단지 음의 사이클이 있는지 없는지를… w.. 2023. 12. 17.

이전 1 2 3 다음

티스토리툴바