SW 역량 테스트 준비 - 연습
문제 목록 : https://code.plus/course/33
풀지 않았던 문제들만 풀어보며 기록했습니다.
브루트 포스
BOJ 1107: 리모컨
Link : https://www.acmicpc.net/problem/1107
solution
예외처리를 좀 해줘야 했다. 더 깔끔하게 푸는 풀이가 있을진 모르겠지만..
여러 TC를 참고한 덕분에 AC를 받는데는 수월했다. 체크해야 하는 경우의 수는 크게 3가지다.
- 기본값 100부터 N까지의 차이(+-)
- N과 자릿수가 같은, 만들 수 있는 숫자들
- N의 자릿수보다 1자리 더 많으면서, 만들 수 있는 최솟값
BOJ 6064: 카잉 달력
Link : https://www.acmicpc.net/problem/6064
solution
M이 x로 나누어 떨어질 때 또는 N이 y로 나누어 떨어질 때를 주의해야 한다.
기본값을 x로 시작해서 M을 계속 더해가면 나머지는 x로 유지가 된다.
이 때 N으로 나눈 나머지가 y일 때 값을 출력하면 된다.
물론 M != x, N != y일 때 해당된다. 그렇지 않을 경우 예외 처리를 해줘야 한다.
BOJ 1748: 수 이어 쓰기 1
BOJ 2529: 부등호
BOJ 1339: 단어 수학
Link : https://www.acmicpc.net/problem/1339
solution
입력받은 문자열에서 알파벳들을 모아 0~9 숫자를 매핑시킨다.
이 숫자의 모든 순열을 구해서 최댓값일 때를 취하면 된다.
알파벳 종류가 10개일 때를 로컬에서 돌렸을 때 생각보다 출력이 늦게 나와서 시간초과를 받을 줄 알았는데
제출하니까 600ms 내로 통과가 됐다..
BOJ 14889: 스타트와 링크
Link : https://www.acmicpc.net/problem/14889
solution
N이 작아서 모든 조합을 돌려도 충분히 통과가 된다.
각 팀의 멤버 수는 N/2이므로 N길이에 0과 1을 넣은 후 next_permutation으로 돌려줘서 멤버를 정한다.
정해진 멤버에 대해 능력치를 모조리 더해 비교해주면 된다.
BOJ 2580: 스도쿠
Link : https://www.acmicpc.net/problem/2580
solution
행, 열, 블럭에 대해서 1~9 숫자를 갖고 있는지를 체크하는 변수를 만들어두고
빈 칸에 1~9를 대입하면서 모든 숫자가 채워지면 바로 출력하고 종료한다.
나는 재귀를 계속 호출하는 바람에 exit(0)을 이용했는데 exit(1)를 쓰면 런타임 에러나므로 주의!
BOJ 1062: 가르침
Link : https://www.acmicpc.net/problem/1062
solution
단어의 앞뒤는 각각 anta, tica가 무조건 붙어있다.
이 부분을 제외한 모든 단어를 체크하기만 하면 되는줄 알았는데 그렇게하면 너무나도 쉽게 TLE를 받는다(?)
찾아보니 anta, tica에 있는 철자 a, n, t, i, c도 외우는 대상에 들어가게 된다고 한다.
따라서 모든 단어 앞뒤에 등장하는 철자 5개를 우선으로 외워야 한다.
k가 5보다 작으면 학습 가능한 단어가 없는 셈이다. 예외 처리를 해줘야 한다.
결론은 나머지 철자 21개에 대해서 k-5개를 선택하는 모든 경우를 조사하면 된다.
BOJ 13460: 구슬 탈출 2
Link : https://www.acmicpc.net/problem/13460
Solution
solution
코드가 200줄이 넘어가서 접어놨다ㅠㅠ..
방향마다 어떻게 해야 간결하게 처리할지 떠오르지 않아서 하드코딩이 돼버렸다.
짜는동안 규칙을 잘못 이해해서 삽질을 많이 하기도 했다.
파란 구슬이 먼저 들어가거나 둘이 같이 들어간다고 바로 탐색을 중단하고 -1을 반환하는게 아니고,
해당 케이스에서의 탐색을 더 이상 진행하지 않도록 해야한다.
BOJ 12100: 2048 (Easy)
Link : https://www.acmicpc.net/problem/12100
solution
구현이 빡센 문제다. 생각보다 반례가 툭툭 튀어나와서 깡이 필요하다.
방향에 따라 조금씩 다른 수행을 하도록 되어있어서 코드가 많이 복잡해졌는데
더 줄일 좋은 방법이 떠오르질 않아서 거의 복붙을 해버렸다..
문제 규칙에 맞춰서 정상적으로 동작하는지 꼼꼼하게 확인해볼 필요가 있다.
이 무슨 안하느니만 못한 말인가 싶지만.. 정말 이 말 말고는 딱히 설명할게 없다.
BOJ 1806: 부분합
Link : https://www.acmicpc.net/problem/1806
solution
제목 그대로 부분합(투 포인터)을 이용해서 쉽게 해결했다.
모든 원소가 자연수이기 때문에 부분합은 반드시 오름차순으로 정렬된 상태가 된다.
정렬된 상태이므로 lower_bound()를 통해 이분 탐색으로 조건을 만족하는 최소 인덱스를 찾아주자.
카테고리가 투 포인터, 이분 탐색인데 브루트포스로 묶여있어서 좀 당황했다.
브루트 포스로도 풀 수 있는 건지, 아니면 이 방법도 브루트포스에 포함되는지 잘 모르겠다.
BOJ 1644: 소수의 연속합
Link : https://www.acmicpc.net/problem/1644
solution
소수는 에라토스테네스의 체를 이용해서 미리 구해주면 된다.
이후에는 투 포인터로 해결해주자.
BOJ 2143: 두 배열의 합
Link : https://www.acmicpc.net/problem/2143
solution
각 배열의 원소 갯수 최댓값이 1000이므로 각 배열의 모든 부분합을 구해준 후 정렬한다.
부분합을 담은 각 배열을 A, B라고 하면, A[i]+B[j]=t가 되는 모든 케이스를 구하면 된다.
이분 탐색으로 구하도록 하자.
BOJ 7453: 합이 0인 네 정수
Link : https://www.acmicpc.net/problem/7453
solution
a, b, c, d에 담긴 수들을 (a, b), (c, d)로 묶어서 생각하자.
이렇게 묶인 것들 끼리 생길 수 있는 모든 합을 구해 배열 v1, v2에 담은 후
이분 탐색으로 답을 구하면 된다.
BFS
BOJ 2251: 물통
Link : https://www.acmicpc.net/problem/2251
solution
처음 물통의 용량이 각각 A, B, C라 하면 물이 C만큼만 주어진 상태로 시작한다.
첫 번째 물통에 물이 없을 때 답을 갱신해주면 된다.
경우의 수가 생각보다 많지만 변수때문에 헷갈릴 여지가 있으므로 주의하자.
BOJ 12851: 숨바꼭질 2
Link : https://www.acmicpc.net/problem/12851
solution
모든 이동 방법에 따른 카운트가 1씩 증가하므로 BFS로 탐색해주면 된다.
최단 시간만 구한다면 쉬워지지만 최단 시간으로 들어오는 방법의 수를 출력하는 문제여서 조금 까다롭다.
계속 고민하다가 이곳에서 도움을 받았다. 확실히 코드가 간결해졌다!
BOJ 9376: 탈옥
BOJ 9328: 열쇠
Link : https://www.acmicpc.net/problem/9328
solution
밖에서 안으로 들어와야 하므로 테두리를 ‘.’로 감씨고 시작한다.
BFS를 1번만 돌려서는 답을 구할 수 없다. BFS를 돌릴 때마다 열쇠를 얻을 수 있는 케이스가 있을 수도 있어서 그렇다.
열쇠 종류는 최대 26가지(알파벳 개수)이므로 BFS를 27번 돌렸다.
유사 문제, BOJ 1194: 달이 차오른다, 가자.
Link : https://www.acmicpc.net/problem/1194
solution
Q&A를 읽다가 찾은 유사 문제다. 열쇠를 구해야 문을 열 수 있다는 컨셉이 같다.
조금 다른 점은 열쇠 종류가 a~f까지 줄어들었다는 점과 도착지까지의 최단 거리를 구해야 한다.
일단 위에서 풀었던 ‘열쇠’ 문제와는 비슷해보이지만 사뭇 다르다.
TC를 조금만 분석해봤다면 느꼈겠지만 열쇠가 있는 지점을 거치는 순간 또 다른 visited를 이용해야 한다.
visitied를 어떻게 활용하느냐가 관건이다. 또한 key값도 동시에 컨트롤 해줘야 한다.
구조체에 두 개를 별도로 벡터로 만들어서 넣어보는 시도도 해봤으나 너무 느렸다. 어쩌면 당연하다
때문에 결론적으로는 두가지를 한 번에 컨트롤할 수 있는 visited를 만들기 위해 비트마스킹으로 풀었다.
문자의 종류가 많지 않아서 가능했다.
BOJ 4991: 로봇 청소기
Link : https://www.acmicpc.net/problem/4991
solution
누가봐도 BFS로 풀어야 할거 같은데 먼지가 최대 10개까지 있으면서 같은 칸을 밟을 수 있다는게 좀 걸린다.
위에서 풀었던 BOJ 1194 : 달이 차오른다, 가자.처럼 비트마스킹으로 처리해주면 된다.
BOJ 6087: 레이저 통신
Link : https://www.acmicpc.net/problem/6087
solution
반대 방향을 제외한 모든 방향으로 이동할 수 있으며, 90도 회전해서 이동할 경우 1씩 카운트해줘야 한다.
처음엔 배열 dist만으로 해결해보려 했는데 반례가 있는지 통과가 되지 않았다.. ㅠㅠ
구조체에 별도로 카운팅할 수 있는 변수를 만들어서 돌려줬더니 통과할 수 있었다.
일반적인 BFS와 크게 다르진 않다.
BOJ 8111: 0과 1
Link : https://www.acmicpc.net/problem/8111
solution
모든 숫자가 0과 1로 이루어지면서 입력으로 들어오는 n의 배수가 되는 값을 찾아야 한다.
뒤에 0 또는 1을 계속 붙여가며 조건에 맞는 값을 찾으면 바로 반환하면 되므로 BFS로 탐색해야 한다.
처음엔 string으로 큰 수를 관리하면서 풀어보려고 했다.
큰 수는 아니지만 가령 1101이 있다고 하고 input으로 N을 입력받았다고 하자.
그럼 1101은 다음과 같이 쓸 수 있다.
\(1101\%N = (1\times 10^3)\%N+(1\times 10^2)\%N+(1\times 10^0)\%N\)
큰 수의 최대 길이는 100이라고 했으니까 미리 \(10^{100}\)까지 모듈러를 계산해놓고
마지막에 모두 합한 후 모듈러를 해서 0이 나오면 n의 배수가 깔끔하게 나올거라고 생각했다.
근데 TC에서 메모리가 터지고.. 시간은 오래걸리는 문제가 발생했다.
큰 수가 중복됐는지 체크하려면 map말곤 떠오르는게 없는데 이건 또 다른 TLE를 만들거라 이 방법은 포기했다.
그럼 어떤 방법이 있을까? 바로 모듈러의 성질을 이용하면 된다.
결론적으로는 큰 수를 끝까지 가져가면서 일일이 모듈러를 해줄 필요가 없다.
자릿수를 넓혀가면서 그 때 그 때 모듈러를 해줘도 결과가 똑같다.
어차피 처음에 추가하는 수는 1이니까 큐에 들어가는 값이 0일 때 리턴을 해주면 되겠다.
다만 값이 갱신될 때마다 모듈러를 해주니까 잃어버린 값에 대해서 찾을 방법이 있어야 한다.
때문에 from[]을 이용했다. 또한 TLE를 피하기 위해 chk[]도 이용해줘야 한다.
BOJ 15558: 점프 게임
Link : https://www.acmicpc.net/problem/15558
solution
조건에 맞춰서 가능한 경우의 수를 만들어서 돌리면 된다.
가능한 케이스가 발생하면 바로 1을 리턴할 수 있도록 BFS로 돌려준다.
다이나믹 프로그래밍
BOJ 11048: 이동하기
Link : https://www.acmicpc.net/problem/11048
solution
이동하는 방향에 맞춰서 점화식을 세우면 된다.
\(f(x, y)=max(f(x+1, y), f(x, y+1), f(x+1, y+1))+board[x][y]\)
BOJ 1890: 점프
Link : https://www.acmicpc.net/problem/1890
solution
입력받는 정보를 board에 담고 x가 행, y가 열이라 하면 점화식은 다음과 같다.
\(f(x, y)=f(x+board[x][y], y)+f(x, y+board[x][y])\)
경로의 개수는 \(2^63-1\)까지 커질 수 있으므로 long long으로 설정해줘야 하고,
종착점이 아닌데 board[x][y]이 0이 될 수 있으므로 주의해야 한다.
BOJ 15989: 1, 2, 3 더하기 4
Link : https://www.acmicpc.net/problem/15989
solution
같은 숫자들로 더해지고 순서만 다른 케이스를 제거해야 한다.
인자 1개만으로는 처리하기 어렵고, 1개를 더 추가해야 한다.
f(n, p) : p이하의 숫자로 n을 만드는 경우의 수
BOJ 2294: 동전 2
Link : https://www.acmicpc.net/problem/2294
solution
BOJ 2293: 동전 1에서 조금만 달라진 문제다.
때문에 점화식은 동일하지만 불가능한 경우도 출력해야 한다.
주어진 단위로 나누어 떨어지지 않을 때 INF를 반환하도록 하면 불가능한 경우에 대해 처리할 수 있다.
BOJ 5557: 1학년
Link : https://www.acmicpc.net/problem/5557
solution
인덱스, 중간값, 연산자 총 3개를 인자로 받아서 DP로 처리했다.
각각 cur, mr, oper이라 하고 oper이 0일 때 +, 1일 때 -라하면 점화식은 다음과 같다.
a는 input을 담은 배열이다.
\(f(cur, mr, oper) = f(cur+1, mr+a[cur+1], 0) + f(cur+1, mr-a[cur-1], 1)\)
\(0<=mr<=20\)을 만족하지 않으면 0을 반환해야 한다.
마지막 연산자는 =이므로 인덱스가 n-2일 때 mr이 a[n-1]와 같으면 1을 반환한다.
BOJ 10422: 괄호
Link : https://www.acmicpc.net/problem/5557
solution
괄호 ‘(‘가 등장하면 +1, ‘)’가 등장하면 -1을 한다고 하자.
그럼 sum이 0보다 작아질 경우 ‘올바른 괄호 문자열’이 되지 않는다.
최종적으로 길이가 L(input)과 같아졌을 때 sum이 0이면 1을, 아니면 0을 반환하도록 잘 설정해주자.
보통 TC가 바뀔 때마다 cache를 초기화해주는데
이 문제는 같은 로직으로 길이에 따라 어떤 값이 나오는지를 구하기 때문에
초기화를 처음 이후에는 해줄 필요가 없다. (오히려 하면 TLE를 받는다)
이미 cache에 기록된 상태라면 메모이제이션으로 해결해줄 수 있기 때문이다.
사실 그렇기 때문에 DP인거지만, 습관적으로 초기화를 해서 틀리는 바람에 적어뒀다.
댓글남기기