안녕

0. 문제 링크 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 1. 풀이 방법 파이썬에는 우선순위 큐를 위한 모듈이 있음. 해당 모듈을 사용하면 최솟값 힙, 최댓값 힙을 구현할 수 있음 최솟값 힙, 최댓값 힙을 만들었음 여기서 생기는 문제점은 최솟값 힙에서 삭제한 숫자가 최댓값 힙에는 적용되지 않는다는 문제점임 따라서 최솟값 힙에서 삭제한 숫자를 따로 저장하는 딕셔너리를 만들었음. 최댓값 힙에도 마찬가지로 생성함 만약 최솟값 힙에서 숫자 ..

0. 문제 링크 https://www.acmicpc.net/problem/1045 1045번: 도로 0부터 N-1까지의 번호가 매겨져 있는 N개의 도시와 두 도시를 연결하는 도로가 있다. 도로에는 우선순위가 있는데, A와 B가 (A < B) 도로 x로 연결되어 있고, C와 D가 (C < D) 도로 y로 연결되어 있을 때, www.acmicpc.net 1. 풀이 방법 edge가 (a, b)가 있다면, a < b가 되도록 모든 간선을 우선순위 큐에 넣음 이때 모든 간선의 개수가 m보다 작다면 -1을 출력 크루스칼 알고리즘을 사용하여 mst를 만들었음 만약 mst가 만들어지지 않으면, 모두 연결되지 않는 것이므로 -1을 출력 크루스칼 알고리즘을 진행하는 도중에 쓸모없는 간선은 따로 관리함 이때 우선순위 큐로 ..

0. 문제 링크 https://www.acmicpc.net/problem/20442 20442번: ㅋㅋ루ㅋㅋ 어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다. www.acmicpc.net 1. 풀이 방법 https://chanu-ps.tistory.com/24 우선 위의 블로그를 참고하였습니다. 맨 처음에 원포인터로 각 R의 위치에서 양 옆의 K의 개수를 세서 구하는 식으로 했는데, 예제랑 질문 게시판의 반례도 다 맞았는데도 1% 펑하길래 좀 힘들었습니다. 혼자 막 도전하다가 결국 구글링을 했는데, 위의 블로그가 매우 잘 정리해놓았습니다. 그래도 혹시 문제가 이해 안 간다던가 풀이가 이해가 ..

0. 문제 링크 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 1. 풀이 방법 일단 문제를 보고 나서 MST를 구하는 문제라는 것은 쉽게 알아차렸음. 아무 생각 없이 크루스칼 알고리즘을 짜고 예제를 돌리는데, 틀렸음 왜 틀렸는지 곰곰히 생각을 해봤음 생각해 보니까 이게 무방향 그래프인데, 두 개의 노드에 최대 두 개의 무방향 엣지가 연결되는 것이 가능함 그래서 무방향 엣지 중에 작은 애를 고르고, 걔를 우선순위 큐에 넣었음 그러고 나서 ..

0. 문제 링크 https://www.acmicpc.net/problem/3107 3107번: IPv6 첫째 줄에 올바른 IPv6 주소가 주어진다. 이 주소는 최대 39글자이다. 또한, 주소는 숫자 0-9, 알파벳 소문자 a-f, 콜론 :으로만 이루어져 있다. www.acmicpc.net 1. 풀이 방법 비교적 간단했던 문제 첫 번째는 ::을 복원하는 것이다. 파이썬의 split(':')을 사용하면 :을 기준으로 나누는데, 만약 맨 앞이나 맨 뒤에 ::이 있다면, 리스트에 ''이 두 개나 들어가게 된다. 참고로 중간에 ::이 있으면 ''이 하나만 들어감 아무튼 ''의 개수를 세서 그게 맞게 0000의 그룹을 복원함 그 다음에는 이제 앞의 0이 없어진 상황을 봐야하는데, 간단하게 길이가 4보다 작으면, 그..

0. 문제 링크 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 1. 풀이 방법 문제를 보자마자 BFS로 풀려고 했다. 여기서 키포인트는 비어있는 칸에 방문했는데, 근처에 쓰레기가 있다면 해당 비어있는 칸을 다른 어떤 값으로 변경해줘야 한다. 아 그리고 문제를 잘 읽어야 한다. 처음에 문제 잘못 읽어서 조금 고생했음 풀이 방법은 비교적 쉽다. 비슷한 류의 문제를 풀어서 그런가 쉽게 느껴졌음 왜냐면 최적의 조건이 딱 ..

0. 문제 링크 https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 1. 풀이 방법 문제를 보고 살짝 투포인터로 풀까 고민했는데, 그렇게 풀면 무조건 시간 초과가 날 것 같아서 포기했다. 양쪽을 한 번에 봐야 하나 싶었는데, 생각을 좀 해보니까 양쪽을 한 번에 볼 필요가 없었음 그냥 왼쪽을 봤을 때의 개수를 세고, 오른쪽을 봤을 때의 개수를 세면 되는 일 ! 그러면 이제 특정한 방향을 봤을 때의 개수와 그때의 건물 번호는 어떻게 세야 할까? 처..

0. 문제 링크 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 1. 풀이 방법 전형적인 MST 문제 프림과 크루스칼 중 뭐로 풀까 고민했다. 시작은 프림으로 했는데, 이유는 시작 도시가 1번 도시이므로 1번부터 정점에 넣어서 MST를 탐색하는게 맞다고 생각했다. 근데 내 구현 issue로 인해, 엄청난 시간초과가 나버렸다... 그래서 결국 크루스칼 알고리즘으로 문제를 풀었다. 생각해보니까 어차피 MST면 1번 정점을 포함하니까,,,,뭐 그냥 크루..

0. 문제 링크 https://www.acmicpc.net/problem/12757 12757번: 전설의 JBNU 첫 줄에는 초기 데이터의 개수인 \(N(1 \le N \le 100,000)\) 과 명령 횟수인 \(M(1 \le M \le 100,000)\), 가장 근접한 Key까지의 거리의 제한인 \(K(1 \le K \le 10,000)\)가 주어진다. 입력의 둘째 줄부터 N개의 줄에 www.acmicpc.net 1. 풀이 방법 눈 씻고 봐도 쌩구현 문제 (+정정, 구현 아니고 탐색 관련 문제였음) 가장 중요한건 인접한 키를 찾는 로직이 가장 중요하다. 이때 Linear로 인접한 키를 구하는 순간 시간 초과가 난다. 따라서 다른 방법으로 탐색해야 한다. 나는 이진 탐색을 골랐다. 아마 더 좋은 방법이..

0. 문제 링크 https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1