[BOJ] 1월 문제풀이
BOJ 16926: 배열 돌리기 1
Link : https://www.acmicpc.net/problem/16926
solution
구현 문제.
둘러싸고 있는 사각형들의 갯수는 $min(n,m)/2$이다.
이를 이용해서 각 사각형들에 속하는 원소들을 Squ[t]에 담아주자. 여기서 t는 사각형의 번호이다. (1부터 시작)
각 사각형의 원소의 갯수는 $2n+2m-4-8(t-1)$이 된다.
r번째부터 좌촉 상단에 담아주면 되는데 r이 원소의 갯수보다 많다면 원소의 갯수만큼 모듈러를 걸어주자.
이후 ret[x][y]에 담아준 후 출력하면 된다.
BOJ 16935: 배열 돌리기 3
Link : https://www.acmicpc.net/problem/16935
solution
구현 문제.
문제에 주어진 쿼리대로 각각 구현을 해서 처리해주면 되는데 최적화가 필요없어서 난이도가 낮게 등록된 것 같다.
반복문을 적절히 이용해주면 된다는 면에서 크게 어렵진 않지만 한 곳에서 꼬이면 시간 잡아먹기 딱 좋은 문제.
BOJ 16917: 양념 반 후라이드 반
BOJ 16936: 나3곱2
Link : https://www.acmicpc.net/problem/16936
solution
브루트포스로 풀 수 있다.
어떤 숫자 x가 있을 때 이를 제외한 값들 중에 x/3, x*2가 있다면 인접 행렬로 인덱스를 담아주고 시작한다.
물론 x/3는 조건에 써있는대로 x가 3으로 나누어 떨어질 때여야 한다.
그리고 각 인덱스에 대해서 재귀를 돌리며 모든 인덱스를 다 돌았을 경우 출력하면 된다.
BOJ 16924: 십자가 찾기
BOJ 16931: 겉넓이 구하기
Link : https://www.acmicpc.net/problem/16931
solution
구현 문제.
현재 위치(x, y)에서 인접한 위치(nx, ny)에 대해 높이가 더 크다면 그 차만큼 답을 갱신해주자.
블럭은 각 위치에 항상 존재하므로 위, 아래를 바라볼 때 보이는 면은 항상 가로세로를 곱한 값이다.
따라서 최종적으로 가로세로 곱의 2배를 더해주면 된다.
BOJ 16956: 늑대와 양
BOJ 16967: 배열 복원하기
BOJ 16929: Two Dots
Link : https://www.acmicpc.net/problem/16929
solution
범위가 작아서 DFS로 풀 수 있다.
문제에 정의된 사이클의 조건을 만족할 때 답을 출력하도록 하고 그렇지 않을경우 재귀를 돌려주면 된다.
BOJ 16964: DFS 스페셜 저지
Link : https://www.acmicpc.net/problem/16964
solution
문제 제목에 적혀있듯이 DFS로 풀 수 있다.
최악의 경우에는 $O(n^2)$이 통과할 수 없으므로
인접한 값들을 모두 정렬해준 뒤 이분 탐색으로 찾는 방법을 택했다.
카테고리를 보니 다른 방법으로도 풀 수 있는 것 같아 보인다.
BOJ 16957: 체스판 위의 공
Link : https://www.acmicpc.net/problem/16957
solution
인접한 위치 중 현재 값보다 작은 값들 중 가장 작은 값의 위치로 이동하는데
인접한 값들이 모두 현재 값보다 큰 위치를 발견할 때까지 이동하게 된다.
위와 다른 현재 위치에서 한 번 기록된 경로를 밟게 된다면 촤종 위치로 바로 이동할 수 있도록
DP를 이용해서 처리하면 된다.
개인적으로 DP보단 분리 집합이 먼저 생각났는데 어떻게 풀어도 상관없어 보인다.
BOJ 16971: 배열 B의 값
Link : https://www.acmicpc.net/problem/16971
solution
이걸 구현 문제로 봐야할지 브루트포스 문제로 봐야할지 모르겠다. 서로 섞은 문제라고 해야하나?
서로 섞는다고 딱히 큰 의미가 있는건 아니다. 생각한 것보다 시간이 정말 오래걸렸다.
풀 아이디어는 떠오르는데 계산 미스때문에 TC를 넘는데도 한참이 걸렸고 중간에 뇌절한게 컸다. 🤕
어떻게 하면 좀 깔끔하게 풀 수 있을까 고민고민하다가 스스로 함정을 팠다.
어떤 경우가 최댓값일지 모르므로 모든 경우의 수를 찾아보긴 해야하는데,
원래 배열에서 행 또는 열을 서로 일일이 바꾸는 행위를 한다면 아마도 TLE를 면할 수 없다고 생각했다.
때문에 누적합 아이디어처럼 R[i]에 i번째 행의 값을 넣어주고 처리하기로 했다.
갑자기 행의 값을 넣는다고 하니 말이 좀 이상한데 이걸 짚기전에 기본적으로 위치별로 몇 번 더해야 하는지
체크해줄 필요가 있다. 3x3 배열에 있다고 하자. 그럼 각 위치별로 더해야 하는 횟수는 다음과 같다.
121
242
121
이걸 NxM으로 확장하면 다음과 같다.
1222...2221
2444...4442
.444...444.
.444...444.
.444...444.
2444...4442
1222...2221
위에서 말한 행의 값은 행에 속해있는 각 위치에 있는 값과 원소를 곱한 값들의 합을 의미한다.
즉, R[i]는 1*a[i][0]+2*a[i][1]+...+2*a[i][m-2]+1*a[i][m-1]을 의미한다.
간단하게 R[i] = 1222...2221이라 하자.
첫번째 행, 마지막 행은 그 외의 행들과 비교했을 때 같은 열 기준 횟수가 절반임을 알 수 있다.
여기서 계산을 하는 방법은 자유지만 내가 푼 방법을 설명해보면,
행을 바꾸는 연산을 했다고 가정하자. 그럼 첫번째와 마지막 행이 다른 행에 비해 절반의 횟수를 가지므로
모두 2444…4442일 때의 총 합을 tmp에 저장한 뒤 첫 번째 행과 나머지 행 또는 마지막 행과 나머지 행을 ${R[i], R[j]}$라 할 때
$tmp-R[i]-R[j]$가 i, j행을 바꿨을 때의 답이 된다. 반드시 한 행은 첫 번째 또는 마지막 행이어야 한다.
그렇지 않다면 서로 바꿔도 두 행 모두 2444…4442번의 횟수를 가지기 때문이다.
이제 마지막으로 열을 바꾸는 연산을 했다고 가정해보자. 이 경우가 좀 까다롭다.
일반성을 잃지않고 한 열은 첫 번째 또는 마지막 열에 픽스시켜놓자.
그리고 나머지 한 열은 첫 번째 또는 마지막 열에 속하지 않는다고 하자.
그럼 서로 바꿨을 때 첫 번째 또는 마지막 행에 속하는 원소는 전자는 횟수가 1 증가, 후자는 1 감소한다.
그리고 그 외의 행들에 속하는 원소는 전자는 횟수가 2 증가, 후자는 2 감소한다.
이 부분들을 구현하면 된다.
열을 바꿀 때 혹시 몰라 더 효율적이고 깔끔한 방법이 없을까 고민하다가 시간이 다 가버렸다.
근데 그럴 필요가 없었던게 이미 누적합 아이디어를 이용한 시점에서 굳이 더 개선할 필요가 없었다.
3중 for문을 사용한게 바로 그 예다. $O(2nm)$은 시간 내에 통과되고도 남는다!
풀면서 이걸 어떻게 글로 옮기지 싶었고 어떻게 옮기는데 까지는 성공했지만 가독성이 많이 떨어지는 것 같다.
개인적으로 설명먼저 읽기보다는 코드먼저 읽고 대충 이렇게 풀었구나 감이 올 때 설명을 읽는게 나아 보인다.
BOJ 16974: 레벨 햄버거
Link : https://www.acmicpc.net/problem/16974
solution
DP로 풀었는데.. 더 쉬운 풀이가 있는 것 같다.
DP로 푸는 것도 그렇게 어렵진 않긴 하다.
나같은 경우 레벨이 n이라고 할 때 f(n)은 레벨-n 버거에 들어가는 총 갯수를,
g(n)은 레벨-n 버거에 들어가는 총 패티 갯수를 반환하도록 DP로 처리했다.
그리고 solve()에서 남은 갯수에 따라 패티 갯수를 반환할 수 있도록 케이스별로 처리해줬다.
남은 갯수가 딱 떨어진다면 더 이상 재귀 호출을 하지 않고 패티 갯수를 반환하도록 했고
그렇지 않은 경우 잔여량에 대해 버거 레벨을 하나 낮춘 뒤 재귀(solve(remain-cur, size-1))를 돌려줬다.
버거를 이루는 케이스 자체도 재귀를 통해 만들어질 수 있기 때문에 DP로 연결지었는데 시간이 좀 걸렸다.
long long 타입으로 처리가 충분히 가능한데 오해해서 string으로 처리하려다 😥
BOJ 9093: 단어 뒤집기
Link : https://www.acmicpc.net/problem/9093
solution
string 내장 함수인 reverse를 이용하면 쉽게 뒤집을 수 있다.
getline()으로 입력받을 시 cin.ignore()를 해줘야 함에 주의. (위에 있는 cin » n 때문)
BOJ 17413: 단어 뒤집기 2
Link : https://www.acmicpc.net/problem/17413
solution
단순 구현 문제.
위 문제인 BOJ 9093: 단어 뒤집기에서 조건이 추가된 버전이다.
태그에 주의해서 조건문을 적절하게 걸어주면 된다.
BOJ 10799: 쇠막대기
Link : https://www.acmicpc.net/problem/10799
solution
구현 문제.
스택으로 푸는 기본 문제로 생각되는데 스택을 안써도 될 것 같아서 그냥 풀었다.
몇 달 전에 프로그래머스에서 풀었던 기억이 나서 코드를 가져와 제출해봤는데 TLE를 받았다! 😨
대강 보니까 $O(n^2)$로 짜서 통과를 못한걸로 보였다. 프로그래머스는 데이터가 약했던 모양인지 통과를 했었는데..
때문에 어떻게 문제를 천천히 읽어보니 $O(n)$으로 짤 수 있는 방법이 금방 보여서 금방 구현하고 AC를 받을 수 있었다!
BOJ 17298: 오큰수
Link : https://www.acmicpc.net/problem/17298
solution
스택 문제. 굳이 스택을 쓰지 않고 배열로 처리해도 상관없다. 사실 그게 더 편한 것 같다.
모든 값을 스택에 push한 후 답을 갱신한다. 즉, 역순으로 처리한다.
현재 값을 cur, 다음 인덱스에 위치한 값을 next라 하자. 각 인덱스를 i, i+1이라 하자.
각 인덱스에서의 답을 ret[i], ret[i+1]라 한다면 cur와 next의 대소 관계에 따라 케이스가 3가지로 나뉜다.
cur == next: ret[i] = ret[i+1]cur < next: ret[i] = nextcur > next: …
1, 2번 케이스는 답을 쉽게 구할 수 있다.
3번이 조금 문젠데, Union-Find 알고리즘에서 부모를 찾는 아이디어를 활용했다.
만약ret[i+1]의 값이cur보다 크다면ret[i]는ret[i+1]이 되겠지만
그렇지 않다면 답을 역추적해 나가야 한다. 때문에 인덱스를 기준으로 지나온 경로를route[인덱스]에 저장한다.
solve(cur, idx)가 바로 역추적하는 함수인데,cur은 현재 값을,idx는ret[i+1]이 위치한 값의 인덱스를 의미한다.
인자에route[idx]를 넣어 재귀를 돌려가면서cur보다 큰 값을 찾고 반환하도록 한다.
이 때idx가 0(default)이거나 -1이면cur보다 큰 값은 더 이상 존재하지 않음을 의미하므로 탐색을 종료한다.
위의 과정을 통해 답을 갱신해주면 되겠다.
단계별로 풀어보기 - 스택에 문제가 새롭게 올라와서 언제 한 번 풀어봐야지 하다 알고리즘 기초 1/2에
적혀있어서 풀어보게 됐다. 금방 풀리겠거니 했는데 시간이 좀 걸리기도 했고 실수도 좀 있었다. 😥
주의 또 주의!
BOJ 17299: 오등큰수
Link : https://www.acmicpc.net/problem/17299
solution
위에서 푼 BOJ 17298: 오큰수에서 기준이 바뀐 문제다.
대소 비교에서 횟수 비교로 바뀌었으니 등장한 횟수를 전처리 해놓고 조건문을 변경해주면 된다.
BOJ 1935: 후위 표기식2
BOJ 1918: 후위 표기식
Link : https://www.acmicpc.net/problem/1918
solution
스택 활용 문제.
간단하게 푼 사람들도 많이 보였는데 나같은 경우 스택의 특성을 주로 활용했다기 보단
재귀 호출로 푼 느낌이 강하다. 딱히 다른 좋은 방법이 떠오르질 않았다.
전체적인 로직은 다음과 같다.
알파벳 또는 괄호로 이루어진 피연산자 그리고 연산자(+,-,*,/)가 있을 때 각각 A,B 그리고 O라고 하자.
그럼 식 중 부분 집합은 AOB로 이루어질 것이고 연장한다면 AOBOC… 가 된다.
괄호 또한 피연산자 취급을 한 이유는 계산하는 로직이 규칙적이기 때문이다.
때문에 연산자 중 곱, 나누기처럼 우선순위가 있거나 괄호가 있다면 재귀 호출을 통해서 별도로 처리했다.
함수가 종료된 후 원래 함수에서 이미 처리한 부분은 지나가도록 visitied(chk)를 활용했다.
난이도에 비해서 엄청 쩔쩔맸다. 처음엔 흘러가는대로 예외 처리를 하다가 4000바이트를 톨파하고
Segmentation fault를 해결하지 못해서 갈아엎는데까지 이틀이 걸렸다. 다른 분들 코드는 정말 간단하더라.
이 문제가 스택 유형이라는 느낌은 강하게 왔으나 구현하는 과정에서 상당히 많은 시간을 소요했다.
qna에서 도움이 되는 tc는 있었으나 다 통과하도록 바꿔도 AC를 못받아 많이 헤맸었는데
원인은 visited에 있었다. 꼼꼼하게 처리하지 못한게 원인이었다. 반성합시다😣
BOJ 11655: ROT13
Link : https://www.acmicpc.net/problem/11655
solution
쉬운 구현 문제.
아스키 코드가 알파벳 범위를 넘어가면 다시 알파벳 범위로 돌아오도록 처리하면 끝.
BOJ 10824: 네 수
Link : https://www.acmicpc.net/problem/10824
solution
쉬운 구현 문제.
처음에 stoi로 처리했는데 int 범위를 넘는 경우때문에 런타임 에러를 받았다. stoi는 int형으로 반환하더라.
그냥 따로 구현해서 처리해줬다.
BOJ 17087: 숨바꼭질 6
BOJ 2089: -2진수
Link : https://www.acmicpc.net/problem/2089
solution
2진수를 구하는 것처럼 처리하면 되는데 다만 나누어야 할 값이 -2이다.
나머지가 0또는 1이 되도록 해야 한다는 점에 주의해야 한다.
BOJ 11005: 진법 변환 2
BOJ 2745: 진법 변환
BOJ 2503: 숫자 야구
Link : https://www.acmicpc.net/problem/2503
solution
브루트포스 문제.
문제에 제시된 기준에 따라 모든 케이스들을 통과하는 3자릿수면서 서로 다른 숫자로 이루어진 수에 대해
조사해야 하므로 111부터 999까지 모두 돌려보면 된다.
조건에 주의.
아무래도 문제집을 골라서 푼다거나 시간을 내서 문제를 엄선하는 정성이 없다보니 결국 코드 플러스로 돌아왔다. 🙃
(아마도) 코딩 테스트 통과를 목적으로 하는 강의다 보니 내 목적에도 맞는 것 같아서 아주 조금씩이라도 풀곤 했는데
SW 역량 테스트 준비 - 문제 2도 어느새 끝내고 알고리즘 기초 1/2도 풀게 됐다! 😆
나중엔 스터디를 구하는 방향으로 해서 푸는 문제들 방향을 바꿔가고 싶다. 아직은 생각중이라 잘 될런지 싶다.
댓글남기기