https://www.acmicpc.net/problem/9935 이해 문자열을 완전 탐색을 통해 더했다가 뺐다가 할 수 있지만, 최대 길이가 1,000,000 이므로 뺄때, 붙일 때 길이만큼 탐색하고, 제거/더해줌 반복되므로 시간 초과가 날 수 있음 Stack 구조의 append/pop 연산을 통해 중복되는 반복을 제거하고, 최대 폭발 문자열의 길이만큼만 반복하게 하여 시간을 줄일 수 있음 구현 Stack으로 이용할 리스트 생성 Stack에 문자열 하나씩 저장하며, 길이가 폭발 문자열 길이 보다 길어졌을 때부터 폭발 문자열이 stack 내부에 있는지 확인 → 마지막 길이만큼만 확인하면 모두를 확인할 수 있음 만약 폭발 문자열이 있다면 pop 연산을 통해 제거 없다면 계속해서 append 연산을 통해 S..

https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 이해 문자열 탐색을 통한 완전탐색 구현 문제 해당 단어를 탐색하여 개수를 센 후, 이를 비교해도 시간이 충분하다.(O(1,000,000)) 구현 각 단어별 구성하고 있는 단어와 그 개수를 저장할 dictionary 생성(편의를 위한 defaultdict 사용) 단어별 구성 단어와 개수를 저장 단어별 구성 단어 개수에서 기준 단어 구성 단어의 개수를 빼서 개수를 재구성(아래와 같이 표현) 해당 단..

https://www.acmicpc.net/problem/1149 이해 완전 탐색을 통해 해결할 수 있지만, 완전 탐색시 O(3000^3)으로 시간 초과 동적 계획법을 통해 빨강, 초록, 파랑으로 칠하는 경우 중 비용이 가장 작은 경우만 저장하는 배열을 통해 해결 구현 빨강, 초록, 파랑으로 칠할 경우 드는 비용을 저장할 dp배열 생성 N개의 집을 칠하기에 빨강, 초록, 파랑 각각 칠해온 비용을 저장할 N*3배열 생성 dp 배열은 최대의 경우를 가정했을 때 나오는 수보다 1큰 수로 저장 dp = [[1000 * 1000+1] * 3 for _ in range(N)] dp배열의 첫번째 줄은 첫 집을 빨강, 초록, 파랑을 칠할 경우의 비용으로 채움 for i in range(3): dp[0][i] = cos..

https://www.acmicpc.net/problem/15684 이해 사다리를 모두 놓아보면서 판별해야하는 문제 DFS 를 통해 완전 탐색을 하되, 중간 가지치기를 이용한 시간을 단축해야함 구현 사다리 타기를 통해 i → i 가 모두 가능한 지 체크 하는 함수 DFS를 통해 사다리를 놓는 경로를 모두 탐색해야하는 함수 사다리 조작에 있어 사다리를 추가할 때, 추가한 사다리가 3개가 초과되면 가지치기 만약 이전에 확인된 사다리의 조작한 사다리 수가 현재 돌고 있는 사다리의 조작한 사다리 수 보다 높은 경우 가지치기 사다리를 놓음에 있어 만약 2개 혹은 3개째 사다리를 놓을 때는 이전에 놓았던 사다리 위치보다 위에 놓을 필요가 없음 코드 # 15684 사다리 조작 import sys input = sys..

https://www.acmicpc.net/problem/1932 이해 완전 탐색을 통해 모든 경우의 수를 확인하는 방식을 사용할 수 있지만, 삼각형의 크기가 1~500 이기 때문에 완전 탐색을 할 경우 시간 초과가 날 수 있다.(2^500가지 경우의 수) 따라서 동적 계획법이용하여 시간을 줄여야 한다. 구현 동적 계획법(DP, Dynamic Programing 이하 DP)을 사용하되, 기본적인 풀이 방식이 아닌 입력을 받은 후, 입력받은 배열을 변경하는 식으로 구현 문제에 있는 크기 5의 정수 삼각형을 예시로 들어보자 i/j j=0 j=1 j=2 j=3 j=4 i=0 7 0 0 0 0 i=1 3 8 0 0 0 i=2 8 1 0 0 0 i=3 2 7 4 4 0 i=4 4 5 2 6 5 i=0일 때는 Pa..

개념 신장 트리(Spanning Tree) 모든 정점을 포함하면서 사이클이 없는 그래프 특징 원 그래프의 모든 정점을 포함 간선(node) 수 = 정점 수 - 1 노드 간 사이클을 형성하지 않음 한 그래프 내에서 여러 개의 신장 트리를 가질 수 있음 최소 신장 트리(Minimum Spanning Tree) 간선(node) 가중치의 합이 가장 작은 신장 트리 간선(node) 가중치가 가장 낮은 간선부터 탐색하여 신장트리를 구성하는 방식 대표 알고리즘 : Kruskal 알고리즘, Prim 알고리즘 차이점 Kruskal 알고리즘 : 간선(node)를 중심으로 하여 신장 트리를 구성 Prim 알고리즘 : 정점(spot)을 중심으로 하여 신장 트리를 구성 크루스칼(Kruskal) 알고리즘 가장 작은 가중치를 갖는..