알고리즘

풀이 bfs로 풀이함 문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 코드 import sys input = sys.stdin.readline move = {(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1)} def bfs(MAP, x, y): q = [(x,y)] MAP[x][y] = -1 while q: x,y = q.pop(0) for tx, ty in move: nx ..

풀이 위 예시처럼, x좌표에서 갈 수 있는 모든 y 중 k의 배수가 되는 것만 구하여 total에 더해주는 식으로 풀이 문제 https://school.programmers.co.kr/learn/courses/30/lessons/140107 코드 def solution(k, d): total = 0 for i in range(0,d+1,k): # 이 x좌표에서 될 수 있는 점의 갯수 total += (int((d**2 - i**2)**0.5) // k + 1) return total

섬의 크기 찾는 문제의 응용, bfs와 공용 visited 배열을 이용해 풀이함. bfs 개념) https://cccaaa.tistory.com/22 넓이우선탐색(bfs) 동작과정 "시작점 (0, 0) 도착점 (1, 2)일 때, 2차원 배열 (3X3)에서 시작점으로부터 도착점까지의 최단거리를 찾아라"는 문제를 푸는 과정입니다. 우선 2차원 배열과 queue를 선언합니다. 본인이 설정해 둔 move cccaaa.tistory.com 문제) https://school.programmers.co.kr/learn/courses/30/lessons/154540 코드) import collections def bfs(x,y,maps,visited): moves = {(-1,0),(0,1),(1,0),(0,-1)} ..

현 상태에서 녹을 수 있는 빙하를 받아서 한 번에 녹이기 -> 섬 갯수 찾기(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)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는..