4Legs_Archives

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

문제 링크 : https://www.acmicpc.net/problem/1176 1176번: 섞기 첫 줄에는 학생의 수 N(1 ≤ N ≤ 16)과 최소 넘어야할 키의 차이 값 K(1 ≤ K ≤ 3,400)가 주어진다. 다음 N개의 줄에는 학생들의 키가 순서대로 들어온다. 키는 25,000 이하인 자연수만 들어온다. www.acmicpc.net 분할 정복을 이용한 아이디어 캐치가 중요한 문제이다. 문제의 상황은 N명을 줄세울 때, 줄을 서는 각 학생들의 양 옆 학생들과의 키 차이를 K 초과로 만들고 싶은 상황이다. 가능한 모든 경우를 보려면 최대 경우의 수가 16!로, 무려 조 단위의 수이므로 불가능하다. N명을 줄 세우는 과정을 생각해보자. 지금까지 내가 몇 명을 세웠던 관계없이, 학생 한 명을 지금 세..

[서론] BFS는 DFS와 더불어 그래프 탐색의 기본적인 알고리즘이다. DFS로 풀 수 있는 문제의 대부분은 BFS로 풀 수 있다. 갈 수 있는 모든 노드를 탐색하는 것은 결과적으로 같기 때문이다. 기본적인 정의와 동작 원리를 이해하고, 이차원 배열에서의 응용 문제들을 풀어보자. BFS (Breadth-First Search, 너비 우선 탐색) ■ 개념 그래프를 탐색할 때, 다음 level의 모든 노드를 먼저 방문하여 탐색하는 기법이다. 즉, 인접한 모든 노드를 우선으로 방문하여 탐색하는 방법이라 할 수 있다. ■ 동작 원리 1번 노드에서 출발하는 다음과 같은 그래프에서 BFS가 어떻게 작동하는지 살펴보자. - 1번 노드의 인접 노드인 2, 5, 7번 노드를 순서대로 방문한다. - 2번 노드의 자식 노드..

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

문제 링크 : www.acmicpc.net/problem/2600 2600번: 구슬게임 첫 줄에는 한번에 꺼낼 수 있는 구슬의 개수를 나타내는 세 개 의 정수 b1 , b2, b3 가 나타난다. 그 다음 5개의 각 줄에는 두 통속에 처음 담겨있는 구슬의 개수 k1, k2가 각각 표시되어 있다. www.acmicpc.net 개인적으로는 DP문제가 어려운 이유를 느낄 수 있었던 문제이다. 이 문제는 복잡하게 생각할수록 풀기 어렵고, DP의 개념 중 하나인 분할 정복을 잘 생각한다면 쉽게 풀 수 있는 문제이다. 양쪽 통에 구슬이 각각 x개, y개 들어있을 때, 현재 구슬을 꺼내야 하는 플레이어가 이기는 경우를 생각해 보자. 플레이어는 여러 가지 수를 둘 수 있다. 문제에서 제시된 예제의 경우만 해도 최대 6가..

문제 링크 : www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이� www.acmicpc.net DP와 Bitmask를 활용해 해결할 수 있는 문제이다. Bitmask에 대해서는 다음 링크에 설명해 두었다. 4legs-study.tistory.com/5 Bitmask 에 대해 [서론] 스위치 4개가 있다고 생각해 보자. 이 스위치가 각각 켜져 있거나, 꺼져 있는 경우를 나타내려면 어떻게 해야 할까? 단순하게 생각해 보면 각 스위치마다 켜져 있는지, 꺼져 있는지에 �� 4legs-study.tistory..

[서론] 스위치 4개가 있다고 생각해 보자. 이 스위치가 각각 켜져 있거나, 꺼져 있는 경우를 나타내려면 어떻게 해야 할까? 단순하게 생각해 보면 각 스위치마다 켜져 있는지, 꺼져 있는지에 대한 bool 값을 지정해 bool의 배열 형태로 나타내면 될 것이다. 하지만 스위치가 백만 개, 천만 개라면 어떻게 스위치들의 상태를 나타낼 수 있을까? 또한, 특정 스위치가 켜져 있는지 확인하려면 어떻게 해야 할까? 이런 경우에도 앞서 말한 4개의 스위치가 있는 상황처럼 bool 배열을 이용해서 확인할 수는 있지만, 차지하는 메모리가 너무 많고 비효율적이다. [개념] 전체 원소 집합 중, 각 원소들을 on/off 형태로 구분할 수 있을 때, 특정 원소들의 포함 여부를 한 번에 나타내고 싶은 경우 사용한다. 예를 들..

문제 링크 : www.acmicpc.net/problem/1082 1082번: 방 번호 문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 예를 들어, N=4이면, 문방구에서 파� www.acmicpc.net DP의 대표적 유형인 거스름돈 문제와 유사한 문제이다. 숫자를 구매하여 높은 숫자를 만드는 방법은 두 가지가 있다. 1. 자릿수가 높은 숫자를 만든다. (ex. 11111 > 9999) 2. 자릿수가 같다면, 값이 높은 숫자를 만든다. 따라서, "숫자를 많이 사는 것"을 1순위로, "높은 숫자를 사는 것"을 2순위로 두고 구매한다. 아래 코드에서 vector dp[n] 은 금액 n으로 구..