버러범의 개발이야기

BOJ 문제 링크 : https://www.acmicpc.net/problem/5430

뒤집기 함수인 R과 배열의 첫번째 요소를 버리는 함수 D를 조합해서 문자열의 형태로 입력에 주어지고 배열이 주어졌을때 함수의 조합들을 실행한후의 배열을 형태를 출력하는 문제이다.

문제에 주어진 조건에 맞게 입력과 출력을 해야하기 때문에 입출력 처리과정이 별도로 필요했다.

또한 R을 수행할때 배열을 직접 뒤질을 필요없이 deque를 이용하여 R이 짝수번 출현한 후의 D들은 deque.pop_front를,

R이 홀수번 출현한 후의 D들은 deque.pop_back으로 D를 수행하면 됐다.

출력시에 deque.size함수를 이용하였는데 deque의 사이즈가 0일시에는 deque.size()-1이 정상적으로 수행되지 않아

별도의 예외처리가 필요했다.(사실 이부분에서 몇시간을 해맸다....)

코드 원본 : https://github.com/sbl133/BOJ/blob/main/%235430.cpp

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

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

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

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

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

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

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

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

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

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

BOJ 문제 링크: https://www.acmicpc.net/problem/1520

각 칸마다 높이가 적혀있는 지도가 입력으로 주어진다. 현재지점보다 낮은 지점으로 상하좌우 이동이 가능하다.

좌측 상단에서 시작해서 우측 하단으로 도착하는 경우의 수를 구하는 문제이다.

현재 위치 (curX, curY) 에서 도착지점 (n-1, m-1) 까지 갈수있는 경로의 수를 cache[curX, curY]에 저장하는 다이나믹 프로그래밍을 이용하면 문제를 풀 수 있다.

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

BOJ 문제 링크: https://www.acmicpc.net/problem/14499

각 칸마다 숫자가 적혀있는 지도안에서 주사위를 굴려가며 주사위가 위치한 칸에 적혀있는 숫자에 따라 다음과 같이 행동한다.

0이 아니면 주사위 밑면에 지도에 적혀있는 숫자를 복사하고 해당칸은 0이된다.

0이면 주사위 밑면에 쓰여있는 수가 칸에 복사된다.

주사위의 6면을 각각 위, 밑, 동, 서, 남, 북을 바라보는 면으로 나눠서 각 면에 적혀있는 숫자를 배열에 저장한다.

주사위를 굴릴때마다 위에서 정의한 배열을 갱신한다.

예를 들어 주사위를 동쪽으로 굴린경우 서쪽을 바라보는 면은 위를 바라보는 면으로 바뀌므로 dice[0]에 적혀 있는 숫자가 dice[3]으로 옮겨져야 된다.

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

알고스팟 문제 링크: 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