GW LABS

한동안 그래프 탐색 문제를 다뤄보지 않아서 복습겸, C++ 공부겸 기본적인 DFS 문제를 풀어봤다. 백준 2644번 촌수계산 문제는 인접 리스트 형태의 자료구조에서 DFS를 통해서 노드의 연결 깊이를 계산하는 문제였다. 인접 리스트이기 때문에 vector를 사용해서 풀었는데 파이썬 보다는 코드가 길어지는 경향이 있다. 아래는 소스코드이다. #include #include #include using namespace std; int search(int searchStart, int searchEnd, vector graph, bool visited[101], int count) { if (searchStart == searchEnd) return count; int answer = -1; visited[s..

C++로 문제푸는 연습을 다시하면서 복습을 할만한 문제였다. 소수 판별의 경우 에라토스테네스의 채를 사용할 수도 있지만 판별하려는 숫자의 제곱근만큼만 탐색하면서 소수를 찾아도 충분히 풀 수 있는 문제였다. 팰린드롬 판별의 경우에는 문자열로 변환하여 손쉽게 판별할 수 있었다. 아래는 풀이이다. #include #include #include using namespace std; bool isPrime(const int& number) { if (number == 1) { return false; } if (number == 2) { return true; } bool answer = true; int limit = static_cast(sqrt(number)); for (int idx = 2; idx > ..

문제를 처음 읽었을 때 어떻게 하면 코드를 줄이면서 구현할 수 있을지 생각해봤다. 회의실 배정 문제같은 그리디 문제에서도 범위와 관련한 문제가 있었는데 이 문제에서는 겹치는 범위를 처리해야 했던 문제였다. 겹치는 범위를 처리하기 위해서 단순히 범위를 표현하는 배열을 만들어두고 그 배열에 겹치는 범위를 표시했다. 아래는 해당 소스코드이다. one, two, three = list(map(int, input().split(" "))) fee_table = [0 for _ in range(100)] for _ in range(3): start, end = list(map(int, input().split(" "))) for idx in range(start-1, end-1): fee_table[idx] += ..

백준 1021번 회전하는 큐 문제는 큐를 이용해서 큐를 회전시키면서 주어진 숫자들을 뽑아내는데 최소 회전 회수를 구하는 문제이다. 쉬운 문제였는데 많은 시간을 소비해 버렸다. 문제 풀이에 있어서 컨디션도 영향을 미치는 것 같다. 또한 알고리즘 문제 풀이에 있어서는 최대한 문제 자체에 집중하기 위해서 필요한 코드만 작정하는 습관을 들여야겠다. 의사코드를 먼저 작성하면 항상 도움이 된다. from collections import deque q_size, pop_count = list(map(int, input().split(" "))) pop_target = list(map(int, input().split(" "))) q = deque([i for i in range(1, q_size+1)]) answe..

백준 11497번 통나무 건너뛰기는 그리디 문제로 정렬을 해서 적절한 순서로 통나무들을 배열시키는 문제이다. 기본 아이디어는 우선 통나무들을 정렬시키고 큰 통나무들을 가운데에, 나머지 통나무들을 배열 양쪽 끝쪽으로 배열시키면 되는 것이다. 그 후 가운데서부터 왼쪽 끝, 오른쪽 끝으로 차이를 계산해서 가장 큰 값을 리턴하면 된다. 처음 접근방법은 가운데 값에서 한 개의 차이값들만 계산해서 [1, 2, 3, 4, 5, 100, 101, 102, 103, 104] 같은 예외에서 실패했다. 다른 그리디 문제들을 통해 예외를 생각해보는 연습을 계속해야겠다. import sys cases = int(input()) for _ in range(cases): length = int(input()) lumbers = l..

14891번 톱니바퀴는 구현 및 시뮬레이션 문제로 좋은 연습이 된 문제다. 4개의 기어들이 회전방향에 따라서 옆에 붙어있는 기어들도 회전시킨다. 그런데 서로 맞물린 극성이 다르다면 회전시킬 수 없고, 회전시킬 수 없는 기어에 맞물린 기어들도 회전시킬 수 없다. 문제를 읽어가면서 부담감이 컸는데 천천히 구현해가면 충분히 풀이할 수 있는 문제였다. 구현과 시뮬레이션 관련한 문제를 좀 더 연습을 많이 해야겠다. import sys from collections import deque if __name__ == "__main__": gears = [] for _ in range(4): gears.append(deque(list(map(int, list(sys.stdin.readline().replace("\n"..

백준 2437번 저울 문제는 정렬을 이용해서 풀 수 있는 그리디 알고리즘 문제이다. 주어진 추들을 정렬하고 추들을 이용해서 만들 수 없는 무게의 최소값을 찾는 문제이기 때문에 역순으로 정렬하여 접근했다. 처음 풀이에서는 최소값을 1씩 늘려가면서 순회하느라 시간초과가 발생했다. 그러나 추들의 무게를 더해주면서 최소값을 찾으면 정답을 얻을 수 있다. 아래는 풀이법이다. import sys if __name__ == "__main__": cases = int(sys.stdin.readline()) weight = list(map(int, sys.stdin.readline().split(" "))) weight.sort(reverse=True) num_check = 1 while True: target = nu..

백준 2583번 영역 구하기 문제는 그래프 탐색 문제의 응용으로, 주어진 좌표로 탐색할 수 없는 영역을 표시하는 부분을 구현하는 것이 핵심인 문제이다. 처음에 접근할 때에는 좌표의 오른쪽 끝점을 포함해서 표시했는데, 이렇게 구현하면 훨씬 큰 영역을 잡게된다. 오른쪽 끝 점에서 1을 빼주고 영역을 표시하고 DFS로 탐색하면 쉽게 풀 수 있는 문제였다. DFS로 구현했을 때 PyPy3 환경에서는 재귀깊이 초과로 런타임 에러가 발생할 수 있다. Python3 환경에서 실행하자. import sys sys.setrecursionlimit(10**6) def dfs(row, col, table): if table[row][col] == 1: return 1 table[row][col] = 1 dx = [0, 0,..