백준136 [백준] 12852 1로 만들기 2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 현재 숫자에서 조건의 연산을 진행하며 나아갈때 이전의 연산들을 기록하여야 했으므로 딕셔너리를 이용하여 기록하였습니다. 또한 메모리 확보를 위하여 이전에 사용한 기록들은 불필요하므로 지속적으로 관리하지 않고 제거하였습니다. 2) 알고리즘 다이나믹 프로그래밍 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 찾으려는 수 dp = {0 : [], 1: [1]} # 각 숫자별 연산 순서 (최소만 기록) for idx in range(1, N+1): # 찾으려는 수까지 반복 if idx * 3 len(dp[idx]) + 1) or not .. 2022. 4. 19. [백준] 1005 ACM Craft 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 문제를 접하고 도착하는 노드에서 거꾸로 BFS 탐색을 이용해 같은 거리만큼 떨어진 노드들의 시간들 중 가장 오래 걸리는 시간을 기록하여 구하려 하였습니다. 그러나 시간초과 문제가 발생하였고, 원인을 정확히 파악하지 못하였으나 거꾸로 진행하는 방식은 값을 구하는 과정에서 오류가 발생할거 같다는 생각이 들었습니다. (건물이 순서대로 건설 되는것이 아니라 병렬적으로 건설이 가능하여 노드들의 위치와 필요한 건물들의 상황에 따라 최소 시간에 오류가 발생) 그래서 앞에서부터 진행하는 방식을 이용하였습니다. 다음 노드에서 단방향으로 들어오는 간선의 개수를 카운트하고 그 카운트가 0이 되었을때 다음 노드를 실행하도록 하였습니다. 2) 알고리즘 다이나믹 프로그래밍 위.. 2022. 4. 16. [백준] 20040 사이클 게임 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 노드들 간에 사이클로 연결이 되어있는지 판단을 하기 위하여 서로소를 이용하였습니다. 서로소는 두개의 노드가 연결이 되어 있다면 하나의 동일한 최상위 부모를 가리키게 됩니다. 따라서 두 노드의 최상위 노드가 서로 다르면 연결이 되어 있지 않으므로 연결을 시켜주고, 두 노드의 최상위 노드가 같으면 이미 연결이 되어 있으므로 현재 간선을 잇게 된다면 사이클이 형성되는 방식을 이용하였습니다. 2) 알고리즘 서로소 알고리즘 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def find(x): # 최상위 부모 노드 탐색 if x != s[x]: # 현재 노드가 최상위가 아니면 x = find(.. 2022. 4. 15. [백준] 17404 RGB거리 2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 이전에 사용한 색상과 다르게 선택해야하고, 가장 첫 집과 마지막 집의 색상이 달라야 하므로 인덱스로 색상을 관리하였습니다. 입력이 3가지 색상이므로 크기 9의 1차원 배열을 생성하였습니다. 0~2 인덱스는 빨간색으로 시작하는 경우로 각 인덱스는 빨간색, 초록색, 파란색으로 끝나는 경우들을 의미합니다. 3~5 와 6~8 인덱스는 각각 초록색과 파란색으로 마지막에 끝나는 경우는 위와 동일합니다. 2) 알고리즘 다이나믹 프로그래밍 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 집의 개수 answer = 1e10 # 비용 (초기 최댓.. 2022. 4. 14. [백준] 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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 12 다음
