L.O.K

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net ◎ 문제풀이 NXN 크기의 사탕상자를 교환하여 같은 색상이 연속된 사탕개수의 최댓값을 탐색하는 문제이다. 시간제한이 1초인데 N의 최댓값이 50이니 반복문으로 완전탐색해도 시간제한에 걸리지 않는다. 1) 사탕상자에서 연속된 같은 색상 사탕개수의 최댓값을 구하는 함수를 만든다. 2) 인접한 사탕을 교환할 때마다 1)에서 생성한 함수를 호출한다. 브루트포스는 원리는 단순하나 단순한만큼 코드가 길어지므로 구현력을 키워야 한다. ◎ 코드 import sys input = sys.stdin.readline n = int(i..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net ◎ 문제풀이 순회를 하려면 '노드'를 '기억'해야 한다. '기억'을 담당하는 자료구조는 STACK이다. 나는 두 가지를 놓쳐서 이 문제를 어렵게 풀었다. 1) 파이썬의 딕셔너리 자료형을 몰랐다. tree = {} 딕셔너리 자료형은 Map처럼 key-value 구조로 이루어져 있다. 딕셔너리 자료형을 몰라서 인덱스로 접근하는 리스트 자료형을 사용하였다. 2) 재귀호출을 발상하지 못했다. 재귀호출은 함수의 호출을 이용한다. 함수는 STACK영역에 쌓이므로..

9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ◎ 문제풀이 1,2,3 기저조건이 있고 목표값까지 가는 경우의 수를 구하는 문제이니 DP문제이다. 1,2,3으로 10을 구하는 경우의 수를 d(10)이라고 하자. 10을 구하는 사건은 3가지 사건이 있다. 사건 ① : 9 + 1 사건 ② : 8 + 2 사건 ③ : 7 + 3 3가지 사건은 모두 독립사건이다. 그러므로 d(10) = d(9) + d(8) + d(7)이 성립된다. dp는 기저조건으로 독립사건을 구하여 점화식을 도출하는 것이 중요하다. ◎ 코드 n = int(input()) def dp(value) : d = [0]*11 d[1],d[2],d[3] ..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net ◎ 문제풀이 그래프를 탐색하여 A ⇢ B ⇢ C ⇢ D ⇢ E 경우가 있는지 탐색해야 한다. 그래프의 탐색은 DFS와 BFS가 있다. 참조의 참조를 하는 문제이므로 DFS가 적절하다. DFS는 STACK으로 구현된다. STACK은 '기억' 기능이 있어서 함수가 호출되면 STACK 영역에 차례대로 쌓여 호출된 순서가 기억된다. 그러므로 DFS는 STACK을 직접 구현하지 않아도 재귀호출를 사용하면 된다. 위 문제를 풀면서 놓친 부분은 3가지가 있다. 1) 방문이력테이블이 필요하다는 생각 X 깊이탐색은 count가 4일때까지 이루어진다. 여기에는 재방문이 포함될 수 있다...

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net ◎ 문제풀이 단순 반복문으로 풀면 시간초과가 난다. 자료구조로 시간복잡도를 줄일 수 있는 능력을 보는 문제이다. [CodingTest] BOJ1046 에디터 ( 자료구조 ) with Python ◎ 문제 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 lordofkangs.tistory.com ( 위 문제도 자료구조로 시간복잡도를..

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ◎ 문제풀이 N에서 K를 구하는 문제이다. 연산은 3가지이다. +1, -1, x2 연산 한번에 1초가 소요되고 몇초가 걸리는지를 구하는 문제이므로, 연산횟수를 구하는 문제이다. 시작점과 목표점이 주어지고 최소연산횟수를 구하는 문제이다. 1) DP가 아니라 BFS 문제 나는 DP가 먼저 연상되었다. 그러나 DP보다는 BFS가 더 적합한 알고리즘이다. 그 이유는 '시작위치'에 있다. DP는 더이상 쪼갤 수 없는 시작위치에서 목표지점까지 구..

10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net ◎ 문제풀이 문제에 제시된 단어 하나하나를 모두 자료구조로 만들 필요는 없다. (완벽주의 조심!) 문제의 목적에 달성하기 위한 수단만 필요할 뿐이다. 즉, 레이저, 막대가 나왔다고 레이저, 막대를 자료구조로 만들 필요가 없다는 의미이다. 레이저가 막대기를 자르면 막대의 개수는 레이저 개수 + 1개 이다. "()"가 레이저이므로 레이저가 나올때까지 막대를 기억해야 한다고 생각해서 STACK을 떠올렸다. ")"는 두가지 경우가 있다. 1. 레이저인 경우 레이저가 등장하면 STA..

17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net ◎ 문제풀이 문자열을 조작하는 문제이다. 파이썬은 다양한 문자열 조작 함수를 제공하기에 간편하게 풀 수 있다. 문제의 목적은 태그(특수문자), 공백(특수문자)로 구분되는 문자열을 뒤집기이다. 문자열을 뒤집는 함수인 reverse()와 특수문자를 구분하는 isalnum()을 이용하면 문제에 쉽게 접근할 수 있다. 1) Pointer 하나를 만들고 문자열을 탐색한다. 2) 태그를 만나면 태그가 끝날때 까지 Pointer를 1씩 증가한다..

◎ 문제 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net ◎ 문제풀이 구간합을 구하는 문제이다. 시간제한이 1초이다. 대략 연산횟수 1억~10억이 1초가 걸린다. 반복문을 이용하면 시간복잡도는 O(N)이다. N은 최대 크기는 10만이다. 구간합을 M번 구해야 한다. 고로 N x M 연산해야 한다. 시간복잡도는 O(NM)이다. M도 10만이 최대이므로 최대 100억번의 연산을 수행해야 한다. 반복문을 활용하면 시간제한에 걸린다. 그러니 prefix-sum 알고리즘을 활용해보자. prefi..

@문제 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net @문제풀이 두 가지 풀이가 있다. 1) 유클리드 호제법 2) 파이썬 math 라이브러리 사용 유클리드 호제법 자연수 A를 B로 나눌때 나머지 r이라면 유클리드 호제법은 A와B의 최대공약수는 B와 r의 최대공약수와 동일함을 의미한다. 유클리드호제법 증명은 위 영상을 참고바란다. 그러면 B를 r로 나눌때 나머지 r2의 최대공약수도 A와B의 최대공약수와 동일하다. 그러면 r을 r2로 나눌때 나머지 r3의 최대공약수도 A와B의 최대공약수와 동일하다. . . . 그러면 rn-2를 rn-1로 나눌때 나머지 rn이 0이 되면 rn-1..