알고리즘/백준 문제풀이

현 상태에서 녹을 수 있는 빙하를 받아서 한 번에 녹이기 -> 섬 갯수 찾기(bfs) 를 반복하여 풀이 문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 코드 import sys input = sys.stdin.readline import collections N, M = map(int,input().split()) MAP = [] for i in range(N): tmp = list(map(int,input().split())) MA..

구현으로 풀었다가 dp로 개선 문제) https://www.acmicpc.net/problem/2775 코드) import sys input = sys.stdin.readline T = int(input().strip()) # dp 만들기 dp = [list(range(15)) for _ in range(15)] for i in range(1,15): for j in range(15): # dp[i][j] = sum(dp[i-1][:j+1]) # 구현 dp[i][j] = dp[i-1][j] + dp[i][j-1] # dp for _ in range(T): k = int(input().strip()) n = int(input().strip()) print(dp[k][n])

새로운 사람이 추가되면 생길 수 있는 새로운 팀을 모든 경우의 수를 따져가며 dp에 max(총점수)를 기록 예를 들어, 10 2 5 7 1 3 4 8 6 9 3 위 테스트 케이스의 경우에는 2, 5 다음 7이 새로 들어왔을 때, 생길 수 있는 새로운 팀은 2, 5 // 7 2 // 5, 7 2,5,7 (한 팀) . . 이런식 그런데 이전 dp에 빨간 글씨 경우는 모두 저장되어 있으므로 새롭게 생길 수 있는 팀의 점수에 가져다 더하면 됨. 모든 경우의 수를 보면서 제일 큰 점수를 가지는 경우를 dp에 저장. 문제) https://www.acmicpc.net/problem/2229 2229번: 조 짜기 알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는..

dictionary를 이용해 단방향 링크드리스트 구조로 구현. 부모의 자식은 여러 명일 수도 있지만, 자식의 부모는 무조건 1명이라는 점을 이용해 순회함. 문제) https://www.acmicpc.net/problem/25601 코드) import sys input = sys.stdin.readline N = int(input().strip()) tree = dict() for i in range(N-1): A, B = input().split() # A: 자식, B: 부모 tree[A] = B # 부모는 언제나 1명 A, B = input().split() def check(tree, child, target_parent): parent = child while True: try: parent = t..

시키는 대로 하면 되는 구현문제, 조건 분기하는걸 다 정리해 두고 시작해야 중간에 꼬이지 않음. check함수로 한 줄에 대해서 올라가는 경사로, 내려가는 경사로를 각각 한 번씩 서치함. 두 경우를 서치하고 나면 지나갈 수 있는 길이라고 판별. default 상태는 True(지나갈 수 있는 길)로 두고 지나갈 수 없는 경우를 모두 탐색하여 그때마다 False 리턴. 문제) https://www.acmicpc.net/problem/14890 코드) import sys input = sys.stdin.readline N, L = map(int,input().split()) MAP = [list(map(int,input().split())) for _ in range(N)] rotated_MAP = [list..

bfs로 풀이함 문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 코드 import sys input = sys.stdin.readline import collections N, M = map(int,input().split()) MAP = [list(input()) for _ in range(M)] move = {(-1,0),(0,1),(1,0),(0,-1)} def bfs(x,y,MAP,color): q = co..

전형적인 지도에서 가장 큰 섬을 찾는 문제. bfs 풀이함. 문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 코드 import sys input = sys.stdin.readline import collections n,m = map(int,input().split()) MAP = [list(map(int,input().split())) for _ in range(n)] move = {(-1,0),(0,1),(1,0),(0,-1)} def bf..

적록 색약일 때와 아닐 때의 MAP을 따로 생성하여 각각 bfs 돌려줌. 적록 색약일 경우에 R, G를 다 R로 저장해서 풀이함. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 import sys input = sys.stdin.readline from collections import deque N = int(input().strip()) MAP = [list(str(input())) for _ in range(N)] MA..