안녕

0. 문제 링크 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 1. 풀이 방법 예전 알고리즘 시간에 풀었던 문제라 비교적 간단하게 풀 수 있었음 2022.04.15 - [Computer Science/알고리즘] - [알고리즘] 동적 계획법 - 연쇄 행렬곱셈 (Chained Matrix Multiplication) 예전에 내가 쓴 글을 보면 자세히 설명해 놓았음 키 포인트는 i ~ i + dia까지의 최적을 구하기 위해서는 i ~ ..

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

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

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

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