버러범의 개발이야기

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

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

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

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

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

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

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

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

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

222-풀링은 다음과 같은 작업을 말한다.

1. 행렬을 2*2 정사각형으로 나눈다.

2. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다.

3. 2번 과정에 의해 행렬의 크기가 줄어들게 된다.

222-풀링을 반복해서 크기를 1*1로 만들었을때 남아있는 값을 구하는 문제이다.

초기 배열을 기저사례(2*2크기)가 될때까지 4조각으로 쪼갠 뒤 4개의 조각중 3번째로 작은 값을 반환하는 식으로 문제를 해결할 수 있다.

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

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

연구소가 N*M크기 행렬로 주어진다. 연구소 각 칸의상태는 빈칸(0), 벽(1), 바이러스(2) 세가지 중 하나이다.

바이러스가 아직 퍼지지 않은 상태지만, 바이러스가 벽에 막히지 않는다면 상하좌우로 인접한 빈 칸에 퍼져 나갈 예정이다.

벽을 꼭 3개 세워서 바이러스가 퍼져나가는것을 막는다 했을때, 빈칸으로 남을 수 있는 안전영역 크기의 최댓값을 구하는 문제이다.

3개의 벽을 세우는 모든 경우를 구하고, 각 경우마다 바이러스가 퍼졌을때 0으로 남아있는 칸의 갯수를 구하는 식으로 문제를 풀 수있다.

벽을 세울때는 N*M개의 각 칸들을 일차원으로 풀어서 here로 표현한다.

현재영역(here)이 0이면 here에 벽을 설치하거나, 설치안하거나 두가지 경우를 계산하고 here이 0이 아니면 바로 다음칸(here+1)로 넘어간다.

안전영역의 넓이를 구할때는 bfs를 이용하는데 연구소상태(lab)를 훼손시키면 안되므로

visited라는 이차원 배열을 따로 두어서 바이러스가 이미 퍼진곳인지, 아직 퍼지지 않은 곳인지 표현한다.

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

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

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

길이가 N인 이진수 A, B가 있다. A는 모든 자리의 수가 1로만 채워져 있고, B는 각 자리에 0, 1, ? 셋중 하나가 올 수 있다. 

B의 ?를 0 또는 1로 적절히 변환시켜서 A와 B를 곱했을때 자릿수가 최대가 되는 경우의 자릿수, 자릿수가 최소가 되는 경우의 자릿수를 구하는 문제이다.

A와 B의 곱이 최대자릿수를 가지려면 가장 큰 값이 되어야 하고, 그러려면 B의 ?는 모두 1로 변환시켜야 한다.

마찬가지로 A와 B의 곱이 최소자릿수를 가지려면 가장 작은 값이 되어야 하고, 그러려면 B의 ?는 모두 0으로 변환시켜야  한다.

곱의 자릿수가 몇인지는 값이 범위가 너무커서 직접적인 계산으로는 알기 어렵다.

계산할 수 있는 방법으로는 A가 모두 1이므로 B의 최고자리수 미만의 자리에 1인 자리가 있으면 N+B의 자리수,

B의 최고자리수 미만의 자리에 1인 자리가 없으면 N + B의 자리수 - 1 임을 몇개의 예를 통하면 금방 알아차릴 수 있다.

예를 들어 N이 10인 경우 1111111111*0010000001 와 1111111111*0011111111의 자리수는 10 + 8 = 18이다.

하지만 1111111111*0010000000의 자리수는 17이다.

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

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

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

(n,m)크기의 성 입구 (1,1)에서 시작해 (n,m)위치에 있는 공주를 구하는 문제이다.

용사는 현재 무기로는 마법의 벽을 통과할 수 없으며, 성 어딘가에 반드시 한개 존재하는 '그람'을 얻으면 벽을 부수며 성내부를 이동할 수 있다.

기본적인 틀은 bfs를 사용한다. bfs를 이용하면 성에 각 칸을 최초로 발견할때마다 해당 칸을 최단시간에 발견한게 된다.

현재 상태에서 이동할 수 있는 다음칸들을 탐색할때 다음칸에 해당하는 cache가 비어있을 경우에만 queue에 push하고,

다음 칸들을 최초로 탐색할때마다 최초 탐색 시간을 cache에 저장한다.

만약 다음칸들을 탐색하다가 공주를 봤다면 현재시간 + 1 을 바로 return한다.

이때 cache는 '그람'을 소지했는지에 대한 상태도 나타낼수 있어야 하므로 3차원 배열로 표현한다.

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

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

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

뱀이 1행1열을 시작으로 N*N크기의 게임판을 매 초마다 이동하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

L개의 줄로 뱀의 방향 변환 정보또한 주어지는데 정수 x와 문자 c로 이루어져 있으며, 게임 시작 시간으로부터 x초가 끝난 뒤에

왼쪽(c가 'L')또는 오른쪽(c가 'D')로 90도 방향을 회전시킨다는 뜻이다.

뱀이 다음으로 전진할 위치를 방향에 맞게 구한다.

만약 다음 위치가 벽에 막히거나 몸통과 부딪친다면 게임을 끝낸다.

다음 위치에 사과가 있는경우 사과를 없애고 꼬리를 전진시키지 않는다. 만약 이번턴에 방향을 전환해야 된다면 방향또한 전환 시킨다.

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

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

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

정사각형 4개를 이어 붙인 폴리오미노를 테트로미노라 한다.

테트로미노를 90도 회전, 대칭 해서 만들 수 있는 모든 모양의 블럭들중 하나를 각 칸마다 숫자가 적혀있는 N*M종이위에 놓는다.

이때 블럭으로 덮은 칸들의 수들의 합이 최대가 되는 경우를 구하는 문제이다.

먼저 필요한것은 테트로미노로 만들 수 있는 모든 블럭들의 경우들을 구하는 것이고, 총 19개의 경우가 있다는걸 알 수 있다.

가장 직관적인 방법은 이 19개의 블럭들을 하나하나 좌표로 표현해서 푸는 방법이다.

다른 방법으로는 재귀를 이용해 블럭을 한칸씩 4가지 방향으로 4번 확장시키고 나머지 예외를 처리하는 방법이 있다.

첫번째 방법은 블럭들의 좌표를 하나하나 좌표로 표현한다는게 너무 하드코딩 아닌가 생각이들 수 있다.

하지만 두번째 방법으로 풀더라도 블럭들의 모든 경우를 생각해야 하며 해당 알고리즘으로 커버하지 못하는 모양( ㅗ, ㅓ, ㅏ, ㅜ)

들을 예외처리 해야한다는 부담이 있기 때문에 첫번째 방법으로 풀었다.

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

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

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

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

수열 S가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 문제이다.

재귀를 이용해서 현재 상황에서 바이토닉을 만들 수 있는 경우를 각각 따져가면서 가장 긴 경우를 반환하는 식으로 문제를 풀 수 있다.현재 상황을 구분하는 변수들로는 curPos(수열 S에서의 현재 위치), lastNum(가장 최근에 바이토닉의 일부로 고른 숫자),isDec(현재 만들고 있는 바이토닉이 증가중인지 감소중인지) 이렇게 3개가 있다.

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

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