수학자로 유명한 유클리드(Euclid)는 최대공약수에 다음과 같은 성질이 있다는 것을 발견하였다. - a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, a % b) - 어떤 수와 0의 최대공약수는 자기 자신이다. 즉, gcd(n, 0) = n def gcd(a, b): if b == 0: # 종료 조건 return a return gcd(b, a % b) print(gcd(1, 5)) # 1 print(gcd(3, 6)) # 3 print(gcd(69, 24)) # 3 print(gcd(81, 27)) # 27
코테/코딩테스트 대비 Python
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 2번의 "틀렸습니다" 결과를 보고 질문 게시판을 보면서 반례들을 시도 해보면서 풀려고 했는데 결국 못풀어서 다른 사람의 풀이를 참조했다. 오답2의 코드는 cctv 감시영역을 확장할 때 매번 가장 많이 확장한 방향을 선택해서 확장해 나간다. 계속 틀려서 반례를 찾아봤다. 질문 게시판의 대부분의 반례를 통과해서 답답하던 중 통과되지 않는 반례를 찾았다. 이 반례를 통해 dfs + 완전 탐색..
https://www.acmicpc.net/problem/22234 22234번: 가희와 은행 가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다. [그림 1] 카운터 직원과 N명의 손님 x번 손님에 대한 정보는 x번 손님의 www.acmicpc.net 틀린코드 - 런타임에러 원인을 모르겠음 import sys from collections import deque from queue import PriorityQueue input = sys.stdin.readline print = sys.stdout.write N, T, W = map(int, input().split()) p, t = map(int, input().split()) pq ..
LSC 설명 블로그 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(L..
https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 정답코드 import sys from collections import deque import heapq dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] input = sys.stdin.readline N,M,Fuel = map(int, input().split()) # 1: wall 2: 승객 3: taxi board = [] for i..
https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 헤멨던 부분: 1. "파이어볼 질량의 합"을 출력해야 하는데 파이어볼의 갯수를 구하고 있었다. 2. 명령의 2번 과정에서 파이어볼들이 나누어지고 이동하는 줄 알았음 느낀점: 예제의 출력이 왜 그렇게 나오는 지 생각하고 풀어야겠다. 예제 설명 첫 명령의 1번 과정 이후 (각 (m, v, d)는 질량 m, 속력 v, 방향 d인 파이어볼을 의미함) [] [] [(..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 확산 문제 풀 때 -> 2차원 배열 돌면서 visit 처리 -> visit 안된거 있으면 bfs or dfs from collections import deque N, L, R = map(int, input().split()) population = [] dx = [0, 0, 1, -1] dy =[1, -1, 0, 0] for i in range(0, N): population.ap..
#오른 위 왼 아래 dx = [0, -1, 0, 1] dy = [1, 0, -1, 0] #반시계방향 d = 0 before = 0 x, y = p, 1 while True: nx = x + dx[d] ny = y + dy[d] if nx == r or ny == c or nx == -1 or ny == -1: d = (d+1)%4 continue if x == p and y == 0: break room[x][y], before = before, room[x][y] x, y = nx, ny #시계방향 p = purifier[1] #오른쪽부터 시작 d = 0 before = 0 x, y = p, 1 while True: nx = x + dx[d] ny = y + dy[d] if nx == r or ny =..
