안녕

0. 문제 링크 https://www.acmicpc.net/problem/12764 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 1. 풀이 방법 우선순위 큐를 3개나 사용해서 풀었음 첫 번째는 시작 시간 순서대로 정렬한 리스트 - A 두 번째는 끝나는 시간을 기준으로 정렬한 리스트 - B 세 번째는 자리의 번호를 정렬한 리스트임 - C A에서 시간을 뽑음 그리고 B에 넣고, C에서 가장 작은 자리의 번호를 추출함 그 다음에..

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/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 1. 풀이 방법 2. 코드 import sys from itertools import permutations input = sys.stdin.readline def sol(): flag = [[True] * n for _ in range(n)] for i, j, k in permutations([*range(n)], 3): if maps[i][k] == maps[i][j] + ..

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. 풀이 방법 해당 방법은 그리디여서 어떻게 풀지 생각이 좀 많았다. 인구가 가장 많은 곳을 기준 잡고, 그 다음 많은 곳을 향해 우체국 위치를 조정할까 이런 생각을 하다가 이건 최적을 보장하지 못한다는 생각이 들어서 그만뒀다. 음..이런 문제를 풀 때, 이게 최적이라는 보장이 있을까요? 그리디는 ..

0. 문제 링크 https://www.acmicpc.net/problem/2374 2374번: 같은 수로 만들기 n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한 www.acmicpc.net 1. 풀이 방법 일단 같은 숫자면 같은 그룹이므로, 중복으로 넣어야 되나 싶었다. 그래서 일단 넣을때부터 같은 그룹이면 하나의 숫자만 넣었다. 예를 들어서, 1 1 1 3 1이 입력되면, 1 3 1만 stack에 들어갔다. 그 이후에는 어떻게 숫자를 더할 것인가가 문제인데, 나는 다른 방법을 썼다. 인덱스를 기준으..

0. 문제 링크 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 1. 풀이 방법 문제를 보고 이건 탐색 기법을 써야겠다고 생각을 했다. 문제 무작정 DFS, BFS를 쓰는 건 좀 아닌 것 같았다. 왜냐면 모든 노드에서 다른 노드를 탐색하는 방법을 사용하면 n^2이 될 것 같았기 때문이다. 어떻게 최장거리를 탐색할 것인가에 대해 고민을 했다. 방금 글 쓰면서 떠오른건데 TSP를 조금 손 봐서 최장거리를 찾아낼 수 있을 것 같다..