전체 보기232 [백준] 1339 단어 수학 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 단어에서 가장 높은 자릿수에 있는 알파벳을 가장 높은 수로 변환하게 된다면 합을 최대로 할 수 있습니다. 그러나 자릿수가 동일하고 여러 알파벳이 임의로 배치되면 예외 상황이 발생할 것이라 예상하였고, 이를 구현하는데 어려움이 있었습니다. 그리하여 문제에서 입력으로 주어지는 단어의 개수와 단어의 길이가 다소 짧다고 판단하여 완전탐색으로 구현하였습니다. 우선적으로 모든 단어에서 사용되는 알파벳들을 구해주었고, 재귀를 이용하여 알파벳들이 어떤 숫자로 변경되는지에 따라 모든 경우의 수를 구하였습니다. 사용되는 알파벳들이 변환될 숫자가 모두 정해졌다면, 모든 단어들을 숫자로 변경하여 계산을 하였고, 이 중 가장 높은 답을 기록하였습니다. 이후 검색을 통해 그리.. 2022. 6. 28. [백준] 2352 반도체 설계 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 연결선들이 서로 꼬이지 않기 위해서는 다음 연결하는 포트가 이전에 연결된 포트보다 항상 큰 번호에 연결이 되어야합니다. 이러한 조건을 만족하는 내용은 LIS(최장 증가 부분 수열)를 탐색해야하는 문제입니다. 정확한 연결된 번호를 구하는 것이 아니라 가장 긴 길이를 구하면 되므로 이분탐색을 이용하였습니다. 2) 알고리즘 LIS (최장 증가 부분 수열) 이분탐색 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(left, right, target): if left > right: # 탐색 종료 return left mid = (left+right) // 2 # 중간 .. 2022. 6. 27. [백준] 8983 사냥꾼 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 각 동물의 위치를 기준으로 하여 사정거리를 계산하여 X축과 만나는 가장 먼 좌표의 값을 구하였습니다. X축의 하나의 좌표와 접할수도 있고, 두개의 좌표가 나올 수 있습니다. 정렬된 사대를 이분 탐색을 이용하여 두 좌표의 사이에 존재하는 사대가 있는지 여부를 탐색하였습니다. 2) 알고리즘 이분탐색 재귀 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(left, right, targets): # 반복문 이용한 이분 탐색 while left 2022. 6. 26. [백준] 1976 여행 가자 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 여행 계획의 중간에 다른 경로를 지나쳐도 상관 없이, 도시들을 방문할 수 있는지 여부만 판별하면 되었습니다. DFS를 이용하여 여행 계획의 첫 도시를 출발점으로 하여 이동 가능한 모든 도시들을 탐색하였고, 계획의 도시들을 방문 가능한지 여부를 판별하였습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(start): stack = [start] # 첫 도시 출발점 while stack: node = stack.pop() if not visited[node]: visited[node] = 1 # 해당 도시 여행 가능 for next in .. 2022. 6. 25. [백준] 2211 네트워크 복구 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 컴퓨터들간의 연결 관계를 기록하고, 1번 컴퓨터를 시작으로 다른 컴퓨터에 도달 가능한 최소 거리들을 구해야 하므로 다익스트라를 이용하였습니다. 다익스트라 탐색 시, 출발 노드와 도착 노드를 기록하여 어떤 회선을 복구하였는지 기록하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start): h = [(0, start, start)] # 거리, 도착 컴퓨터 번호, 출발 컴퓨터 번호 while h: node = heapq.heappop(h) if distance[node[1]] == -1: # 컴퓨터 거리 .. 2022. 6. 24. [백준] 2616 소형기관차 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 연속된 특정 구간의 합을 이용하여 최대의 값을 구하여야 했으므로 누적합을 이용하였습니다. 누적합을 이용하여 객차의 구간별로 이송 가능한 인원 수를 빠르게 구할 수 있도록 하였습니다. 소형 기관차가 객차를 선택하는 경우에 따라 최대 인원을 구할 수 있었으므로 완전탐색을 이용하여 최대 이송이 가능한 경우를 탐색하였습니다. 그러나 객차의 수가 많아질수록 경우의 수가 다양해지기 때문에 시간 초과 문제가 발생하였습니다. 시간을 줄이기 위하여 DP를 이용하여 최대 이송 인원을 구하였습니다. 2차원 배열을 이용하여 행에는 소형 기관차를 사용하는 개수로 기록하였고, 열에는 객차의 번호로 사용하여 소형 기관차의 사용 개수와 끌고 가는 객차의 번호에 따라 인원수가 기록.. 2022. 6. 23. [백준] 10986 나머지 합 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 특정 구간의 합이 특정 수로 나누어 떨어지는 경우를 찾아야했습니다. 구간의 합을 빠르게 구하기 위하여 누적합을 이용하였습니다. 숫자만큼 반복하여 처음부터 마지막 수까지 누적합을 구하였고, 특정 수로 나눈 나머지만을 구하여 기록하였습니다. 구간의 시작과 마지막이 동일한 경우는 나머지가 0으로 기록되면 경우의 수에 포함할 수 있으므로 누적합에서 0으로 기록된 개수를 찾으면 됬으므로 간단하였습니다. 그러나 모든 구간들의 나머지를 구하기 위해 2중 반복문을 사용하였으나 입력으로 무수히 많은 수가 들어온다면 시간초과 문제가 발생하였습니다. 2중 반복문을 사용하지 않고, 경우의 수를 구하는 방법이 필요했습니다. 누적합의 A~B 구간의 합의 나머지가 X 이고, A.. 2022. 6. 22. [백준] 3584 가장 가까운 공통 조상 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 노드들의 연결 관계를 먼저 정리한 이후, 두 노드를 큐에 담았습니다. 두 노드를 번갈아가며 부모 노드들을 모두 탐색하였습니다. 탐색 중 이미 방문한 노드인 경우가 공통 조상 노드이기 때문에 해당 노드를 반환하였습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(a, b): visited = [False] * N # 노드 방문 여부 q = deque([a, b]) # 큐, 초기에 시작할 두개의 노드 while q: node = q.popleft() if not visited[node].. 2022. 6. 21. [백준] 2580 스도쿠 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 빈칸에 입력이 가능한 숫자들을 채워가며 스도쿠의 조건을 만족시켜야 했습니다. 빈칸으로 주어진 좌표들을 모두 리스트로 정리하였고, 좌표들을 반복하며 해당 좌표에 입력 가능한 숫자들을 모두 구한 후 숫자들을 넣어보며 탐색하였습니다. 2) 알고리즘 DFS 재귀 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def get_can_num(y, x): # 행, 열, 사각형을 확인해서 들어갈 수 있는 번호 구하기 can_num = {1, 2, 3, 4, 5, 6, 7, 8, 9}.difference(sudoku[y]) # 현재 행에서 들어갈 수 있는 번호 for j in range(9): # 현.. 2022. 6. 20. [백준] 1937 욕심쟁이 판다 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 입력으로 주어지는 대나무 숲의 크기가 크므로 모든 좌표에 대해 이동 가능한 거리를 탐색하면 시간 초과 문제가 발생합니다. 그러므로 각 좌표에 이동 가능한 최대의 거리를 기록이 필요하여 DP를 이용하였습니다. 처음에 BFS를 이용하여 가장 적은 대나무 양의 좌표를 탐색하여 이동 가능한 거리를 기록하였고, 기록이 안된 좌표들이 남아있을 경우 다음으로 적은 대나무 양을 가진 좌표를 탐색하여 거리를 구하였습니다. 그러나 기록이 되지 않은 좌표들이 남아있을 때 마다 계속해서 2차원 배열 탐색이 필요하였고, 이전에 기록한 이동 가능한 거리가 탐색의 경우에 따라 값이 변하게 되었습니다. 이러한 과정으로 인해 탐색의 양이 증가하여 시간 초과가 발생하였습니다. 이러한.. 2022. 6. 17. [백준] 2668 숫자고르기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 문제의 조건을 만족시키도록 정수를 뽑기 위해서는 첫째줄의 번호들을 순서대로 모두 뽑을때, 사이클이 생성되는 집합을 찾아야 했습니다. 첫번째 줄에서 선택한 인덱스와 두번째 줄에서 나온 숫자가 같은지 판별을 하기 위하여 두개의 변수를 이용하여 관리하였습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(start): global answer stack = [start] # 스택 chk_first = [] # 첫번째 줄에서 선택한 인덱스 chk_second = [] # 두번째 줄에서 나온 숫자 while stack: node = stack.p.. 2022. 6. 16. [백준] 2251 물통 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 각 바구니로 물을 이동시킬 때, 물을 최대한 많이 옮겨야했습니다. A->B, A->C, B->A, B->C, C->A, C->B 로 물을 옮기도록 하는데, 두 바구니를 비교하여 이동가능한 물의 양을 구하여 이동시켰습니다. 탐색 여부를 확인하는 딕셔너리 변수를 이용하여 중복 탐색을 방지하였습니다. 딕셔너리 변수의 키 값으로는 (A바구니 물의 양, B바구니 물의 양)으로 지정하였습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(): q = deque([(0, 0)]) # 처음 A, B.. 2022. 6. 15. 이전 1 2 3 4 5 6 7 ··· 20 다음
