알고리즘 문제풀이/Python179 [백준] 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. [프로그래머스] 여행경로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 항공편을 모두 이용하여 이동 가능한 여행경로를 탐색해야 하므로 DFS 탐색을 이용하였습니다. 2) 알고리즘 DFS 재귀 3) 풀이 코드 사용 언어 - Python def solution(tickets: list): answer = [] # 정답 리스트 def make_linked(tickets: list): # 연결 관계 변수 만드는 함수 linked = {} # 연결 관계 visited = {} # 항공편 이용 여부 for a, b in tickets: linked[a] = linked.get(a, []) + [b] # a -> b 연결 추가 visited[a] = visited.get(a, []) + [0] # 항공편 방문여부 0으로 초기화 for.. 2022. 3. 21. [프로그래머스] 네트워크 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 컴퓨터들을 연결하여 네트워크가 만들어지고, 서로 다른 네트워크가 몇개인지 확인이 필요하므로 서로소 집합 알고리즘을 이용하여 네트워크 개수를 확인하였습니다. 2) 알고리즘 서로소 집합 3) 풀이 코드 사용 언어 - Python def solution(n, computers): network = list(range(n)) # 컴퓨터들 서로간 연결 정보 def union(x, y): # 컴퓨터 두대 연결 network[find(y)] = find(x) # 각 연결된 컴퓨터의 대표 컴퓨터를 연결 def find(x): # 해당 컴퓨터 네트워크의 대표 컴퓨터 검색 if x != network[x]: # 현재 컴퓨터가 대표 컴퓨터가 아니라면 network[x] .. 2022. 3. 20. [백준] 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. [프로그래머스] 삼각 달팽이 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 2차원 배열에서 대각선으로 반을 채운다고 생각하였습니다. 그리하여 가장 왼쪽위의 좌표에서 시작하여 아래, 오른쪽, 왼쪽위 의 세가지 방향으로만 나아갔습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.setrecursionlimit(10000) dr = [1, 0, -1] # 아래, 오른쪽, 왼쪽위 dc = [0, 1, -1] def solution(n): answer = [] # 정답 리스트 pyramid = [[0] * n for _ in range(n)] # 2차원 배열 direction = 0 # 진행 방향, 초기 아래 방향 def make_py.. 2022. 3. 16. [프로그래머스] 구명보트 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 탑승 가능한 인원이 최대 2명이므로, 무게가 가장 작은 사람과 가장 큰 사람이 함께 탐승하게 하는 방법이 최선의 방법입니다. 2) 알고리즘 탐욕법 3) 풀이 코드 사용 언어 - Python from collections import deque def solution(people, limit): answer = 0 q = deque(sorted(people, reverse=True)) # 사람의 무게를 내림차순으로 정렬 while q: # 사람이 남아있으면 answer += 1 # 보트 한개 추가 if len(q) < 2: # 한명만 남았으면, 혼자 사용 q.pop() elif q[0] + q[-1] 2022. 3. 16. [프로그래머스] 캐시 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 문제에서 제시한 LRU 알고리즘을 이용하여 풀이하였습니다. 2) 알고리즘 LRU (Least Recently Used) 3) 풀이 코드 사용 언어 - Python from collections import deque def solution(cacheSize, cities): answer = 0 # 정답 변수 q = deque() # 캐시 공간 if not cacheSize: # 캐시 사이즈가 0인 경우, 입력마다 항상 5초가 소요 됨 return len(cities) * 5 for city in cities: city = str(city).lower() # 대소문자 구분을 안함 if city not in q: # 현재 도시가 캐시 공간에 저장되어 있지.. 2022. 3. 15. [프로그래머스] 양궁대회 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 재귀로 높은 점수부터 시작하여 탐색하였습니다. 각 점수는 이길때는 딱 한발만 더 쏘도록 하였고, 질때는 한발도 쏘지 않도록 하였습니다. 2) 알고리즘 재귀 3) 풀이 코드 사용 언어 - Python def solution(n, info): answer = [] # 점수 받는 정답 리스트 max_difference = 0 # 가장 많이 차이 나는 점수차 def sol(idx, remain, apeach, ryan, ans): # 인덱스, 남은 화살 수, 어피치 점수, 라이언 점수, 점수별 라이언이 쏜 화살 수 nonlocal answer, max_difference if idx > 10 and remain >= 0: # 모두 반복했고, 화살이 남거나 다.. 2022. 3. 14. [백준] 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. 이전 1 ··· 5 6 7 8 9 10 11 ··· 15 다음
