알고리즘 문제풀이210 [백준] 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. [백준] 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. [백준] 22944 죽음의 비 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 상하좌우를 이동하면서 우산 내구도와 남은 체력을 확인하며 한칸씩 이동하도록 진행하였습니다. 초기에 DFS를 이용하고, 몇몇 조건을 주어 백트래킹을 시도하였으나 배열의 크기가 최대 500 * 500 이고, 새로운 우산 내구도 적용시 방문했던 위치를 다시 방문이 가능해 더 많은 연산을 하기 때문에 시간초과가 발생했습니다. 이를 해결하기 위해 BFS 탐색으로 변경을 시도하였고, 약간의 메모이제이션을 활용하여 연산의 횟수를 줄이도록 시도하였습니다. 2) 알고리즘 BFS 메모이제이션 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def s.. 2022. 1. 18. [프로그래머스] 튜플 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 원소들이 순서가 랜덤하게 있을 수 있으므로 길이 순서대로 정렬하였습니다. 또한 원소들을 집합으로 구분하여 현재 없는 원소를 쉽게 찾아내도록 사용하였습니다. 2) 풀이 코드 사용 언어 - Python def solution(s): answer = [] li = sorted(s[2:-2].split('},{'), key=lambda x: len(x)) # 양 끝의 중괄호 삭제, '},{' 기준으로 원소들 구분 후 원소의 개수순으로 정렬 for e in li: # 각 원소들 반복 num = set(e.split(',')) - set(answer) # 정답에 있는 현재 길이의 원소와 정답 원소들의 차집합을 구함 answer.append(num.pop()) #.. 2022. 1. 17. [프로그래머스] 타겟넘버 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 특정 자릿수의 숫자가 더하기 아니면 빼기를 진행하여야 하므로 각 자리마다 두가지의 경우가 생깁니다. 첫번째 반복문에서 모든 경우의 수를 반복하고, 두번째 반복문에서 각 자릿수마다 확인하여 더하기와 빼기를 진행합니다. 2) 알고리즘 완전탐색 3) 풀이 코드 사용 언어 - Python def solution(numbers, target): answer = 0 # 정답의 개수 for i in range(1 2022. 1. 16. 이전 1 ··· 10 11 12 13 14 15 16 ··· 18 다음
