python178 [백준] 2467 용액 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 두 개의 용액들을 서로 비교하여 혼합하였을 경우 특성값이 0에 가까운 용액들을 찾아야 했습니다. 0을 만들기 위해서는 현재 용액에 -1을 곱한 값이 리스트에서 어느 위치에 들어갈 수 있는지 이분 탐색을 이용하여 찾았습니다. 찾은 인덱스 값의 앞뒤 용액들을 모두 현재 용액과 혼합했을때 특성값을 계산하여 0에 가장 가까운 수가 되는 경우를 탐색하였습니다. 2) 알고리즘 이분 탐색 3) 풀이 코드 사용 언어 - Python import sys from bisect import bisect_left sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 용액의 수 num_li = list(map(int,.. 2022. 4. 13. [백준] 2096 내려가기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 행이 아래로 진행이 될때마다 최댓값과 최솟값을 기억하며 내려가야 하므로 다이나믹 프로그래밍을 이용하였습니다. 초기에 문제를 접했을때, 주어진 모든 숫자들을 2차원 배열에 저장하였고 최댓값과 최솟값을 저장하는 3차원 배열의 리스트를 생성하였습니다. 그리고 각 행을 진행하면서 행별 최댓값과 최솟값을 저장하였습니다. 그러나 N의 범위가 최대 100,000으로 최악의 경우에 메모리 초과가 발생하였습니다. 그로 인하여 3차원 배열 DP를 3*2 크기의 2차원 배열로 변경하였습니다. 또한, 주어진 모든 숫자를 입력받은 후 계산을 진행하지 않고, 숫자가 주어질때 바로바로 연산을 진행하여 숫자들을 저장하는 변수를 사용하지 않게 진행하여 문제를 해결하였습니다. 2) .. 2022. 4. 12. [백준] 1918 후위 표기식 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 변환된 정답을 저장하는 스택과 연산자와 괄호를 저장하는 스택을 생성하여 관리하였습니다. 알파벳은 바로 정답 스택에 쌓았고, 괄호와 연산자의 우선순위에 따라 정답에 추가하였습니다. 2) 알고리즘 자료구조 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') infix = sys.stdin.readline().rstrip() # 중위 표현법 answer = [] # 후위 표현법으로 변형된 정답 op = [] # 괄호 및 연산자가 들어갈 스택 for c in infix: # 앞에서부터 반복 if c.isalpha(): # 알파벳이라면 바로 정답에 넣기 answer.append(c) elif c .. 2022. 4. 11. [백준] 17070 파이프 옮기기 1 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 처음에 문제를 접하고 간단하게 BFS 방식으로 탐색을 시도하였습니다. 그러나 모든 경우를 탐색하여야 하므로 시간 초과가 발생하였습니다. 그 이후 각 좌표에 올 수 있는 경우의 수를 구하는 방식으로 풀이하였습니다. 2) 알고리즘 다이나믹 프로그래밍 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 가로, 세로 길이 home = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 집의 상태 0-빈칸, 1-벽 dp = [[[0] * (N+1) for _ in range.. 2022. 4. 10. [백준] 1202 보석 도둑 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 가방에 담을 수 있는 모든 보석들 중 가장 가치가 높은것을 담으면 최대 가치를 얻을 수 있습니다. 그리디 방식으로 접근하여 풀이했습니다. 2) 알고리즘 그리디 3) 풀이 코드 사용 언어 - Python import sys import heapq from collections import deque sys.stdin = open('input.txt') N, K = map(int, sys.stdin.readline().split()) # 보석의 개수, 가방의 개수 gems = deque(sorted([list(map(int, sys.stdin.readline().split())) for _ in range(N)], key=lambda x: x[0])) #.. 2022. 4. 9. [백준] 2749 피보나치 수 3 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 피보나치 수열을 구하고 특정 수로 나누었을때 나머지의 값을 구하는 문제였습니다. 단순히 메모이제이션을 이용하여 풀이를 하려 하였으나, 입력 값이 최대 1,000,000,000,000,000,000 으로 매우 큰 수이므로 메모이제이션을 이용하더라도 시간 초과가 우려되었습니다. 학습 진행 중 피사노 주기 라는 내용을 학습하게 되어 피사노 주기를 이용하여 풀이했습니다. 2) 알고리즘 수학 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) period = 15 * 10 ** 5 # 나누는 수가 10^k 일때, 나머지는 주기를 이루는데 주기는.. 2022. 4. 2. [백준] 1987 알파벳 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 상하좌우칸을 이동하면서 지나온 정보들을 집합으로 저장하여 기록 및 중복 여부를 확인하였습니다. 시간초과를 고려하여 집합을 이용하여 알파벳을 기록하였으나 시간초과가 발생하였습니다. 이후 리스트에서 좌표들의 정보를 가지고 탐색하던것을 중복을 줄이기 위하여 집합을 이용하였습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') dr = [-1, 0, 1, 0] # 위 오른쪽 아래 왼쪽 dc = [0, 1, 0, -1] def solution(): global answer s = set([(0, 0, board[0][0])]) # 좌표, 지나온 좌표들의 알파벳 기록 (시.. 2022. 3. 31. [백준] 10800 컬러볼 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 공의 색이 최대 200,000 개가 나올 수 있으므로 단순 이중 반복문으로 풀이시 시간초과 문제가 발생할것을 예상하였습니다. 1차적으로 공의 크기별로 정렬을 하였고 크기가 작은 순서대로 확인하며 누적합을 쌓는 방법을 이용하였습니다. 그러나 사이즈가 같은 공이 여러개 나오는 경우, 다음 순서 진행시 누적합에 같은 사이즈의 합도 포함이 되는 오류가 발생하였습니다. 이러한 문제 해결을 위해 같은 사이즈 발견시 처리해주는 코드를 작성하였습니다. 2) 알고리즘 누적합 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 공의 개수 infos .. 2022. 3. 30. [백준] 9370 미확인 도착지 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최단거리로 이동을 하기 때문에 다익스트라를 이용하여 풀이했습니다. 최초 풀이시 각 노드로 이동하는 최단 경로를 저장하였습니다. 메모리 초과 문제가 발생하여, 출발지, g, h 노드에서 출발하는 최단 거리를 모두 구해주었습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start): heap = [(0, start)] distance = [-1] * (n+1) # 반환할 최단 거리 while heap: node = heapq.heappop(heap) if distance[node[1]] == -1: # 도착하.. 2022. 3. 29. [백준] 15900 나무 탈출 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 재귀를 이용하여 모든 리프 노드에서 루트 노드까지의 거리를 구한 후, 모두 더한 값을 구하였습니다. 모든 리프 노드의 더해진 값이 짝수인지 홀수인지 여부에 따라 이길 수 있는지 없는지 구하였습니다. 2) 알고리즘 재귀 트리 3) 풀이 코드 사용 언어 - Python import sys sys.setrecursionlimit(1000000) sys.stdin = open('input.txt') def solution(node): global need_move is_leaf = True # 현재 노드가 리프노드인지 구분을 위함 for next in linked[node]: if not distance[next]: # 방문하지 않은 노드들이라면 distan.. 2022. 3. 28. [프로그래머스] 등굣길 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 2차원 배열의 각 칸별로 도착할 수 있는 경우의 수를 저장하였습니다. 2차원 배열의 누적합을 구하는 방법과 유사하게 접근하였습니다. 2) 알고리즘 DP 누적합 3) 풀이 코드 사용 언어 - Python def solution(m, n, puddles): dp = [[0] * (m+1) for _ in range(n+1)] # 2차원 배열 생성, 누적합과 유사하여 가장 왼쪽 열과 가장 위의 행을 0으로 모두 채움 dp[0][1] = 1 # 출발지 (1, 1) 에 도착 가능한 경우의 수를 1개로 만들기 위함 for i in range(1, n+1): # 2차원 배열 반복 for j in range(1, m+1): if [j ,i] in puddles: #.. 2022. 3. 27. [프로그래머스] 정수삼각형 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 삼각형의 각 층별로 나올 수 있는 최댓값들을 기록하였습니다. 다음 층을 계산할때 이전층의 최댓값에서 현재 더할 수 있는 값들을 더하고 더 큰 값들을 저장하였습니다. 2) 알고리즘 DP 3) 풀이 코드 사용 언어 - Python def solution(triangle): N = len(triangle) # 삼각형의 높이 dp = [] # 삼각형의 높이별 나올 수 있는 값 dp.append(triangle[0]) # 가장 위에층 설정 n = 1 # 현재 높이 while n < N: # 현재 높이가 삼각형의 높이 보다 작으면 반복 tmp = [] # 현재 층의 정답 경우의 수 tmp.append(dp[-1][0] + triangle[n][0]) # 현재 층.. 2022. 3. 26. 이전 1 ··· 4 5 6 7 8 9 10 ··· 15 다음
