Algorithm

[백준 1854] K번째 최단경로 찾기 (C++)

1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 다익스트라 알고리즘을 큰 변형없이 그냥 사용하면 되는 문제이다. 다익스트라 알고리즘에서는 현재까지 구한 시간보다 다음 정점까지 가는데 걸리는 시간이 더 긴 경우에만 다음 정점을 탐색하고, 걸리는 시간을 갱신한다. 따라서 이 조건을 빼는 경우에는 N 정점에 도달하는 경우는 무수히 많아지게 될 것이다. 다익스트라에서는 다음 정점으로 가는 시간이 가장 적은 간선부터 탐색하기 때문에 이를 응용하면, 특정 정점에 ..

[백준 14595] 동방 프로젝트(Large) (C++)

14595번: 동방 프로젝트 (Large) 첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다. www.acmicpc.net x ~ y 사이의 모든 방은 통합해서 하나의 방으로 만든다. 통합하는 순서는 결과에 영향을 주지 않기 때문에 x가 작은 순으로 오름차순 정렬한다. 현재 통합한 y 좌표의 최댓값보다 새로 통합할 방의 x좌표가 더 크다면, ((새로운 x) - (이전 y)) 값 만큼 방의 개수가 늘어난다는 뜻이다. 만약 새로운 x의 좌표가 현재 y보다 작다면 새로운 방은 더 생기지 않는다. N에서 y의 최댓값을 뺀 값을 ..

[백준 1941] 소문난 칠공주 (C++)

1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 처음에 단순 dfs로 갔다가 ㅓㅏㅗㅜ 모양으로 탐색이 불가능해서 바로 접었다. bfs로 다시 도전하는데 정점간의 상태정보를 공유할 수가 없어서 방법을 생각하다가 모든 경우의 수가 최대 25C7 = 48만으로 충분히 탐색 가능함을 깨닫고 dfs를 사용해서 상태 정보를 기록하고 구한 상태들이 서로 이어져 있는 경우를 찾는 방식으로 시도를 했다. 2차원 배열을 1차원 배열로 바꿔서 편하게 백트래킹을 할 수도 있었지만 굳이 내가 2차원 배열을 유지하면서 백트래킹을 해보려는..

[백준 1043] 거짓말 (C++)

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 재미있는 문제였다. 나는 사람과 파티를 똑같이 하나의 정점으로 보았다. 둘다 최대 50이므로 사람은 51부터, 방은 1부터 번호를 가지도록 설정했다. 진실 감별사부터 시작하는 dfs를 수행한다. 이때 연결되는 모든 정점은 진실 감별사로 바뀌게 된다. 처음 주어진 진실 감별사와 연결된 모든 정점을 진실 감별사로 바꾸고, 아직까지 진실 감별사가 되지 않은 사람의 수를 출력하면 답을 구할 수 있다. 처음에 Union find로 풀려고 했다가 너무 어려워졌다. 그래프를 계속 그려..

[백준 2616] 소형기관차 (C++)

2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 현재 칸을 선택할 때, 선택하지 않을 때를 정해서 재귀를 수행하면 되는 문제이다. 현재 칸을 선택하지 않는다면 현재 칸의 번호를 +1 한 채로 다음 칸으로 넘어간다. 현재 칸을 선택한다면? 현재 칸부터 소형 기관차의 크기만큼 연속된 칸에 타있는 손님의 수를 누적합 배열 parr을 통해서 구해준다. 그리고 현재 칸의 번호를 +소형기관차의크기 한 채로 다음 칸으로 넘어간다. 기저 조건은 소형 기관차를 선택한 횟수가 4가 되거나 현재 칸을 선택해도 소형 기관차의..

[백준 2696] 중앙값 구하기 (C++)

2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 일단 처음에 들어오는 값은 반드시 최초의 중앙값이고 최초의 기준값이 된다. 그리고 앞으로 들어오는 값을 현재 기준과 비교해서 기준보다 크다면 최소 힙에, 기준보다 작다면 최대 힙에 넣어준다. 만약 지금까지 입력받은 수가 짝수라면 넘어간다. 하지만 홀수라면 현재 기준값이 중앙값이 되기 위해서는 최소 힙과 최대 힙에 들어있는 원소의 수가 서로 같아야 한다. 코드 : 만약 최소 힙의 수가 더 많다면 최소 힙에서 최상단 원소를 중앙값으로 둘..

[백준 1199] 오일러 회로(인접 리스트) (C++)

[백준 1199] 오일러 회로 C++ 1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 hyeo-noo.tistory.com 예전에 풀었던 오일러 회로 문제가 인접행렬로 풀 수 없게 데이터가 추가되면서 많은 사람들이 시간초과의 늪에 빠졌었다. 나도 마찬가지로 시간초과로 틀리게 되었고 4달이 지나서야 인접 리스트 방식의 오일러 회로를 공부하고 다시 풀게 되었다. INPUT 우선 input 부분에 많은 변화가 있었다. i에서 j로 가는 간선을 인접 행렬로 저장하지 않고 간선 그 자체로 저장했다. 대신에 j에서 i로 가는 간선은, 입력에서 i에서 ..

[백준 1948] 임계경로 (C++)

1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 단방향 그래프(DAG)임을 유의 특정 도시에서 모두 만나는데 걸리는 시간은 시작도시에서 특정 도시까지 가는데 걸리는 모든 시간 중 최댓값이 된다. 따라서 BFS를 통해 모든 정점에 대해 걸리는 시간 값을 구할 수 있다. 도착 정점까지 쉬지 않고 달려야 하는 사람이 지나는 도로의 개수의 의미는 도착 정점을 시작점으로 해서 되돌아 갈 때, '도착 정점까지 가는데 걸리는 시간 - 도착 정점을 시작으로 특정 정점까지 가는데 걸리는 시간 = 시..

[백준 17398] 통신망 분할 (C++)

17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 문제를 읽어보니 통신망들의 집합을 구현해야 했다. 서로 연결이 되어있는 통신망, 즉 하나의 정점으로 귀납되는 노드들 사이의 한 간선을 끊으면 2개로 나뉠 텐데 몇 개씩으로 나눠지는지를 구하면 된다. 풀이 방법을 떠올리기까지 꽤 오래 걸렸는데 처음에 노드의 간선을 끊는 동작을 하나의 쿼리로 보고 세그먼트 트리를 구성해서 풀어야 하나?라는 말만 그럴듯한 이상한 생각을 했다. 그러다가 일단 input에 입력을 다 받고 보니 반대로 생..

[백준 1863] 스카이라인 쉬운거 (C++)

1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1≤n≤50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1≤x≤1,000,000. 0≤y≤500,000) 첫 번째 지점 www.acmicpc.net 스택 높이가 바뀌는 y좌표만 저장하면 된다. 높이가 점점 증가하다가 갑자기 감소했을 때, while문을 돌면서 stack의 top에 위치한 높이가 현재 높이와 같거나 작아질 때까지 pop을 수행한다. 마지막에 stack에 남아있는 건물의 수 만큼 답에 더해준다. 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..