버러범의 개발이야기

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

스도쿠는 아래와 같은 규칙으로 빈칸을 채워나가는 게임이다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

2. 굵은 선으로 구분되어 있는 3*3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

입력될때 빈칸은 0으로 입력된다.

입력으로 스도쿠 문제가 주어졌을때 알맞게 빈칸을 채운 9*9 행렬을 출력하는 문제이다.

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

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

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

R * C 크기의 표 모양의 보드가 알파벳으로 이뤄진채 주어진다.

말은 보드의 좌측 상단에서 시작해 상하좌우 4방향으로 한 칸씩 이동 가능하다.

단, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과 달라야한다.

이때 말이 최대한 몇칸을 지날 수 있는지 구하는것이 문제이다.

해당 문제는 dfs를 이용하여 문제를 풀 수 있다.

여기서 중요한점은 이미 지나온 경로에 있는 알파벳을 따로 저장하여 앞으로의 경로와 비교해야 한다는 것이다.

나는 지나온 알파벳을 비트마스크 형태로 저장하여 다음 경로의 알파벳과 bit단위 비교를 하여 다음 경로가 유효한지 판단하였다.

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

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

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

출발점에서 도착점까지 이동장치를 이용하여 이동한다 했을때 이동 규칙은 다음과 같다.

바로 직전 이동거리가 k광년이면 이번에 이동 가능한 거리는 k-1, k, k+1 셋 중 하나이다.

음수 혹은 0거리만큼의 이동은 의미가 없다(이동 불가능 하다).

이러한 규칙으로 이동한다 했을때 공간이동 장치 작동 횟수의 최소값을 구하는 문제이다.

이러한 종류의 문제는 일단 가까운 거리부터 어떤방식으로 이동해야 가장 빨리 갈 수 있는지를 나열해 보면된다.

나열하다 보니깐 다음과 같은 규칙을 찾을 수 있었다.

작동 장치를 1번 쓰는 경우 갈 수 있는 거리 : 1(1) - 1개

작동 장치를 2번 쓰는 경우 갈 수 있는 거리 : 2(11) - 1개

작동 장치를 3번 쓰는 경우 갈 수 있는 거리 : 3(111), 4(121) - 2개

작동 장치를 4번 쓰는 경우 갈 수 있는 거리 : 5(1211), 6(1221) - 2개

작동 장치를 5번 쓰는 경우 갈 수 있는 거리 : 7(12211), 8(12221), 9(12321) - 3개

작동 장치를 5번 쓰는 경우 갈 수 있는 거리 : 10, 11, 12 - 3개

작동 장치를 6번 쓰는 경우 갈 수 있는 거리 : 13, 14, 15, 16 - 4개

작동 장치를 7번 쓰는 경우 갈 수 있는 거리 : 4개

작동 장치를 8번 쓰는 경우 갈 수 있는 거리 : 5개

.

.

.

장치를 2번씩 더 쓸때마다 갈 수 있는 거리가 1개씩 더 늘어나는것을 알 수 있었다.

이러한 규칙을 토대로 프로그래밍을 하면 다음과 같다.

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

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

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

N * M 크기의 맵이 있다. 맵에서 벽은 1, 벽이 없는 곳은 0으로 표현된다.

(1,1)에서 (N,M) 위치까지 상하좌우로 한칸씩 이동면서 최단경로를 구하는 문제이다.

이때 벽을 부수고 이동하는 경우 경로가 더 짧아진다면, 벽을 한 개 까지 부수고 이동하여 된다.

bfs를 이용하면 문제를 해결할 수 있다. 이때 이미 지나온 곳을 다시 지나는것을 막기위해 discover배열을 둔다.

단, 벽을 부술 수 있는 상태인지 이미 벽을 부순 상태인지에 따라 이동할 수 있는 경로가 달라지므로 discover를 이차원이 아닌 3차원 배열로 한다.

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

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

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

N * M 크기의 배열 형태로 격자모양을 한 토마토 상자의 정보가 주어진다. 각 칸에는 0, 1, -1이 올 수있는데 각각 익지않은 토마토, 익은 토마토, 빈칸을 의미한다.

익은 토마토는 앞, 뒤, 좌, 우 4방향으로 익지 않은 토마토에게 영향을줘 다음날 익게만든다.

이러한 조건 속에서 토마토들의 정보가 주어졌을때 며칠이 지나면 토마토들이 모두 익는지 그 최소 일수를 구하면 되는 문제이다.

단, 토마토들이 전부 익는 경우가 없으면 -1를 출력한다.

bfs를 이용하면 문제를 풀 수 있지만 날짜를 계산하기 위해서는 추가적인 로직이 필요하다.

이를 위해서 앞으로 익을 토마토들의 목록을 저장하는 queue에 날짜구분자를 삽입하여 날짜를 구분할 수 있도록 한다.

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

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

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

L개의 알파벳이 주어졌을때 L개중 C개를 다음 조건에 맞게 골라 나열하여 출력하는 문제이다.

조건은 C개의 알파벳을 나열한 문자열은 알파벳순으로 정렬되 있어야 하고 모음이 한 개 이상 자음이 두 개 이상이여야 한다.

L개의 문자들을 알파벳 순으로 정렬한후 순서대로 조합하는 방식으로 문제를 해결 할 수 있다.

이때 완성된 암호의 모음의 갯수와 자음의 갯수를 확인하는 유효성 검사가 출력전에 선행되야 한다.

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

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

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

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

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

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

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

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

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