alpyrithm_알파이리즘

1743 음식물 피하기 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진� www.acmicpc.net 문제 풀기 전 공부할 것 : 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 풀이 1 음식물을 waste에 입력받는다. idx 리스트에 음식물 위치를 저장한다. check 리스트를 만들어 이미 뭉친 음식물인지 아닌지 판별한다. idx 리스트가 비어질 때까지 while문을 반복한다. 음식물 위치를 pop 해서 만약에 이미 뭉친 음..

1965 상자넣기 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 �� www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 상자를 입력받고 dp array를 1(해당 상자 1개)로 초기화해서 만든다. for문을 돌면서 주어진 상자 순서보다 앞에 있는 상자 중 크기가 작을 때 상자의 수+1과 비교해서 큰 값을 dp에 저장한다. dp 중 max인 값을 출력한다. n = int(input()) box = list(map(int, input().split()..

1735 분수 합 www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 문제 풀기 전 공부할 것 : 수학, 정수론, 유클리드 호제법 풀이 1 분모들의 최소공배수로 통분하여 계산한다. 최대공약수를 구하는 gcd 함수를 만든다. 분모들의 최소공배수로 통분하여 분모를 구하고 분자도 구한다. 분자와 분모를 기약 분수로 만들기 위해 최대공약수로 나눈다. def gcd(a, b): while a % b != 0: mod = a % b a = b b = mod return b a, b = map(int, input().split..

11660 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍, 누적 합 풀이 표를 입력받아 table에 저장한다. 완전 탐색을 하면 시간 초과가 뜨기 때문에 dp를 이용해서 해결해야 한다. table의 (x, y) 즉, x행 y열은 1행 1열부터 x행 y열까지의 합으로 채워지도록 for문을 통해 구현한다. 행의 누적 합을 먼저 구한다. ..

2407 조합 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 풀기 전 공부할 것 : 수학 풀이 1 조합을 구하는 것이므로 factorial 함수를 만들어서 해결한다. nCm은 n! / m! * (n-m)!이다. n, m = map(int, input().split()) def factorial(a): res = 1 for i in range(a): res *= (i+1) return res if m > (n//2): m = n - m print(factorial(n)//(factorial(m)*factorial(n-m)))

11659 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에 www.acmicpc.net 문제 풀기 전 공부할 것 : 누적 합 풀이 1 완전 탐색으로 해결하면 시간 초과가 발생할 수 있기 때문에 누적 합을 이용해서 해결하기 누적 합 리스트 nums_add를 구하면 i에서 j까지의 합은 nums_add[j] - nums_add[i-1]과 같다. nums_add[j]는 j까지의 숫자의 합이다. nums_a..

1057 토너먼트 https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 문제 풀기 전 공부할 것 : 수학, 브루트포스 알고리즘 풀이 1 김지민의 번호와 임한수의 번호를 입력받는다. 토너먼트에서 항상 승리하기 때문에 김지민과 임한수는 대결하지 않는 경우는 없다. 토너먼트 규칙을 찾으면 된다. 토너먼트를 할 때 1, 2가 붙어 다음 라운드에서 1이 되고 3, 4가 붙어서 다음 라운드에 2가 된다. 이를 적용했을 때 번호가 홀수이면 1을 더하고 짝수이면 그대로 ..

9655 돌 게임 https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍, 게임 이론 풀이 두 사람이 완벽하게 게임을 하는 것이므로 모든 상황을 고려했을 때 짝수이면 창영이가 이기고 홀수이면 상근이가 게임을 이긴다. n = int(input()) if n % 2 == 0: print('CY') else: print('SK') 9656 돌 게임 2 https://www.acmicpc.net/problem/9656 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc..