백준136 [백준] 10775 공항 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 1번부터 g번째 게이트 중 하나에 도킹할 수 있으므로, g게이트부터 1번까지 도킹이 가능하다면 바로 도킹을 시도해야합니다. 만약 g 게이트가 이미 도킹하여 사용중이라면 g 보다 작은 수 중 도킹이 가능한 가장 큰 수를 찾아야합니다. 해당 수를 찾기위해 게이트가 도킹이 되면, 다음으로 도킹이 가능한 게이트 번호를 가리키도록 하였습니다. 2) 알고리즘 그리디 3) 풀이 코드 사용 언어 - Python import sys sys.setrecursionlimit(100000000) sys.stdin = open('input.txt') def union(a: int) -> int: ''' 게이트에 비행기 도킹 params: a: 도킹 시도하려는 게이트 번호 r.. 2022. 8. 26. [백준] 17837 새로운 게임 2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 구현 문제로 조건에 따라 특정 행위를 잘 고려할 필요가 있었습니다. 좌표별로 말이 어느 순서로 쌓여있는지 확인을 위해 3차원 배열을 이용하였습니다. 그리고 각 말별로 어느 좌표, 어느 진행 방향을 갖고 있는지 확인을 위해 딕셔너리를 이용하였습니다. 말이 새로운 좌표로 이동을 위해 해당 말과 위에 있는 모든 말을 리스트 형태로 반환하는 함수를 생성하였습니다. 그리고 다음 좌표의 색상에 따라 추가적인 내용이 다르므로 각각의 함수를 생성하였습니다. 이동이 이루어지면, 이동된 모든 말들의 좌표 및 진행 방향을 갱신해주었습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt'.. 2022. 8. 25. [백준] 1525 퍼즐 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 비어있는 칸의 이동을 위해 DFS 탐색을 시도하였으나, 최소 이동 가능한 횟수를 우선적으로 구하는 것이 아니라 이동이 가능한 모든 경우를 탐색하게 됩니다. 모든 경우를 탐색하므로 시간 초과 문제가 발생할 수 있었습니다. 이로 인해 BFS 탐색을 이용하였습니다. 보드판의 특정 상황을 탐색한적이 있는지 확인이 필요했습니다. 특정 좌표의 원시값을 방문 여부로 처리 하는 것이 아니라 2차원 배열의 전체 상황을 기록이 필요하였습니다. 특정 상황의 탐색 여부를 확인하기 위해 2차원 배열을 저장할 수 없으므로, 2차원 배열의 상황을 풀어서 하나의 문자열로 나타냈습니다. 문자열을 이용하여 방문 여부를 확인하였습니다. 2) 알고리즘 BFS 문자열 3) 풀이 코드 사용.. 2022. 8. 24. [백준] 1011 Fly me to the Alpha Centauri 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 문제의 조건에 맞게 각 거리별 이동에 필요한 최소 작동 횟수를 구하였습니다. 작동 횟수 이동 가능한 거리 1 1 2 2 3 3, 4 4 5, 6 5 7, 8, 9 6 10, 11, 12 위의 표와 같이 작동 횟수가 홀수가 될때마다 이동 가능한 거리의 개수가 1씩 증가하는 규칙이 발견되었습니다. 이에 따라 작동 횟수, 이동 가능한 거리의 개수, 마지막 이동 가능한 거리를 변수로 관리하여 탐색하였습니다. 2) 알고리즘 수학 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') T = int(sys.stdin.readline()) for _ in range(T): # 입력 x, y = map(i.. 2022. 8. 21. [백준] 2437 저울 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 처음에 비트마스킹을 이용하여 각 자릿수의 비트가 무게 하나로 생각하여 불가능한 무게를 구하는 방식을 이용하였습니다. 불가능한 무게를 구하기 위해서는 1비트씩 오른쪽으로 시프트 과정을 거치며 AND 연산을 통해 1의 여부 판별을 진행하였습니다. 그러나 입력에 따라 불가능한 무게를 탐색하는 과정이 매우 많이 필요하였고 그로 인해 시간 초과가 발생하였습니다. 추를 가장 가벼운 것부터 정렬하였고, 불가능한 최소 무게보다 작거나 같은 추가 있다면, 해당 무게는 측정이 가능하므로 다음 불가능한 무게로 갱신하였습니다. 그리고 불가능한 무게보다 큰 무게의 추가 나온다면 해당 무게는 측정이 불가능하므로 탐색을 종료하였습니다. 2) 알고리즘 정렬 그리디 3) 풀이 코드.. 2022. 8. 19. [백준] 4195 친구 네트워크 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 친구 관계가 주어지면 두 이름은 하나의 친구가 되어 같은 그룹에 속하게 됩니다. 친구 관계가 주어질때 마다 해당 그룹에 속한 인원 수를 출력해야 했습니다. 그룹을 계속해서 생성하거나 하나로 합치는 과정이 필요했습니다. 이 부분을 서로소집합과 연관지어 접근하였습니다. 기존의 간단한 서로소 집합은 1차원 배열을 이용하여 그룹들을 합치는 과정을 통해 특정 수들이 서로 같은 그룹에 속했는지 여부를 판별할 수 있습니다. 이를 참고하여 이름별 속한 그룹의 번호를 명시하는 딕셔너리 변수와 그룹별 속한 이름의 명단을 기록하는 1차원 배열을 이용하였습니다. 친구 관계가 주어질때 마다 주어진 이름이 현재 그룹에 속해있는지 여부와 그룹의 조건들을 비교하여 그룹을 변경하는.. 2022. 8. 18. [백준] 1944 복제 로봇 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 열쇠의 위치에서 로봇이 분열하여 새로운 로봇으로 이동이 가능합니다. 그로 인해 로봇의 위치와 열쇠의 모든 위치들의 상호 거리를 구한 후 해당 위치를 노드로 하는 최소 신장 트리를 구해야했습니다. BFS 를 이용하여 특정 위치(로봇 시작 위치, 열쇠의 위치)를 시작으로 하여 다른 지점까지의 거리를 모두 구했습니다. 거리의 정보는 딕셔너리 형태로 관리하였으며, 키는 특정 위치의 좌표를 값은 거리와 다른 노드의 좌표를 기록하였습니다. 2) 알고리즘 BFS MST (최소신장트리) 3) 풀이 코드 사용 언어 - Python import sys import heapq from collections import deque sys.stdin = open('input.. 2022. 8. 17. [백준] 1700 멀티탭 스케줄링 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 해당 문제를 처음 접했을 때, 앞으로 사용할 숫자들을 순환하면서 앞으로 사용하지 않거나 가장 적게 사용하는 숫자들을 제거하도록 구성하였습니다. 그러나 적게 사용하지만 일정 주기마다 해당 숫자를 사용해야하는 특정 상황이 발생하면, 해당 숫자를 위해 계속해서 값을 변경해주어야 합니다. 이로 인하여 최소 교환 횟수를 구하기 어려웠습니다. 위의 방법을 보완하여 앞으로 사용하지 않거나, 가장 나중에 사용하는 숫자를 우선적으로 제거하도록 하였습니다. 2) 알고리즘 그리디 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') # 가장 나중에 사용되거나 앞으로 사용하지 않을 숫자 반환 def get_fa.. 2022. 8. 16. [백준] 2206 벽 부수고 이동하기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 시작 좌표에서 도착 좌표까지 이동 시 최소 거리를 구할 필요가 있으므로 BFS 알고리즘을 이용하였습니다. 그리고 최대 한번 벽을 부수고 이동이 가능하므로 현재 이동에서 벽을 부수고 이동이 가능한지 여부도 계산이 필요했습니다. 기존의 BFS 이용 시 좌표별 거리 계산을 2차원 배열을 이용하였으나, 벽을 부수고 이동이 가능한지 여부를 기록하기 위하여 3차원 배열을 이용하였습니다. 크게 벽을 부수고 이동이 가능한 경우를 기록하는 2차원 배열과 벽을 부수지 않고 이동이 가능한 2차원 배열로 구분하였습니다. 다음 좌표의 벽 유무와 현재 조건에 따라 BFS 탐색을 하였고, 탐색이 모두 끝나면 두 2차원 배열에서 더 작은 값을 정답으로 출력하였습니다. 2) 알고리.. 2022. 8. 15. [백준] 1504 특정한 최단 경로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 특정 출발점에서 목적지까지 도착하는 최단 경로를 구하기 위하여 다익스트라를 이용하였습니다. 또한, 거리 기록을 최초에 임의의 큰 값을 입력하여 도착 가능한 최단 경로를 구하도록 구성하였습니다. 두 지점의 노드를 필수적으로 통과해야 했으므로 '출발지 -> 노드1 -> 노드2 -> 도착지' 또는 '출발지 -> 노드2 -> 노드1 -> 도착지' 의 두가지 경우를 탐색하였습니다. 출발지, 노드1, 노드2 를 시작으로 하는 다익스트라를 세번 이용하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start: int.. 2022. 7. 30. [백준] 1719 택배 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 모든 집하장에 대하여 다른 집하장으로 이동하는 최소 소요시간을 구하여야 했습니다. 플로이드 워셜 알고리즘을 이용하여 모든 집하장에 대해 이동 최소 시간을 구하도록 하였고, 다른 집하장으로 이동시 가장 먼저 이동해야할 집하장을 기록하기 위하여 2차원 배열을 이용하였습니다. 우선적으로 주어진 경로들은 서로 연결되어 있으므로 가장 먼저 이동할 집하장으로 도착 집하장 번호를 기록하였습니다. 이후 플로이드 워셜 알고리즘을 이용할 때, 중간에 다른 집하장을 거쳐 이동하는 것이 더 빠른 경우가 있어 조건이 필요했습니다. 이러한 경우에는 중간에 거치는 집하장으로 가는 경로에 대해서 가장 먼저 이동하는 집하장을 가져와 기록하였습니다. 2) 알고리즘 플로이드 워셜 3).. 2022. 7. 18. [백준] 6087 레이저 통신 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 출발점에서 4가지 방향으로 진행을 시키고, 좌표에 도달하기에 필요한 거울의 개수를 기록하는 배열을 생성하였습니다. 큐를 이용하여 현재 좌표, 다음 진행 방향, 거울 사용 개수를 하나의 묶음으로 보관하였고, 탐색하였습니다. 그리고 방향 전환이 발생하는 경우에 거울 사용 개수에 1을 추가하였습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(start): q = deque() for k in range(4): # 시작 좌표는 4가지 방향으로 시작할 수 있음 q.append((start[.. 2022. 7. 17. 이전 1 2 3 4 ··· 12 다음
