알고리즘 문제풀이210 [백준] 1516 게임 개발 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 건물을 짓기 위해 필요한 건물의 개수와 해당 건물이 완성되면 다음에 건설 가능한 건물의 목록을 리스트로 관리하였습니다. 건물을 전체적으로 탐색하여 바로 건설이 가능한 목록을 찾은 후 해당 건물이 완성되면 건설이 가능한 다음 건물을 찾았습니다. 그 건물을 짓는데 필요한 앞 건물의 개수 카운트를 1씩 감소시켰고, 0이 되었을 때 건물을 짓도록 하였습니다. 2) 알고리즘 위상정렬 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 건물 수 linked = [[] for _ in ran.. 2022. 7. 4. [백준] 11437 LCA 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 공통의 부모를 찾기 위하여 DFS 탐색을 이용하였습니다. 처음에 DFS 탐색을 루트 노드부터 시작하여 아래 노드로 진행하였고, 해당 노드까지 진행하며 지나친 노드들을 리스트로 기록하였습니다. 위의 작업을 통해 각 노드별로 바로 위 부모부터 루트노드까지 경로가 기록되어 있었습니다. 그 이후 비교할 두 노드의 경로를 가져와 한 노드의 경로에서 요소를 하나씩 가져와 다른 노드 경로에 포함되는지 여부로 공통 부모를 확인하였습니다. 한 번만 DFS탐색을 진행하고, 두 노드의 부모를 찾을때는 기록된 경로들만 가져와 공통 요소를 찾았기 때문에 적은 시간이 소요되었지만, 각 노드별로 모든 부모의 경로를 기록하였기 때문에 메모리 초과가 발생하였습니다. 시간이 조금 더.. 2022. 7. 3. [백준] 9466 텀 프로젝트 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 학생들이 한명을 선택하여 팀이 이루어지는 경우는 사이클이 이루어지는 경우입니다. 따라서, 학생들을 탐색하며 사이클이 이루어지는 경우를 탐색하면 되었습니다. 학생들을 순서대로 탐색하였고, 이미 탐색을 했다면 이후에 같은 학생을 탐색하여도 어차피 같은 결과이므로 한번만 확인하도록 방문 변수를 만들어 확인하였습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(start): stack = [start] pick = [] # 선택된 학생들 while stack: node = stack.pop() if not visited[node]: # 현재 .. 2022. 7. 2. [백준] 11559 Puyo Puyo 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 뿌요가 현재 위치한 좌표와 색상 정보를 딕셔너리에 기록하였습니다.(키 - 좌표, 값 - 색상) 키 값들을 반복하여 인접하고 색상이 동일한 뿌요를 DFS 탐색하였습니다. 4개 이상이 연결되어 있다면 터트리기 위하여 빈 리스트에 좌표값들을 추가적으로 기록하였습니다. 한번의 턴에서 뿌요를 모두 터트렸고(딕셔너리에서 키를 제거), 딕셔너리의 키를 내림차순으로 정렬하여 동일한 열과, 가장 아래의 행(바닥)에서부터 반복이 되도록 구현하였습니다. 새로운 열을 탐색할때, 가장 바닥의 행 인덱스를 초기화하였고, 바로 위의 뿌요의 행과 바닥 행을 서로 비교하여 중력 작용 여부를 판별하였습니다. 2) 알고리즘 구현 DFS 탐색 3) 풀이 코드 사용 언어 - Python .. 2022. 7. 1. [백준] 3055 탈출 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 특정 좌표로 이동하는 최소 시간을 구해야하므로 BFS를 이용하였습니다. 한번의 시간 흐름에 고슴도치와 물이 움직여야 하므로, 시간의 흐름에 따라 구현되도록 하였습니다. 고슴도치와 물이 움직여야 할 좌표들을 집합으로 분류하였습니다. 한번의 시간 흐름에 고슴도치와 물을 모두 이동시키면서 다음번에 이동을 해야할 좌표들을 새로운 집합에 추가하였습니다. 이때, 고슴도치가 이동 가능하여 집합에 추가하였으나 동일한 시간에 물이 들어와 고슴도치가 이동할 수 없는 경우가 발생합니다. 이러한 경우의 고슴도치 좌표를 제거하기 위하여, 고슴도치 이동 좌표 집합에서 물 이동 좌표 집합의 요소들을 빼주었습니다. 2) 알고리즘 BFS 구현 3) 풀이 코드 사용 언어 - Pyth.. 2022. 6. 30. [백준] 17281 ⚾ 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 1번 선수는 4번 타자로 정해져 있고, 나머지 선수들은 순서가 정해져 있지 않아 선수들이 갈 수 있는 모든 순서를 구해야 했습니다. 완전 탐색을 이용하여 가능한 모든 경우를 구하였고, 각 경우마다 이닝을 시뮬레이션하여 득점 가능한 점수들을 구하였습니다. 각 이닝을 시뮬레이션하는 로직에서 1루, 2루, 3루를 리스트로 관리하였고, 반복문을 이용하여 안타, 2루타, 3루타, 홈런의 경우에 모두 적용이 가능하도록 구현하였습니다. 그러나 문제에서 주어진 제한된 시간에 통과하지 못하였습니다. 이후 관련 내용에 대하여 찾아보니 Python3 으로 통과하기에는 거의 불가능하고, PyPy3 에서도 베이스를 리스트로 관리하면 시간 제한에 걸린다는 사실을 알게 되었습니.. 2022. 6. 29. [백준] 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. 이전 1 2 3 4 5 6 ··· 18 다음
