yeony's story

> 유클리드 호제법 최대 공약수를 구할 땐 유클리드 호제법을 이용해야 한다. * 유클리드 알고리즘 * : a, b의 최대 공약수는 (a-b),b의 최대공약수와 같다. 1. 임의의 두 자연수 a,b가 주어졌다. 2. 두 자연수 중에 큰 값을 a라고 가정한다. 3. 큰 수 a 자리에는 a-b와 b값 중에 큰 값을 넣는다. 작은 수 b 자리에는 a-b와 b값 중에 작은 값을 넣는다. 그리고 재귀함수를 호출한다. import sys sys.setrecursionlimit(100000) def gcd(a, b): if b == 0: return a return gcd(max(a - b, b), min(a - b, b)) c1, p1 = map(int, input().split()) c2, p2 = map(int,..

> 다이나믹 > 조합 일단 조합으로 먼저 푼 문제 해당 문제는 서로 다리가 교차되는 일은 허용되지 않으므로 순열(중복허용)대신 조합(중복불허)을 사용함. 조합은 팩토리얼 함수를 이용해서 구할 수도 있고, permutation 함수를 이용할 수도 있음. 해당 문제에서는 팩토리얼을 재귀함수로 구현 ex) 6C3 = 6 * 5 * 4 // 3! 8C3 = 8 * 7 * 6 // (3!) -> ( factorial(8) // factorial(8-3) ) // factorial(3) t=int(input()) def factorial(n): if n==0 or n==1: return 1 return factorial(n-1)*n for _ in range(t): w,e=map(int,input().split()..

https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 이분 탐색으로 풀려다 실패하고 결국 다이나믹 프로그래밍으로 푼 문제다 ^0^ 사실 이것도 구글링...해서 겨우 이해한 문제ㅜㅜㅜ power=max(a,b) 이 부분이 이해가 되지 않아서 애를 먹었다. a에 들어가는 건 j번째 -> i번째로 이동할 때 쓰여지는 힘 b에 들어갈 건 j번째까지 탐색을 진행했을 때 구해진 최소의 힘이다. 앞에서..

> 이분 탐색 https://www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 이분 탐색 문제를 풀 때마다 헷갈렸던 거! left, right 값에 인덱스를 넣어야할 때도 있고, 0,max(array)처럼 0과 배열의 최댓값을 넣어줘야 풀리는 문제도 있었다. 근데 언제 인덱스를 넣어야하는지, 최댓값을 넣어줘야하는지 기준이 잡히지 않아서 헤맸던 문제다. 1. 문제에서 값을 구하라고 하는 문제 > 배열의 최댓값을 right에 넣어줌. l..

> 이분탐색 https://www.acmicpc.net/problem/1654 k, n = map(int, input().split()) array = [int(input()) for _ in range(k)] left = 1 right = max(array) result=0 while left [2792] 보석상자 in python > 이분탐색 평소에는 이분탐색을 풀 때 cnt==n일때, cnt cnt>n일때 각각 조건을 나눠 계산을 진행해줬다. 그러나 이번 문제처럼 최솟값이나 혹은 최댓값을 구할 땐 위 방식보다는 아래 코드와 같이 eboong.tistory.com

> 벨만포드 알고리즘 다익 스트라 : 모든 간선의 비용이 양수일 때 최단 경로를 구할 수 있다. 심지어 음수간선이 포함되어 있더라도 해당 간선이 순환되는 구간이 없으면 된다. https://youtu.be/Ppimbaxm8d8 그러나 음수 간선이 순환되는 경우에는 다익스트라는 사용할 수 없고, 벨만 포드 알고리즘을 사용해야한다. 1. 출발 도시 설정 2. 최단 거리 테이블 무한으로 초기화 3. 벨만 포드 알고리즘 시행 3.1. 다음 과정을 n-1번 반복한다. 3.2. 만약 dist[a]의 값이 무한이 아니고, dist[b]의 값이 dist[a]+c값보다 크면? dist[b]에 dist[a]+c, 최단경로를 넣어준다. 3.3 만약 현재 i가 n인데도 갱신이 이뤄졌다면? -> 음수..

> dfs dfs 개념을 다시 짚고 넘어가자.. 갑자기 막 헷갈림 ㅠㅠ (1) 재귀함수를 이용한 dfs 구현 방문처리는 함수 맨 첫줄에...! 방문하지 않은 노드가 있다면 재귀함수만 호출시킴. def dfs(node): visited[node]=False # 현재 노드 방문처리 for i in array[node]: # 현재 노드와 연결된 노드들중에 if not visited[i]: # 방문하지 않은 노드가 있다면 dfs(i) # dfs(i) 재귀함수 호출 (2) stack을 이용한 dfs 구현 방문처리는 while문 안에서..! 방문한 노드가 아닐 경우의 조건문 안에서! def dfs_iteration(graph, root): visited = [] stack = [root] while(stack): ..

> 깊이 우선 탐색 > 그래프 탐색 아래와 같이 코드를 작성해서 제출했더니 재귀 관련 오류가 났다. n, r, q = map(int, input().split()) tree = [[] for _ in range(n + 1)] for i in range(n - 1): a, b = map(int, input().split()) tree[a].append(b) tree[b].append(a) query = [int(input()) for _ in range(q)] def check(node): count[node] = 1 for child in tree[node]: if not count[child]: check(child) count[node] += count[child] return count[node] ..

> bfs 문제 최소 경로를 출력해야한다길래 max로 매번 경로횟수를 체크해줘야하나 생각했으나 1칸씩 이동할때마다 +1씩 증가시키고 도착점에 도착하면 현재 횟수를 출력한다. 큐에 cnt 횟수까지 넣으면 메모리초과 남.. from collections import deque n = int(input()) r1, c1, r2, c2 = map(int, input().split()) # 1~6번 순으로 dx = [-2, 0, 2, 2, 0, -2] dy = [1, 2, 1, -1, -2, -1] def bfs(): queue = deque() queue.append((r1, c1, 1)) visited = [[False for _ in range(n)] for _ in range(n)] visited[r1][..

> 문자열 예시는 s= abab 1번째 생각) s = s + s[0] 위 식은 위 예시에만 성공적 2번째 생각) s=qwerty s=s+s[len(s)-1::-1] qwerty + trewq = qwertytrewq 위 예시에서는 성립. 하지만 abab + aba abababa 똑같이 역으로 해도 똑같은 값이 나오긴 하지만 가장 짧은 팰린드롬을 만드는 방법은 아니다. 3번째 생각) s = abdfhdyrbdbsdfghjkllkjhgfds 위 예시에서 2번째 방법을 대입했더니 53이 나옴 나와야하는 답은 38... 그래서 다시 살펴봄 문자열 내 부분 문자열이 팰린드롬일 경우를 생각해줘야한다. 만약 팰린드롬이 문자열 끝부분에 위치해있다면? 2번째 방법을 사용하면 가장 짧은 팰린드롬을 구할 수 없게 된다. s..