4Legs_Archives

단어 찾기 사전에서 "Algorithm" 이란 단어를 찾는 상황을 가정해보자. 사전에서 단어를 찾는 방법은 여러 가지가 있을 것이다. ① 단순 탐색 : 사전의 처음부터 Algorithm이 나올 때까지 모든 단어를 확인 가장 확실하고 구현하기 쉬운 방법이지만, 찾고자 하는 단어가 사전의 어느 위치에 있냐에 따라 걸리는 시간이 천차만별일 것이다. 따라서 모든 경우에 대해 그다지 좋은 효율을 갖고 있다곤 할 수 없을 것이다. ② 이분 탐색 : 사전의 절반 지점의 단어를 확인 사전의 처음부터 끝까지 모든 단어들 중 딱 절반 지점의 단어를 확인한다. 이 절반 지점을 mid라 하자. 이 때 확인된 단어가 찾고자 하는 단어보다 사전 순으로 앞서면, 다음 탐색 범위는 mid부터 사전의 끝이 될 것이다. 또한 앞서지 않..

문제 링크 : www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제의 조건을 잘 살펴보자. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 제시된 조건들을 봤을 때 문제집의 문제 간에는 선행 관계가 존재함을 알 수 있으며, 따라서 이 문제는 사이클이 없는 방향 그래프 내에서 위상 정렬의 결과를 출력하는 문제임..

위상 정렬 (Topological Sort) 방탈출 게임을 한다고 생각해 보자. 우리는 메인 룸에 있는 3개의 자물쇠를 풀어야 탈출에 성공하고, 다음 단계의 탈출에 도전할 수 있다. 3개의 열쇠는 메인 룸과 연결된 3개의 방에 각각 하나씩 숨겨져 있다. 따라서, 메인 룸에서 나가기 위해서는 방 A, B, C 에서 열쇠를 모두 찾아야만 할 것이다. 단 열쇠를 찾는 순서는 영향을 주지 않는다. 또한 열쇠를 3개 모두 찾지 못하면, 다음 단계의 탈출에는 도전할 수 없을 것이다. 따라서 다음 단계의 탈출에 도전하기 위해서는 다음과 같은 순서를 따라야 한다. (A방에서 열쇠를 찾음 - B방에서 열쇠를 찾음 - C방에서 열쇠를 찾음) - 메인 룸의 자물쇠를 모두 푼다 - 메인 룸에서 탈출 후 다음 단계에 도전 (A..

문제 링크 : www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 2차원 배열 형태의 입력에서 목적지까지의 최대 가치를 구하는 문제이다. 문제에서 로봇은 위쪽으로 이동할 수 없다는 것에 주목하자. 로봇이 위쪽으로 이동할 수 없기 때문에, 어떤 한 행에 대한 최대 가치를 구하기 위해 그 이전 행의 최대 가치들을 미리 구해놓는다는 접근이 가능하다. 또한 로봇은 오른쪽, 왼쪽 양방향으로 이동 가능하며, 한번 지난 칸은 이동할 수 없다는 제약을 갖고 있다. 이..

문제 링크 : www.acmicpc.net/problem/20117 20117번: 호반우 상인의 이상한 품질 계산법 어떤 묶음에 있는 호반우의 품질이 [1, 2, 3, 4] 라고 하면 중간값인 3으로 모든 호반우의 품질을 계산한다. 따라서 이 묶음의 총 가격은 3 × 4 = 12 가 된다. 품질이 [6, 3, 9] 라고 하면 중간값인 6으로 www.acmicpc.net 그리디 알고리즘으로 해결할 수 있는 문제이다. 판매하는 물건들을 가장 비싸게 팔 수 있는 가장 좋은 방법은 가장 싼 물건과, 가장 비싼 물건을 묶어 파는 것이다. 문제에서 물건의 묶음이 짝수인 경우, 가격의 중앙값은 (묶음 개수/2+1)번째 호반우로 정의했기 때문에 (k1, k2) 묶음에 대해서 반드시 k2의 가격이 중앙값이 된다. 따라서..

문제 링크 : www.acmicpc.net/problem/20116 20116번: 상자의 균형 3번 박스의 중심의 x좌표는 9이며 2번 박스의 구간 (0, 20) 에 속한다. 그리고 2, 3번 박스의 중심의 x좌표는 (10+9)/2 = 9.5 이고 1번 박스의 구간 (-10, 10) 에 속하므로 균형을 이룬다. www.acmicpc.net 누적합 등으로 쌓여 있는 상자들의 평균 중심을 구해가며 안정적인 구조인지 판단하면 된다. 이 풀이에서는 맨 위 상자부터 계산하였다. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46..

문제 링크 : www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 문제에서 제시된, "세금이 인상될 때 최단거리가 갱신되는 경우"란 무엇일까? 세금이 인상되지 않았을 때 최단거리를 이미 알고 있다는 가정에서 생각해보자. ① 세금이 인상될 때, 어떤 한 경로에 대해 비용의 상승은 무엇에 의해 결정될까? 이는 해당 경로에 포함된 간선의 개수와 관련된다. 즉, 세금이 k원 인상될 때, 간선을 m..

문제 링크 : www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 책을 최대한 많이 나눠주기 위해선 어떻게 해야 할까? 우선 책 번호의 범위가 좁은 사람에게 먼저 책을 나눠주는 것이 유리할 것이다. 범위가 넓은 사람에게 더 많은 선택지가 있기 때문이다. 또한, 동일한 크기의 여러 구간들이 겹쳐 있는 경우에는 최대한 겹치는 구간의 수가 적은 책을 먼저 나눠주어야 더 많은 사람에게 책을 나눠줄 수 있을 것이다. 겹치는 구간을 최대한 피하기 위한 방법은 다음과 같은 두 ..

문제 링크 : www.acmicpc.net/problem/20115 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net 그리디 알고리즘으로 해결할 수 있는 문제이다. 최종적으로 만든 드링크의 양이 최대가 되기 위해서는, 두 드링크를 섞을 때 버려지는 양이 최소가 되어야 한다. 그러기 위해서는 두 드링크를 섞을 때, 원래 양이 더 적은 드링크를 절반 버리는 것이 이득이다. 따라서, 드링크의 목록 중 가장 양이 많은 드링크가 기준이 되어, 다른 모든 드링크를 절반씩 섞은 양이 최종 드링크의 최대 양이 된다. [코드] ..

문제 링크 : www.acmicpc.net/problem/20114 20114번: 미아 노트 첫째 줄에 원래 문자열의 길이 N, 세로로 번진 글자의 개수 H, 가로로 번진 글자의 개수 W가 주어진다. (1 ≤ N ≤ 100, 1 ≤ H ≤ 10, 1 ≤ W ≤ 10) 둘째 줄부터 H개의 줄에 걸쳐 N × W 길이의 문자열이 www.acmicpc.net 각 문자열이 번진 형태는 위 그림과 같다. 번진 전체 문자열 중 한 문자당 그 문자가 나타나는 구역이 있음을 캐치하고, 그 구역 내에서 문자를 찾을 수 있다면 그 문자를, 찾을 수 없다면 ?을 출력하도록 한다. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29..