4Legs_Archives

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 programmers.co.kr 문제 유형 Brute Force, DFS, 순열 [2020 카카오 블라인드 코딩 테스트] weak의 크기가 15, dist의 크기가 8로 매우 작기 때문에 완전 탐색으로 접근할 수 있는 문제이다. 우선 각 친구들은 반드시 취약 지점에서 출발하는 것이 유리함은 자명하다. 같은 거리를 이동하더라도 반드시 최대의 취약 지점을 지나기 때문이다. (따라서 문제의 4.5 ~..

문제 링크 : www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 게임을 무한히 할 수 있는 경우는 어떤 경우일까? 일련의 순서로 각 칸을 방문할 때, 이미 한 번 방문했던 칸을 다시 방문할 수 있다면 게임을 무한히 진행할 수 있다. 즉, 게임판 내에서 사이클이 발생하는 경우이다. 따라서, 제시된 2차원 배열의 각 칸을 정점으로 하는 그래프를 구성한 후 1번 정점으로부터 시작해 백트래킹을 통해 최대로 갈 수 있는 거리를 구하면 된다. (이 과정에서 사이클을 발견..

문제 링크 : www.acmicpc.net/problem/2001 2001번: 보석 줍기 첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 www.acmicpc.net 보석의 개수가 최대 14개이므로, 어떤 보석을 주운 상태인지 비트마스크를 통해 나타낼 수 있음을 캐치하자. 보석이 있는 섬에 도착했을 때, 보석을 주운 후 다음 섬으로 이동할 수도 있고 줍지 않고 이동할 수 있다. 위와 같은 예제 그래프에서, 1번 노드에서 출발해 최대로 보석을 주웠을 때의 개수는 4이다. 경로는 다음과 같다. ① 1번 섬에서 보석을 줍지 않고 5번 섬으..

문제 링크 : www.acmicpc.net/problem/17501 17501번: 수식 트리 수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다. 연산자 노드는 항상 두 개 www.acmicpc.net 예제 1을 수식 트리로 나타내면 아래와 같다. 노드 1 ~ 5의 피연산자 노드를 각각 미지수 X1 ~ X5로 두었을 때, 이 수식 트리의 최종 결과값은 (X1 + X3 + X5) - (X2 + X4)가 된다. 즉, 트리의 형태와 상관없이 각 리프 노드(피연산자 노드)까지 도달했을 때, 해당 피연산자가 최종 식에서 어떤 부호를 갖는지만 파악하면 문제를 쉽게 해결할 수 있다. 만약 최종 식에서..

문제 링크 : www.acmicpc.net/problem/2593 2593번: 엘리베이터 첫째 줄에는 N과 M이 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 M줄에 걸쳐 엘리베이터 번호 순서대로 Xi와 Yi가 빈 칸을 사이에 두고 주어지며, 마지막 줄에는 A와 B가 주어진다. N은 100,000이하, M www.acmicpc.net 문제를 그래프의 관점에서 이해하는 것이 중요한 문제이다. 문제에서 층은 최대 10만개, 엘리베이터의 갯수는 최대 100개이므로 BFS를 적용할 때 층이 아닌 엘리베이터를 기준으로 해야 함을 캐치할 수 있다. (BFS의 시간복잡도는 일반적으로 O(V^2)이다.) 문제에서 제시된 예제를 통해 설명하자면, 아래와 같은 엘리베이터 상황을 4층에서 7층으로 이동 가능, 7층에서 12층..

문제 링크 : https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net DFS를 재귀 형태로 구현하면 쉽게 풀 수 있는 문제이다. 문제의 그래프를 인접 리스트 형내로 변환한 뒤, 한 노드에 들어올 수 있는 양의 수 = 모든 자식 노드들에 들어올 수 있는 양의 수 합 이라는 점을 이용하여 루트 노드(1번)의 최종 값을 구하면 된다. 양의 수가 음수가 될 수 없다는 것과 각 값 자료형에만 유의하면 쉽게 해결할 수 있다. [코드] 1 2 3..

[서론] DFS는 BFS와 더불어 그래프 탐색의 기본적인 알고리즘이다. 기본적인 정의와 동작 원리를 이해하고, 이차원 배열에서의 응용 문제들을 풀어보자. DFS (Depth-First Search, 깊이 우선 탐색) ■ 개념 그래프를 탐색할 때, 더 높은 level의 노드를 먼저 방문하여 탐색하는 기법이다. Tree에서 Preorder 순회, 백트래킹과 유사한 점을 보인다. 쉽게 말하자면, 갈 수 있는 한 일단 최대로 깊게 들어가는 방법이라 할 수 있다. ■ 동작 원리 다음과 같은 그래프에서 DFS가 어떻게 작동하는지 살펴보자. 위와 같은 그래프에서 1번 노드를 시작으로 각 노드를 탐색하는 상황을 보자. (단, 같은 level의 노드가 여러 개 있다면 낮은 숫자를 먼저 방문한다) DFS는 일단 갈 수 있..