백준136 [백준] 9370 미확인 도착지 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최단거리로 이동을 하기 때문에 다익스트라를 이용하여 풀이했습니다. 최초 풀이시 각 노드로 이동하는 최단 경로를 저장하였습니다. 메모리 초과 문제가 발생하여, 출발지, g, h 노드에서 출발하는 최단 거리를 모두 구해주었습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start): heap = [(0, start)] distance = [-1] * (n+1) # 반환할 최단 거리 while heap: node = heapq.heappop(heap) if distance[node[1]] == -1: # 도착하.. 2022. 3. 29. [백준] 15900 나무 탈출 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 재귀를 이용하여 모든 리프 노드에서 루트 노드까지의 거리를 구한 후, 모두 더한 값을 구하였습니다. 모든 리프 노드의 더해진 값이 짝수인지 홀수인지 여부에 따라 이길 수 있는지 없는지 구하였습니다. 2) 알고리즘 재귀 트리 3) 풀이 코드 사용 언어 - Python import sys sys.setrecursionlimit(1000000) sys.stdin = open('input.txt') def solution(node): global need_move is_leaf = True # 현재 노드가 리프노드인지 구분을 위함 for next in linked[node]: if not distance[next]: # 방문하지 않은 노드들이라면 distan.. 2022. 3. 28. [백준] 2146 다리 만들기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 섬들간에 다리를 놓아야 하므로, 섬들을 구분하기 위해서 DFS 탐색을 이용하여 섬들에 서로 다른 번호를 매겼습니다. 섬마다 경계선 부분의 좌표들을 모두 구하여 각 섬들의 경계선끼리 거리를 구해주었습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') dr = [-1, 0, 1, 0] # 위 오른쪽 아래 왼쪽 dc = [0, 1, 0, -1] def numbering(y, x, num): # 섬마다 숫자를 매김 q = deque([(y, x)]) board[y][x] = num # 현재 위치부터 섬 번호를 매김.. 2022. 3. 24. [백준] 5014 스타트링크 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 목표하는 층을 이동하기 위해 최소한으로 누르는 버튼 횟수를 구해야하여 BFS 탐색을 이용하였습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def bfs(start): # BFS 탐색 q = deque([start]) visited[start] = 0 # 시작 층은 0번 눌러서 도착하므로 0으로 초기화 while q: floor = q.popleft() n1, n2 = floor + U, floor - D # 올라가는 층, 내려가는 층 if n1 2022. 3. 23. [백준] 13460 구슬탈출 2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 구슬 두개를 이용하여 상하좌우를 10번 이하로 움직여 공 하나만 구멍으로 빼내야 했습니다. 보드판을 상하좌우로 기울이는 횟수가 10번이 되어야 하므로 재귀를 이용한 탐색으로 구현하였습니다. 2) 알고리즘 구현 재귀 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') dr = [-1, 0, 1, 0] # 위 오른쪽 아래 왼쪽 dc = [0, 1, 0, -1] def solution(ans, blue, red, direction): # 기울인 횟수, 파란공의 좌표, 빨간공 좌표, 기울인 방향 global answer if ans > 10: # 10번 넘게 기울인 경우 탐색 중지 return .. 2022. 3. 22. [백준] 11052 카드 구매하기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 필요한 카드의 개수가 1개부터 최고의 금액을 구하며, N개일때까지 구하였습니다. 2) 알고리즘 다이나믹 프로그래밍 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 필요한 카드의 개수 price = list(map(int, sys.stdin.readline().split())) # 입력으로 주어지는 카드팩별 금액 dp = [0] * (N+1) # 카드의 개수별 최고 금액 for i in range(1, N+1): # 카드 N개까지 인덱스 반복 cases = {price[i-1]} # 카드 i개가 들어있는 팩을 하나 샀을 경우 fo.. 2022. 3. 19. [백준] 2644 촌수계산 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 두 노드간의 거리를 구해야 하므로 BFS를 이용하여 풀이했습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(): q = deque([p1]) visited[p1] = 0 # 본인 촌수는 0부터 시작 while q: node = q.popleft() for e in linked[node]: # 연결된 다음 노드 if visited[e] == -1: visited[e] = visited[node] + 1 # 촌수 증가 q.append(e) N = int(sys.stdin.readlin.. 2022. 3. 13. [백준] 1051 숫자 정사각형 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 가장 큰 정사각형을 찾아야하므로 초기에 변의 길이를 가장 길게 시작하여 줄여가며 정답을 찾았습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N, M = map(int, sys.stdin.readline().split()) # 행, 열 square = [list(sys.stdin.readline().rstrip()) for _ in range(N)] # 입력으로 받은 사각형 answer = min(N, M) # 정사각형이므로 열과 행 중 짧은 변의 길이를 구함 end = False # 정답을 찾았는지 유무 while not end: for i in range.. 2022. 3. 11. [백준] 1774 우주신과의 교감 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최소신장트리에 관한 문제로 프림 알고리즘을 이용하여 풀이했습니다. 이미 연결되어 있는 노드들 간에는 가중치를 0으로 두어 경로를 추가해주었습니다. 2) 알고리즘 프림 알고리즘 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start): global answer heap = [(0, start)] while heap: node = heapq.heappop(heap) if not visited[node[1]]: # 도착 노드를 아직 연결하지 않았으면 visited[node[1]] = 1 # 연결 처리 answer += node[0] # 가중.. 2022. 3. 9. [백준] 12015 가장 긴 증가하는 부분 수열 2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 2중 반복문을 이용하여 풀이하였으나, 시간 초과 문제가 발생하였습니다. 시간 단축을 위해 고민하던중 '최장 증가 부분 수열 (LIS)' 를 새롭게 학습하여 해결하였습니다. 2) 알고리즘 최장 증가 부분 수열 (LIS) 3) 풀이 코드 사용 언어 - Python import sys import bisect sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 수열의 길이 A = list(map(int, sys.stdin.readline().split())) # 수열 lis = [0] # 최장 증가 부분 수열(LIS) for num in A: # 수열 하나씩 확인 if num > lis[-1.. 2022. 3. 8. [백준] 1002 터렛 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 두 개의 점을 기준으로 하여 반지름이 주어졌을때, 두 개의 원이 그어지면 그 원이 접하는 점의 개수를 구해야 했습니다. 2) 알고리즘 수학 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') T = int(sys.stdin.readline()) # 테스트 케이스 개수 for _ in range(T): x1, y1, r1, x2, y2, r2 = map(int, sys.stdin.readline().split()) # 좌표와 반지름 distance = ((x1-x2)**2 + (y1-y2)**2)**0.5 # 두 점간의 거리 if x1 == x2 and y1 == y2 and r1 == r.. 2022. 3. 4. [백준] 2268 수들의 합 7 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 특정 구간의 합을 여러번 구해야하고, 특정 인덱스 값 변경이 필요하여 세그먼트 트리를 구성하여 구현하였습니다. 2) 알고리즘 세그먼트 트리 3) 풀이 코드 사용 언어 - Python import sys from math import log2, ceil sys.stdin = open('input.txt') def make_linked(node, left, right): # 배열의 숫자가 세그먼트 트리의 어느 인덱스에 저장되었는지 알기 위함 if left >= right: linked[left] = node # 리프노드인 경우 배열에 저장 return make_linked(node*2, left, (left+right)//2) # 왼쪽 노드들 탐색 mak.. 2022. 3. 3. 이전 1 ··· 4 5 6 7 8 9 10 ··· 12 다음
