안녕

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/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

0. 문제 링크 https://www.acmicpc.net/problem/20440 20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. 다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE max_value: # 만약 현재의 값이 최댓값보다 크다면 갱신 max_value = cur_value start = i flag = True # 중복으로 end를 갱신하는 것을 방지하기 위함 if flag and bef_value == max_value and cur_value < max_value: # 위에서 갱신했을 때만 end를 갱신함 # 이때 현재 값은..

0. 문제 링크 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1. 풀이 방법 일단 문제를 보자마자 이건 DP라는 생각이 들었다. 가장 문제는 마지막 집과 첫 번째 집의 색이 달라야 한다는 것이다. 사실 마지막 집과 첫 번째 집의 색을 고려하지 않고 짰는데, 알고 보니 고려해야 해서 조금 수정을 했다. 그러면 고려를 한다면 어떻게 해야할까? 많은 고민을 했다. 누가 봐도 DP인데, 어떻게 첫 번째 집의 정보를 저장..

0. 문제 링크 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 1. 풀이 방법 1번 시도(트리라 생각함) 1. defaultDict을 이용해서 자신의 직속 후임을 리스트로 만들어놓음 2. 그리고 우선 자신에게 칭찬을 더하고, 후임들을 또 재귀함 3. 재귀 제한에 걸려서, 다시 수정하고 제출하니 이번엔 시간 초과 2번 시도(트리에 BFS를 적용함) 1. 재귀 때문에 시간 초과라 생각함 2. 그래서 재귀를 bfs로 변경해서 구현함 3. 시간 초..

0. 문제 링크 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 1. 풀이 방법 일단 내가 푼 방식을 먼저 얘기하고 Two Pointer로 풀 수 있는 방법에 대해 얘기해 보자. 나는 일단 정렬 이런 거 안 했다. a, b, c, d가 있으니 a와 b를 합쳐서 ab, c와 d를 합쳐서 cd로 만들었다. 이때 cd를 Counter 객체로 만들었다. Counter 객체는 파이썬 내장 모듈이므로 한 번 찾아보면 될 것 같다. 아무튼..

0. 문제 링크 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 1. 풀이 방법 일단 딕셔너리를 사용해서 B의 부모에 A를 넣었다. 이를 이용해서 각자 자신의 부모를 저장할 수 있게 만들어놓았다. 마지막에 내가 찾고자 하는 a와 b가 있다고 가정하자. a의 부모를 루트 노드 전까지 계속해서 참조하면서 부모들을 집합에 넣었다. 마지막으로 b를 계속해서 루트 노드로 올라가면서 부모들을 집합에 있는..

0. 문제 링크 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, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 1. 풀이 방법 해당 방법은 그리디여서 어떻게 풀지 생각이 좀 많았다. 인구가 가장 많은 곳을 기준 잡고, 그 다음 많은 곳을 향해 우체국 위치를 조정할까 이런 생각을 하다가 이건 최적을 보장하지 못한다는 생각이 들어서 그만뒀다. 음..이런 문제를 풀 때, 이게 최적이라는 보장이 있을까요? 그리디는 ..