알고리즘
백준 11000번 : 강의실 배정
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 다른 비슷한 문제와 헷갈려서 조금 해맸던 문제이다. 시작시간과 종료시간이 있는 N개의 강의가 입력으로 주어지고, 강의마다 강의실을 배정하려고 한다. 한 강의가 끝나자마자 다른 강의를 시작할 수 있지만, 강의 시간이 겹친다면 그 강의실은 현재 진행중인 강의가 끝날때까지 사용할 수 없다. 강의실을 최소한으로 사용했을때 강의실 개수를 구하는 문제다. 얼핏봤을때 회의실 배정 문제와 비슷해서 N개의 강의를 종료시간 기준으로 오름차순 정렬하고 풀었더니 오..
백준 2141번 : 우체국
https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 접근하기 굉장히 까다로웠던 문제. 풀이를 보고나서 이해했다. 일직선 상의 1차원 좌표에 N개의 마을이 있고 각 마을의 위치와 주민의 수가 입력으로 주어진다. 여기에 우체국을 세우려고 하는데, 각 마을에 살고있는 주민들이 우체국을 가기위해 이동해야 하는 거리의 총합이 최소인 위치에 세우려고 한다. 이때 우체국의 위치를..
백준 2250번 : 트리의 높이와 너비
https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 구현이 까다로웠던 그래프 탐색 문제이다. 문제를 요약하자면 트리의 노드들을 2차원 좌표공간에 매칭시키는 문제다. 루트 노드부터 시작해서 자식으로 내려갈때(레벨이 증가할 때) 마다 x좌표(행)가 증가하,고 부모의 왼쪽 자식은 부모보다 y좌표(열)가 작으며 오른쪽 자식은 더 크다. 하나의 열에는 오직 한 개의 노드만 들어갈 수 있고 트리의 가장 왼쪽에있는 노드와 가장 오른쪽에있는 노..
백준 1774번 : 우주신과의 교감
https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 처음 풀어본 최소신장트리(MST) 문제이다. 문제를 요약하자면 N개의 점에 대한 2차원 좌표가 주어지고, 두 점을 잇는데 두 점 사이의 거리만큼 비용이 발생할 때 비용을 최소로 하면서 N개의 점을 모두 연결된 상태(특정한 점에서 다른 점까지 도달할 수 있음)로 만드려고 한다. 그런데 이때 처음부터 이미 이어져있는 점이 있을 수도 있다. 이때 필요한 최소 비용을 구하는 문..
백준 2655번 : 가장높은탑
https://www.acmicpc.net/problem/2655 2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차 www.acmicpc.net 아이디어가 어렵진 않아서 풀 순 있었지만 재귀로 구현하는데 시간이 오래 걸렸던 문제다. N개의 벽돌은 각각 높이와 서로 다른 넓이의 정사각형 밑면을 갖고 있고 무게도 모두 다르다. 이 벽돌들을 차례차례 쌓아올려서 가장 높은 탑을 만드려고 한다. 벽돌을 쌓기 위해서는 밑에 있는 블록보다 위에 있는 블록의 무게가 가벼워야하고, 밑면의 넓이도 작아야한다. 탑을 가장 높게 쌓아올렸을때 사용한 벽돌의 ..
백준 9251번 : LCS
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 접근 방법을 생각하지 못해 해답을 보고 푼 문제이다. 주어진 두 문자열의 부분 수열 중, 공통으로 들어있는 가장 긴 부분 수열의 길이를 구하는 문제다. 처음 떠오른 생각은 두 문자열의 부분 수열을 모두 구하고 비교하려고 했다. 문자열의 길이가 최대 1000이기 때문에 당연히 불가능하지만 이 방법밖에 머릿속에 떠오르지 않았다. 다이내믹 프로그래밍의 메모이..
백준 12865번 : 평범한 배낭
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 다이나믹 프로그래밍의 기본 유형이라고 할 수 있는 문제이지만, 2차원 리스트를 이용한 메모이제이션을 생각하는 과정과 사소한 실수로 푸는데 시간이 많이 소요됐다. 문제를 요약하면 N개의 물건은 각각 무게와 가치를 갖고 있는데, 주어진 배낭의 용량(K)을 넘지 않게 물건을 넣어서 배낭 안에 들어있는 물건들의 가치의 합을 최대로 만드는 ..
백준 1766번 : 문제집
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상 정렬의 개념을 알고, 이 문제에 적용할 수 있으면 쉽게 풀 수 있는 문제였다. 총 N개의 문제가 있고 문제는 1번부터 N번까지 난이도를 기준으로 오름차순 정렬돼있다. N개의 모든 문제를 풀되, 가장 쉬운 문제(번호가 낮은 문제)부터 풀어야 하지만 어떤 문제는 그 문제보다 선행되어 풀어야 하는 문제가 존재한다. 즉 선행 문제를 풀기 전엔 해당 문제를 풀 수 없다...
백준 4195번 : 친구 네트워크
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 처음 접해본 Union-Find 문제였다. 문제를 간단히 요악하면 두 사람의 이름이 입력으로 주어질 때 각 사람이 가진 친구들을 합한 수를 출력하는 문제이다. 예를 들어 A와 B가 입력으로 주어지면 그때부터 A와 B는 친구 관계를 맺게되고, A와 B가 친구가 되는 순간 A의 친구는 B의 친구가 되고, B의 친구는 A의 친구가 된다. 그 상태에서 A와 B가 가진 친구들의 수를 구해야 하는..
백준 1991번 : 트리 순회
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이진 트리에서 전위, 중위, 후위순회를 코드로 구현하는 문제이다. 각 순회는 자식을 가진 특정 노드에서, 부모 노드가 방문되는 순서에 따른 분류이다. 전위 순회 : 부모 노드를 가장 먼저 방문하고 왼쪽 자식, 오른쪽 자식 순서대로 방문한다. (parent → left → right) 중위 순회 : 왼쪽 자식을 먼저 방문하고 부모 노드, 오른쪽 자식 순서대로 방문한다. (left → pa..