알고리즘 문제풀이/Python179 [프로그래머스] 괄호 변환 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 주어진 문자열을 계속하여 분할하면서 재귀적 호출이 필요하여 함수를 만들어 접근하였습니다. 2) 알고리즘 재귀 구현 3) 풀이 코드 사용 언어 - Python def solution(p): # 올바른 괄호 문자열인지 판별 def is_right(s): stack = [] # 괄호를 쌓아놓 리스트 for c in s: if c == '(': # 현재 괄호가 여는 괄호라면 stack.append('(') # 리스트에 저장 elif not stack: # 닫는 괄호인데, 이전에 여는 괄호가 없었다면 return False # 올바른 괄호가 아님 elif stack[-1] == '(': # 현재 괄호가 닫는 괄호인데, 바로 이전 괄호가 여는 괄호였으면 stac.. 2022. 3. 10. [백준] 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. [프로그래머스] 기둥과 보 설치 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 2차원 배열을 생성하여 구조물을 설치하려 하였습니다. 그리하여 설치 또는 제거시 구조물들이 모든 조건에 해당하는지 확인하려 하였으나, 조건이 너무 까다로워 어려움을 겪었습니다. 조금 더 간단한 방법을 생각하여 집합을 이용하여 설치한 구조물들만 반복하며 조건을 확인하도록 하였습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python def solution(n, build_frame): built = set() def is_right(): for b in built: # 모든 구조물 탐색 x, y, a = b # x, y 좌표, a-0: 기둥, 1: 보 if not a: # 현재 구조물이 기둥이라면 if y and (x, y-1, 0).. 2022. 3. 7. [프로그래머스] n진수 게임 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 튜브가 몇번째 순서일때마다 말을 해야하는지 순서를 구해주었습니다. 숫자들을 n진수로 변화하여 사람들이 외칠 한자리씩 나누어 리스트에 저장하였습니다. 2) 풀이 코드 사용 언어 - Python from collections import deque def solution(n, t, m, p): # 변경해야할 진법, 구해야할 정답의 개수, 게임 참여 인원, 튜브의 순서 answer = [] # 정답 리스트 turns = [] # 튜브가 말해야할 순서 converted = ['0'] # 변경된 진법이 한자리씩 저장되는 리스트 def convert(num): # 변환 함수 result = deque() while num > 0: # 0보다 크다면 if num%.. 2022. 3. 6. [프로그래머스] 메뉴 리뉴얼 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 손님들이 주문한 2번 이상 주문한 메뉴들을 조합으로 만들어 풀어야 했으므로, 손님에게 주문받은 주문들을 이용하여 조합을 구하여 가장 많은 선택을 받은 조합들을 구했습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python from itertools import combinations def solution(orders, course): answer = [] # 정답 리스트 li_orders = [] # 손님들이 주문한 메뉴들이 문자열로 들어와서, 메뉴 하나씩 나누어 하나의 리스트에 담음 combs = set() # 나올 수 있는 메뉴 조합들 max_cnt = [0] * (max(course)+1) # 메뉴 개수별로 나올수 있는 조합들 중.. 2022. 3. 5. [백준] 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. [백준] 1939 중량제한 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 섬들이 다리로 이어져 있고, 이 다리는 양방향으로 이루어져 있어 경로와 관련된 문제로 다익스트라를 이용하여 풀이하였습니다. 기존의 최단 경로를 구하는 다익스트라와는 조금 다르게 출발지에서 도착지까지 이동할때 한번에 옮길 수 있는 물품 중량의 최댓값을 구해야하므로, 다른 섬으로 이동시 가능한 최대 무게를 기록하였습니다. 최소힙을 이용하여 구현시 메모리 초과가 발생하였습니다, 그래서 현재 문제에서는 최대 중량만이 필요하므로 최대힙을 이용하여 불필요한 메모리 사용을 방지하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def sol.. 2022. 3. 2. [프로그래머스] k진수에서 소수 개수 구하기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 주어진 숫자를 조건에 맞는 진수로 변환해주었고, 변환된 숫자에서 주어진 조건에 맞는 숫자들을 추출하였습니다. 소수 판별을 위해 에라토스테네스의 체를 이용하였으나 메모리 초과 문제로 각 숫자들을 하나씩 소수 판별을 해주었습니다. 2) 풀이 코드 사용 언어 - Python def solution(n, k): nums = [] # 진수 변환 후 조건에 맞는 숫자 리스트 prime_number = {} # 이미 소수 여부를 확인한 숫자들 answer = 0 # 정답 def trans(num): # 진수로 변환해주는 함수 result = 0 # 변환된 숫자 idx = 0 # 자릿수 while num > 0: result += (num%k) * (10**idx).. 2022. 2. 28. [백준] 12851 숨바꼭질 2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 동생이 위치한 곳으로 도착하는 최단시간을 구해야하므로 다익스트라를 이용하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start): heap = [(0, start)] # 시작 시간, 시작 좌표 cnt = 0 # 동생에게 최단시간에 도착하는 방법 개수 카운트 while heap: node = heapq.heappop(heap) if distance[node[1]] >= node[0]: # 다음 위치로 이동하는게 최소시간인 경우 distance[node[1]] = node[0] # 최소 시간 갱신 if .. 2022. 2. 27. [백준] 2512 예산 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 국가 예산을 초과하지 않으면서 최대한 받을 수 있는 상한액을 구해야하므로 이분 탐색을 이용하였습니다. 이분탐색의 최솟값은 0원, 최댓값은 현재 예산 요청의 최댓값을 지정하였습니다. 2) 알고리즘 이분 탐색 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 예산 요청의 개수 nums = list(map(int, sys.stdin.readline().split())) # 예산 요청 금액들 government = int(sys.stdin.readline()) # 정부의 총 예산 answer = 0 # 최대 상한액 low, high = .. 2022. 2. 26. 이전 1 ··· 6 7 8 9 10 11 12 ··· 15 다음
