alpyrithm_알파이리즘

DP 1463 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 n을 Scanner를 이용하여 입력받는다. 배열의 크기가 n+1인(인덱스가 0 ~ n 까지) 배열을 선언한다. 1 - n 까지 반복문을 돌면서 i가 1, 2, 3 일 때는 해당 결괏값을 배열에 넣어주고 이외의 경우는 연산에 따라 3으로 나눠질 때, 2로 나눠질 때, 1을 뺄 때 각각의 경우에 해당하는 연산 횟수에 1을 더한 값 중 최솟값을 구하여 해당 배열에 값을 넣는다. 배열의 각 값은 해당 인덱스를 1로 만드는데 필요한 연산 횟..

너비 우선 탐색 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개로 지을 수 있..