백준136 [백준] 1197 최소 스패닝 트리 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최소 스패닝 트리 문제로 크루스칼 알고리즘으로 접근했습니다. 2) 알고리즘 크루스칼 3) 풀이 코드 사용 언어 - Python def find_set(x): # 정점 x 의 최상단 정점을 찾음 if x != s[x]: s[x] = find_set(s[x]) return s[x] def union(x, y): # 두개의 집합을 서로 합침 s[find_set(y)] = find_set(x) def kruskal(): # 크루스칼 알고리즘 global answer edge_cnt, idx = 0, 0 # 모두 연결이 되었는지 확인을 위한 변수, 간선 집합의 인덱스 번호 while edge_cnt != V-1: # 정점-1 개 만큼 연결되어 있지 않으면 x .. 2022. 2. 2. [백준] 15686 치킨 배달 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 치킨집을 기준으로 하여 각 치킨집에서 집까지 치킨 거리를 모두 구하여 2차원 배열로 저장하도록 했습니다. 치킨집을 최대한 M개 모두 사용하는것이 도시의 치킨 거리를 가장 작게 만들 수 있으므로, M개 모두 선택했을때의 조합을 구하였습니다. 미리 구해둔 2차원 배열을 이용해, 각 집과 치킨집의 최소 거리를 찾아서 도시의 치킨거리의 최솟값을 구했습니다. 2) 알고리즘 브루트포스 3) 풀이 코드 사용 언어 - Python import sys from itertools import combinations sys.stdin = open('input.txt') N, M = map(int, sys.stdin.readline().split()) # 도시의 크기, 최.. 2022. 1. 31. [백준] 3190 뱀 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기 뱀의 몸을 좌표값으로 저장하여 DFS 탐색을 이용하는 방식으로 접근하였습니다. 그러나 뱀이 방향전환을 하면 얼굴만 방향 전환이 아닌 몸 전체가 방향을 전환하여 원치않는 결과가 나타났습니다. 뱀의 몸은 움직이지 않고, 머리와 꼬리 부분만 삭제와 추가를 컨트롤 하면 된다는 사실을 파악 후 큐를 이용한 구현으로 접근하였습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(): snake = deque([(1, 1)]) # 뱀의 몸이 있는 위치 direction = 1 # 뱀의 진행 방향.. 2022. 1. 30. [백준] 18222 투에-모스 문자열 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 과정이 반복될수록 2의 제곱만큼 자릿수가 증가하는 규칙이 있어 초기 몇번째 값을 토글하여야 하는지 찾는 방식으로 접근했습니다. 2) 알고리즘 분할정복 3) 풀이 코드 사용 언어 - Python import sys import math sys.stdin = open('input.txt') K = int(sys.stdin.readline()) # 찾아야하는 자릿수 patterns = '0110' # 가장 앞의 4자리 sign = 0 # 반전 여부 while K >= 4: # 4자리 이상이면 반복 if sign: # 반전 여부 토글 sign -= 1 else: sign += 1 n = int(math.log2(K)) # 현재 자릿수보다 작거나 같은 2의 제.. 2022. 1. 29. [백준] 1963 소수 경로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 에라토스테네스의 체를 이용하여 소수를 구하였고, 여러 테스트 케이스마다 소수를 구하지 않도록 전역에서 필요한 소수들을 모두 구한 후 테스트케이스의 정답을 찾아나갔습니다. 각 자릿수 변경을 BFS 탐색을 이용하였는데, 반복문을 이용하여 각 자릿수를 변경해서 탐색을 진행하였습니다. 2) 알고리즘 에라토스테네스의 체 BFS 3) 풀이 코드 사용 언어 - Python import sys import math from collections import deque sys.stdin = open('input.txt') def solution(n): q = deque([n]) visited[n] = 0 # 시작 숫자는 0번 바꿔서 돌아오므로 0으로 지정 while .. 2022. 1. 28. [백준] 9935 문자열 폭발 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 제한 시간을 고려하여 문자열과 폭발 문자열을 비교하여 스택에 쌓다가 첫 문자열이 일치하면 그 이후 문자들을 비교하여 조건을 처리하는 방식으로 진행하였습니다. 그러나 인덱스 관리의 어려움을 느껴 스택에 문자들을 쌓다가, 마지막 문자가 일치하면 안에 들어온 문자들과 비교하여 모두 일치하면 pop을 시키는 방식으로 접근하였습니다. 2) 알고리즘 스택 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') word = list(sys.stdin.readline().strip()) # 주어진 문자열 bomb = list(sys.stdin.readline().strip()) # 폭발 문자열 answer.. 2022. 1. 27. [백준] 2110 공유기 설치 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 문제에서 주어지는 공유기의 개수를 만족시키며 공유기간의 사이 거리를 구해야 하므로 이분 탐색을 이용하였습니다. 2) 알고리즘 이분탐색 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N, C = map(int, sys.stdin.readline().split()) # 집의 개수, 공유기의 개수 home = sorted([int(sys.stdin.readline()) for _ in range(N)]) # 집의 위치 answer = 0 l, r = 1, home[-1] - home[0] # 공유기간의 거리 최솟값과 최댓값 while l = gap: # 이전에 설치한 집과 현재 집의 거리.. 2022. 1. 26. [백준] 2665 미로만들기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최초 접근시 DFS 이용하여 접근하였으나 배열의 크기로 인하여 시간초과를 예상했습니다. 그래서 BFS 를 사용하여 접근하였습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(): q = deque([(0, 0)]) # 시작 visited[0][0] = 0 # 시작 방문처리 while q: node = q.popleft() for k in range(4): r = node[0] + dr[k] # 새로운 좌표 c = node[1] + dc[k] if 0 2022. 1. 23. [백준] 14621 나만 안되는 연애 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 각 노드들이 남초 대학교와 여초 대학교들끼리만 연결이 되어야 하므로, 링크를 저장하는 과정에서 서로 반대되는 경우에만 경로를 저장하였습니다. 2) 알고리즘 프림 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start): heap = [(0, start)] # 시작 거리, 시작 노드 while heap: node = heapq.heappop(heap) if not visited[node[1]]: # 아직 방문하지 않은 학교인 경우 visited[node[1]] = 1 # 방문 처리 distance[node[1]] = node[0] # 최.. 2022. 1. 22. [백준] 9205 맥주 마시면서 걸어가기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 특정 지점(출발점과 이동이 가능한 편의점)에서 맥주 20병을 가지고 최대로 이동할 수 있는 범위 내에 도착지나 편의점이 있는지 여부를 탐색하였습니다. 2) 알고리즘 너비 우선 탐색 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') T = int(sys.stdin.readline()) # 테스트케이스 개수 for _ in range(T): N = int(sys.stdin.readline()) # 편의점의 개수 start = list(map(int, sys.stdin.readline().split())) # 집의 좌표 coordinate.. 2022. 1. 21. [백준] 5052 전화번호 목록 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 번호가 짧은 것을 기준으로 하여 긴 문자열의 접두사에 포함되는지 파악하기 위해서 정렬을 시도하였습니다. 정렬은 앞글자가 일치하는 순서대로, 길이 순서대로 정렬하였습니다. 짧은 글자를 순서대로 기준으로 하여 가장 앞자리를 비교하며 일치하는지 여부를 판별하였습니다. 만약 현재 비교한 자리의 숫자가 더 큰숫자가 있다면 기준의 뒤의 다른 문자들은 모두 일치하지 않으므로 반복문을 종료하고 기준 숫자를 변경해주었습니다. 2) 알고리즘 정렬 문자열 비교 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') T = int(sys.stdin.readline()) # 테스트 케이스 개수 for _ in ra.. 2022. 1. 20. [백준] 1707 이분 그래프 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 이분 그래프를 찾아야하므로 DFS 탐색을 통해 노드들을 탐색하였고, 인접한 노드마다 방문처리를 다르게 하여 이분그래프 여부를 판별했습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(start): # DFS 탐색 stack = [start] visited[start] = 1 # 첫 시작점 방문처리 while stack: node = stack.pop() for i in linked[node]: # 인접한 노드 탐색 if visited[i] == visited[node]: # 인접한 곳이 서로 같은 숫자인 경우, 이분 그래프가 성립하지 .. 2022. 1. 19. 이전 1 ··· 6 7 8 9 10 11 12 다음
