전체 보기232 [백준] 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. [프로그래머스] 입국심사 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 시뮬레이션으로 풀이를 진행하려 하였으나, 입력 조건의 범위가 너무 크기에 시간초과 발생을 예상했습니다. 많은 인원의 연산을 위해 이분탐색을 이용하였습니다. 2) 알고리즘 이분탐색 3) 풀이 코드 사용 언어 - Python def solution(n, times): times.sort() # 이분 탐색을 위한 정렬 answer = 0 l, r = 0, times[-1] * n # 모든 심사관의 소요되는 최소 시간, 최대 시간 while l = n: # 현재 심사관까지 심사했는데, 모든 인원 심사가 가능한 경우 answer = mid # 현재 전체 소요 시간 저장 r = mid - 1 # 더 짧은 시간으로 가능한지 탐색을 위한 설정 break else: .. 2022. 1. 25. [프로그래머스] 게임 맵 최단거리 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최단거리로 목표지점에 이동하고, 최단 거리를 알아야하므로 BFS 로 접근하였습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python from collections import deque dr = [-1, 0, 1, 0] # 상 우 하 좌 dc = [0, 1, 0, -1] def solution(maps): N = len(maps) # 세로 M = len(maps[0]) # 가로 visited = [[0] * M for _ in range(N)] # 방문 여부 def solution(): # 내부함수, BFS 탐색 q = deque([(0, 0)]) visited[0][0] = 1 # 시작점 방문 처리 while q: node = q.p.. 2022. 1. 24. [백준] 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. 이전 1 ··· 11 12 13 14 15 16 17 ··· 20 다음
