목록카테고리 (60)
교대최소제곱법
9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문자열 전체를 DP에 저장해서 사용하는 아이디어가 참신했다 공간 복잡도 O(n)로 짠 코드 def lcs(seq, tar): dp = [''] * len(tar) # 배열의 크기는 두 번째로 도는 iter의 크기로 해야한다 ->5번라인으로 for i in range(len(seq)): max_dp = '' for j in range(len(tar)): # 배열의 크기만큼 돈다 if len(max_dp) < len(..
평소에 작업을 정글 깃허브에 브랜치를 열고 했었는데 이번 주차가 끝나니 알 수 없는 오류가 생겼다 클론을 땄는데 알 수 없는 커밋이 생긴 것! 이대로 두면 나중에 작업하고 머지할 때 에러가 발생할 것 같아서 트러블 슈팅을 진행했다 1. 삭제 후 다시 클론하기 -> 여전히 같은 문제 발생 2. 무시하고 커밋을 진행 그냥 깃허브 데스크탑 오류인가 싶어서 그냥 진행해봤다 -> 동일한 파일 한 개 더 생성 ? 3. 왜 너만 그럴까? 이쯤에서 눈치를 챘다 과거에 윈도우에서 개발환경을 설정하면서 한국어 사용자명 때문에 고생을 한 경험이 있었기 때문에 한국어가 문제다는 것을 파악하고 구글링을 돌렸다 https://hyerios.tistory.com/115 깃 한글 파일명 포함 해결 깃에 있는 프로젝트를 다운로드하으니..
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 다시 한 번 겸손을 배울 수 있었던 문제 핵심은 1. 어떻게 분할정복 문제로 볼 것인가 2. 어떻게 메모이제이션을 활용할 것인가 3. 어떻게 구현할 것인가 무려 3개의 난관을 넘어야 풀 수 있는 문제였다. 1. 어떻게 분할정복 문제로 볼 것인가? ABCDE 행렬이 있을 때 A + BCDE, AB + CDE, ABC + DE, ABCD + E 로 분할하여 최소를 찾을 수 있다가 첫 번째..
https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 이번 문제도 위상정렬을 활용하면 최장경로를 구하는 것에는 어려움이 없다. 이번 문제 핵심은 중복되지 않게 도로의 개수를 구해라 중복을 제거하기 위해서 역추적을 통해서 set에 간선을 저장한다 역추적을 하기 위해 노드를 이동할 때 이전 노드를 기억시킬 배열이 필요하고 이는 노드의 최대값이 갱신되거나 같을 때 이전 노드를 기억시킨다. 위상정렬 두 문제를 풀어 보았는데 위상정..
https://www.acmicpc.net/problem/1432 1432번: 그래프 수정 첫째 줄에 정점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 인접행렬 형식으로 입력이 주어진다. 0은 연결되지 않았음을 의미하고, 1은 연결되었다는 것을 의미한다. N은 50보다 작거나 같은 www.acmicpc.net 이번 문제의 핵심은 답이 여러 개일 경우에는 사전 순으로 제일 앞서는 것을 출력한다. 사실 중복되는 답을 찾는 것은 위상정렬만 알면 어렵지 않다. 하지만 사전 순이 매우 큰 난관이었다. 핵심적인 아이디어는 1. 반대로 위에서 내려오는 방식으로 생각할 것 2. 최대 힙을 활용해 큰 인덱스부터 찾을 것 1번까지는 스스로 생각했는데 2번을 생각하지 못해 해결하지 못했다. "거꾸로 생각해도 작은 것부..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net BFS로 빠르게 풀었지만 메모리 초과... 기존의 BFS 문제의 경우 상하좌우 최대 4가지 분기로만 나눠졌기 때문에 메모리 초과 문제가 안났지만 이번 문제는 연결된 노드의 개수만큼 큐에 저장되기 때문에 케이스에 따라 메모리 초과가 날 수 있다는 것을 고려해야했다. BFS문제에서 메모리 초과가 날 경우 -> DP를 첨가해서 풀면 맛이 좋다 from collection..
파이썬 라이브러리는 어떻게 구현할까? 무조건 작은 숫자가 0번 인덱스, 1번이 트리의 루트는 고정이다. 그리고 부모가 인덱스 k일 때 2k의 값은 2k+1보다 크다는 공식을 통해 구현된다 + 23.11.14 왜 트리의 루트를 0번 인덱스부터 시작하지 않을까? 루트를 1에서 시작하면 부모 노드를 찾을 때 단순히 i // 2만 해주면 되는 반면 루트를 0에서 시작하면 (i-1) // 2를 해야하는 번거로움이 있다. 삽입 연산은 → heappush 가장 마지막 인덱스에 값을 넣고 (현재 인덱스) // 2로 부모 인덱스를 찾아서 비교한다 이때 비교의 기준이 작은 것이 올라가면 최소힙, 큰 것이 올라가면 최대힙이 된다. 삭제 연산은 → heappop 파이썬 같은 경우 이미 하나를 빼서 0번 인덱스에 넣어놓는다 0..
B- tree가 무엇인가? 자료구조 중 하나 이진트리와 다르게 하나의 노드에 최대 M개의 자식을 가지는 트리 예를들어 값이 [10, 20]이 있으면 10보다 작은 서브트리, 10과 20 사이의 서브트리, 20보다 큰 서브트리 이렇게 3개의 자식이 생기는 트리가 B-트리이다. 삽입의 경우 M개의 제한을 걸어두고 값이 M개 이상이 되면 (노드는 최대 M-1개 까지 값을 가질 수 있다) 분할이 이루어진다 분할 과정은 가운데 값이 부모 노드로 올라가서 합쳐지는 방식으로 부모노드도 초과할 경우 계속 올라가는 방식으로 삽입이 진행된다 삭제는 더 어렵다, 자세한 것은 블로그 참조 [자료구조] 그림으로 알아보는 B-Tree [자료구조] 그림으로 알아보는 B-Tree B트리는 이진트리에서 발전되어 모든 리프노드들이 같은..