전체 글

현 상태에서 녹을 수 있는 빙하를 받아서 한 번에 녹이기 -> 섬 갯수 찾기(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])

S (시작위치) 에서부터 L (레버위치)까지 찾는 bfs 1회, L (레버위치)에서 E (출구위치)까지 찾는 bfs 1회 수행하여 둘 중에 하나라도 -1 (탐색불가)인 경우 -1 리턴 bfs 개념) https://cccaaa.tistory.com/22 넓이우선탐색(bfs) 동작과정 "시작점 (0, 0) 도착점 (1, 2)일 때, 2차원 배열 (3X3)에서 시작점으로부터 도착점까지의 최단거리를 찾아라"는 문제를 푸는 과정입니다. 우선 2차원 배열과 queue를 선언합니다. 본인이 설정해 둔 move cccaaa.tistory.com 문제) 코드) import collections def bfs(start_x, start_y, target_x, target_y, MAP): move = {(-1,0),(0,1..

시계 방향 list(map(list, zip(*MYLIST[::-1]))) 반시계 방향 list(map(list, zip(*MYLIST)))[::-1] 전치 행렬 list(zip(*MYLIST))

새로운 사람이 추가되면 생길 수 있는 새로운 팀을 모든 경우의 수를 따져가며 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..