알고리즘

문제 https://www.acmicpc.net/problem/2045 2045번: 마방진 3 by 3 크기의 마방진을 생각하자. 마방진이란 가로, 세로, 대각선 위의 수들의 합이 모두 같은 성질을 가지고 있다. 몇 가지 마방진을 예로 들면 다음과 같다. 생일빵을 맞은 정신을 잃은 동주와 www.acmicpc.net 문제 풀이 지저분하지만 단순 구현.. 코드 import sys input = sys.stdin.readline ''' 마방진 : 가로, 세로, 대각선 위의 수들의 합이 모두 같다 주어진 마방진을 가로, 세로, 대각선 조사하여 합이 되는 수를 구함 마방진을 계속 가로, 세로, 대각선으로 탐색하며 0을 지움. 예외 케이스) 0 9 9 9 0 9 9 9 0 ''' MAP = [list(map(in..

문제 https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 문제 풀이 가장 큰 섬을 찾는 bfs 문제 코드 import sys input = sys.stdin.readline import collections N, M = map(int,input().split()) MAP = [list(map(int,input().split())) for _ in range(N)] T = int(input().strip()) def bfs(visited, i, j):..

문제 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제 풀이 0인 부분만 잘 세팅해주면 되는 bfs 문제 코드 import sys input = sys.stdin.readline import collections N, M = map(int,input().split()) MAP = [] res = [[-1 for _ in range(M)] for _ in range(N)] for i in range..

문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 문제 풀이 가장 큰 섬을 찾는 bfs 문제 코드 import sys input = sys.stdin.readline import collections N, M, K = map(int, input().split()) MAP = [[0 for _ in range(M)] for _ in range(N)] for i in range(K): r, c = map..

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 풀이 dp 코드 import sys input = sys.stdin.readline T = int(input().strip()) p = [1,1, 1, 2, 2, 3, 4, 5, 7, 9] while len(p)

문제 https://www.acmicpc.net/problem/12099 12099번: 점심메뉴 Q개의 줄에 줄마다 각 날의 영우와 승관이가 둘 다 좋아하는 메뉴의 수, 즉 u ≤ a ≤ v 이고, x ≤ b ≤ y 인 메뉴의 수를 출력한다 www.acmicpc.net 문제 풀이 매운맛 범위를 이분탐색해서 한번 범위를 좁혀주고, 단맛의 범위를 이분탐색으로 찾기 코드 import sys input = sys.stdin.readline import bisect N, Q = map(int,(input().split())) menu = [list(map(int,input().split())) for _ in range(N)] menu.sort() spicy = list(zip(*menu))[0] sweet = ..

문제 https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹 코드 import sys input = sys.stdin.readline N, M = map(int,input().split()) LIST = sorted(list(set(map(int,input().split())))) total = [] def back(): if len(total) == M: print(*total) return for i in range(len(..

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 dp, 세번 연속으로 1칸씩 이동하는 경우는 없어야 하므로, dp[i]가 두번째 1칸씩(stairs[i-1] + stairs[i-2]) 이동이라면 dp[i-3]을 더해줘서 무조건 불연속하게 만들기 코드 import sys input = sys.stdin.readline N = int(input().strip()) stairs = [int(input().strip()) for _ in range..