alpyrithm_알파이리즘

너비 우선 탐색 7569 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 풀기 전 공부할 것 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 1 토마토 정보를 저장할 box와 익은 토마토의 좌표를 넣을 grow를 선언한다. for문을 돌면서 box와 grow에 각각 토마토 값과 익은 토마토의 좌표를 넣어준다. 이 부분이 이해가 안 되면 주석처리가 된 print 부분을 주석을 없애고 출력해보자. bfs이므..

너비 우선 탐색 7576 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀기 전 공부할 것 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 1 먼저 box에 토마토 정보를 저장한다. 그리고 익은 토마토를 ripe에 넣어준다. 이중 for문으로 box를 돌면서 값이 1인 익은 토마토를 확인하고 해당 위치를 ripe에 넣는다. dx, dy는 해당 토마토와 인접한 곳(왼쪽, 오른쪽, 앞, 뒤) 네 방향을 확인하기 ..

Brute Force, 구현 1051 숫자 정사각형 www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net 문제 풀기 전 공부할 것 : 구현, 브루트포스 알고리즘 풀이 구체적인 단계 풀이가 필요하신 분은 댓글 남겨주세요. import sys input = sys.stdin.readline n, m = map(int, input().split()) square = [list(map(int, input().rstrip())) for _ in range(n)] s =..

Brute Force 10448 유레카 이론 www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 문제 풀기 전 공부할 것 : 수학, 브루트포스 알고리즘 풀이 구체적인 단계적 풀이가 필요하신 분은 댓글 부탁드립니다. import sys input = sys.stdin.readline t = int(input()) tri = [i*(i+1)//2 for i in range(1, 45)] for _ in range(t): n = int(input()) m =..

DP 10164 격자상의 경로 www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 문제 풀기 전 공부할 것 : 수학, 다이나믹 프로그래밍 풀이 구체적인 단계 풀이가 필요하신 분이 계시다면 댓글 부탁드립니다. n, m, o = map(int, input().split()) dp = [[0 for _ in range(m)] for _ in range(n)] if o == 0: for i in range(n): for j in r..

1013 Contact www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 문제 풀기 전 공부할 것 : 구현 풀이 구체적인 단계 풀이 내용이 필요하신 분이 계시다면 댓글 남겨주세요. def solve(idx, node , wave): if node == -1: print('NO') return if idx == len(wave) and (node == 5 or node == 6 or node == 7): print('YES') return if idx..

조합 1010 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 풀기 전 공부할 것 : 수학, 다이내믹 프로그래밍, 조합론 풀이 1 다리를 지을 때 겹칠 수 없기 때문에 규칙을 찾아보면 서쪽에 1개, 동쪽에 n개 있을 때 다리는 n개 지을 수 있다. 서쪽의 사이트 개수와 동쪽의 사이트 개수가 똑같다면 다리는 1개 지을 수 있다. 서쪽의 사이트 개수가 n, 동쪽의 사이트 개수가 m이라면 (서쪽에 n개, 동쪽에 m-1개로 지을 수 있..

DP 10844 쉬운 계단 수 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 1 계단 수의 경우 n = 1 일 때는 1 - 9까지 모두 가능하다. n = 2 일 때는 1 뒤에는 0 또는 2가, 2 뒤에는 1 또는 3이, ..., 8 뒤에는 7 또는 9가, 9 뒤에는 8만 올 수 있다. 이런 규칙이 반복되는데 n = 3에서부터 나오는 0 뒤에는 1만 올 수 있다. 규칙을 만들면, 0 뒤에는 1만, 9 뒤에는 8만, 1 - 8 뒤에는 (해당 숫자 - 1) 또는 (해당 숫자 + 1)이 올 수 있다. 위의 규칙을 이용해서 개..