버러범의 개발이야기

알고스팟 문제 링크: https://algospot.com/judge/problem/read/GALLERY

그래프에서 인접한 노드중에 적어도 하나의 노드에 감시카메라가 설치되어있지 않으면 해당 노드에 감시카메라를 설치 해야한다.

이때 필요한 최소한의 감시카메라의 개수를 구하는 문제이다.

문제 조건에서 "미술관은 한 번 관람한 갤러리를 다시 가기 위해서는 이전에 지나왔던 복도를 반드시 한 번 지나야 하는 구조로 설계되어 있으며"가 있으므로 해당 그래프는 트리형태임을 알 수 있다.

따라서 자손 노드들의 상태를 보고 하나라도 UNWATCHED상태라면 해당 노드에 감시카메라를 설치하는 알고리즘을 사용할 수 있다.

또한 "모든 갤러리가 서로 연결되어 있지 않을 수도 있습니다."라는 조건이 있으므로 모든 노드가 방문되었는지 확인하는 절차도 필요하다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/28.%20DFS/GALLERY.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/NH

입력으로 주어지는 특정한 문자열 패턴들이 나타나지 않게 알파벳 소문자로만 이뤄진 n자리 암호를 만들 수 있는 모든 경우의 수를 10007로 나눈 나머지를 구하는 문제이다.

bruteforce로 풀게되면 26^n의 시간복잡도를 가지게 되므로 제한시간 안에 문제를 푸는것이 불가하다.

동적계획법을 이용하면 문제를 풀 수 있는데 그 방법이 매우 어렵고 까다롭다. (종만북의 연습문제중 가장 어려웠던것 같다.) 

먼저 입력으로 주어진 문자열 패턴들을 트라이로 만들고 각 노드마다 상태를 부여한다.

앞으로 만들어야하는 글자의 갯수 length, 현재 트라이의 상태를 state라 했을때 cache[length][state]형태의 캐시를 이용한다.

하지만 이렇게 트라이를 이용한 동적계획법을 구현하기 위해서는

먼저 트라이의 각 노드들이 실패연결과 출력문자열을 가지고 있어야하고, 각 노드마다 상태 번호가 부여되야 한다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/26.%20Trie/nh.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/SOLONG

사전에 들어있는 단어들이 빈도수와 함께 주어진다. 특정한 문장을 완성시키려할때 탭키를 사용하여 사전을 참조한 자동완성 기능을 사용할 수 있다.

타이핑한 알파벳을 접두사로 갖는 단어들의 빈도수를 우선순위로 하고 빈도수가 같은  단어가 두개 이상있으면 사전순을 우선순위로 한다.

이때 특정한 문장을 완성시키기 위한 총 타이핑 횟수를 구하는 문제이다.

일단 사전에 들어갈 문자들을 트라이 형태로 삽입한다. 이때 삽입하는 단어들을 빈도수와 사전순을 고려하여 정렬한 후 차례로 삽입한다.

이런식으로 삽입할 경우 자동완성을 위한 first를 한번만 갱신하면 되므로 자동완성 단어를 계산하기 위한 메모리와 시간이 최소화 된다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/26.%20Trie/solong.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/ROUTING

정점에서 다른정점으로 가기 위한 회선을 지날 때 노이즈가 회선에 부여된 수 만큼 곱으로 증폭 된다.

0번째 정점에서 n-1번째 정점으로 가는 최소 증폭량을 구하는 문제이다.

다익스트라 알고리즘을 이용하면 쉽게 문제를 해결할 수 있다.

주의할 점은 곱연산으로 dist를 계산하기 때문에 초기 증폭값을 0이 아닌 1.0으로 두어야 한다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/ROUTING.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/HANOI4

기둥이 4개인 하노이의 탑 문제이다. 단 초기 상태는 입력으로 주어진다.

양방향 BFS를 이용하여 문제를 풀 수 있다. 이때 각 디스크가 위치할 수 있는 기둥은 총 4개이므로 두개의 비트로 각 디시크의 위치를 표현가능하다.

따라서 총 12*2개의 비트로 디스크의 전체 위치를 표현 가능하므로 비트마스크 기법을 이용하여 int로 디스크의 전체 위치를 표현할 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/29.%20BFS/HANOI4B.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/CHILDRENDAY

문자열로 주어진 특정 십진수(0~9)로만 장난감 갯수를 확보할 수 있다.

장난감을 n명의 아이들에게 나눠주는데 그 중 m명은 같은 개수의 장난감을 받으면 삐지므로 한 개 더 주려 한다.

위 조건을 만족하면서 가능한 적은 수의 장난감의 갯수 c를 계산하는 문제이다.

문제에 주어진 c에 대한 조건을 정리하면 다음과 같다.

1. n+m 이상이어야 한다.

2. n으로 나눈 나머지가 m이어야 한다.

3. d에 포함된 숫자들로만 구성되어 있어야 한다.

먼저 3번 조건을 만족하는 숫자들 중에서 2번을 만족하는 경우를 계산하는 방법을 생각해보면,

c의 뒤에 숫자 x를 붙여나가는 방식으로 c를 확장한다면 ((c mod n)*10+x) mod n = (c*10+x) mod n 이므로 c를 n으로 나눈 나머지가 m인 최소 숫자를 찾을 수 있다.

이때 주의할 점은 n+m이상인 조건도 만족시켜야 하므로 n+m미만인 나머지값 정점이랑 n+m이상인 나머지값 정점을 구분해야 한다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/29.%20BFS/CHILDRENDAY.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/SORTGAME

중복이 없는 정수 수열에 임의의 구간을 선택해서 뒤집는 작업을 반복하여 수열을 정렬시킨다 했을때 필요한 최소 뒤집기 횟수를 구하는 문제이다.

상대적 크기가 같은 배열의 최소 뒤집기 횟수는 같다.

예를들어 {1, 3, 2, 4}와 {10, 30, 20, 40}의 최소 뒤집기 횟수는 같다. 따라서 크기가 n인 수열은 원소가 1~n인 경우만 고려하면 된다.

수열의 배치가 다른 각각의 경우의 수는 n!이므로 n!개의 정점과 현재 상태에서 뒤집기 한번 했을때의 수열이 서로 연결된 형태의 그래프를 이용하여 문제를 풀 수 있다.

이때 테스트케이스의 최대가 1000이므로 크기가 1~n인 경우들의 최소 뒤집기 횟수들을 미리 구해놓는다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/29.%20BFS/SORTGAME.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/WORDCHAIN

입력된 단어들을 한번씩만 사용하여 끝말잇기를 한다.

모든 단어를 사용하여 게임이 끝날 수 있는 경우 어떤 순서로 단어를 사용해야 하는지 출력하는 문제이다.

만약 모든 단어를 사용하고 게임이 끝나느 경우가 없다면 IMPOSSIBLE를 출력한다.

알파벳 26개를 정점으로 하는 그래프에서 각 단어의 시작 알파벳을 나오는 방향, 끝나는 알파벳을 들어가는 방향으로 하는 간선을 추가한다.

그래프를 생성한 후에 오일러 서킷/트레일을 이용하여 각 간선의 방문순서를 기록한다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/28.%20DFS/WORDCHAIN.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2