알고리즘 문제풀이210 [프로그래머스] 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) 문제 이해 및 접근 입력으로 주어진 시간을 분으로 수정하여 딕셔너리에서 입차와 출차를 관리하였고, 누적 시간을 저장하였습니다. 마지막에 이 누적시간에 따라 요금을 계산하였습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python from math import ceil def solution(fees, records): base_time, base_cost, per_time, per_cost = fees # 기본 시간(분), 기본 요금(원), 단위 시간(분), 단위 요금(원) answer = [] # 정답 리스트 parking = {} # 주차장에 차량이 있는지 없는지 여부, 키: 차량 번호, 값: 입차 시간 times = {} # 차량별 주차장 이용 누적시.. 2022. 2. 25. [백준] 1300 K번째 수 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 딕셔너리를 이용하여 각 숫자의 값들이 몇개씩 있는지 모두 정의한 후 탐색하려는 인덱스의 값이 어떤 값인지 탐색하였습니다. 그러나 메모리 초과 문제가 발생하였습니다. 이 후 이분탐색을 이용하여 해결하였습니다. 2) 알고리즘 이분탐색 3) 풀이 코드 사용 언어 - Python import sys N = int(sys.stdin.readline()) # 배열의 길이 K = int(sys.stdin.readline()) # 찾으려는 인덱스 번호 answer = 0 # 정답 low, high = 0, K # 정답의 최소 숫자, 최대 숫자 while low = K: # K번째 이후의 숫자라면 high = mid - 1 # 정답으로 작성 answer = m.. 2022. 2. 24. [프로그래머스] 징검다리 건너기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 단순하게 이중반복문을 이용하여 모든 디딤돌을 탐색하는데, 하나의 디딤돌을 기준으로 k개만큼의 디딤돌을 확인하여 몇명이 지나가면 더 지나갈 수 없는지 확인하였습니다. 그러나 이중반복문이기에 시간초과가 발생하였습니다. 시간 초과를 해결하기 위하여 이분탐색을 이용하여 건너는 인원의 수를 구하는 방법으로 접근하였습니다. 2) 알고리즘 이분탐색 3) 풀이 코드 사용 언어 - Python def solution(stones, k): low, high = 0, max(stones) # 건널 수 있는 인원의 최솟값, 최댓값 answer = 0 # 건널 수 있는 인원 while low = k: # k거리 만큼 벌어지면 종료 break else: # 건널 수 있.. 2022. 2. 23. [프로그래머스] 광고 삽입 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 모든 구현을 하는 방식으로 접근하였습니다. 그러나 변수의 범위가 매우 넓어 시간초과가 발생하였습니다. 이후에 시간 단축을 위하여 고민하던 중 시청자가 몇명인지에 따라 결과가 달라지기 때문에 누적합을 이용하여 풀이를 할 수 있다고 생각하여 접근했습니다. 2) 알고리즘 누적합 3) 풀이 코드 사용 언어 - Python def solution(play_time, adv_time, logs): def time_to_seconds(s): # 문자열 시간을 초로 바꾸어 주는 함수 return int(s[:2]) * 3600 + int(s[3:5]) * 60 + int(s[6:8]) play_time_seconds = time_to_seconds(play_.. 2022. 2. 22. 이전 1 ··· 7 8 9 10 11 12 13 ··· 18 다음
