[BOJ]15기 SW마에스트로 1차 코테대비
Coding Test Study 2024 Soma1
💻231223~231229 (브1 ~ 골4)
1. 기상청 인턴 신현수 (브1) 2435
누적합
• max_value는 음수가 될 수 있기 때문에 0이 아니라 전체 합을 초깃값으로 가지고 있어야 한다.
• total에서 제일 앞에 수를 빼고, 그 다음 수를 더하면서 누적합을 계산한다.
2. 감소하는 수 (골5) 1038
브루트포스
1021번째 수는 9876543210
1. 바로 뒤에 수가 현재 수보다 2 이상 클 때 현재 수를 +1 해준다.
2. for문을 통과하기 못 하고, 마지막 수가 9보다 작을 때 마지막 수를 +1
3. 갱신된 수 전까지를 01234···로 초기화 시키기
3. 소수 사이 수열 (실1) 3896
소수
1. 해당 수의 하나씩 앞으로 가면서 소수가 나오면 멈추고, 또 하나씩 뒤로 가면서 소수가 나오면 멈춘다.
2. 몇 개의 수를 가는지 cnt를 해주고 그 값을 출력한다.
4. 전화번호 목록 (골4) 5052
문자열
python은 문자열을 sort하면 앞 글자부터 사전 순으로 된다. 즉 길이가 짧더라도 앞 글자가 사전 순으로 뒤면 뒤에 배치된다.
💻231230~240105 (실4 ~ 골3)
1. 균형잡힌 세상 (실4) 4949
스택
1. '(' 이거나 '[' 이면 stack에 넣는다.
2. ')' 일 때 stack 마지막 값이 '('이 아니면 False
2. ']' 일 때 stack 마지막 값이 '['이 아니면 False
3. 문장이 끝났는 데도 stack에 값이 남아 있다면 False
2. 수 묶기 (골4) 1744
그리디
1. 음수, 0 유무, 양수, 1로 나눈다.
2. 1은 어떤 수와 곱하는 것보다 1을 그대로 결괏갑에 더하는 게 더 큰 수가 된다.
3. 음수 작은 수 부터 두 개씩 묶어서 곱한다.
4. 음수가 홀수 개 있을 때 0이 있으면 0을 곱하고, 없으면 결괏값에 그 제일 작은 음수를 더한다.
5. 양수도 똑같이 큰 수 부터 두 개씩 묶어서 곱한다.
6. 양수가 홀수 개면 결괏값에 제일 작은 양수를 더한다.
3. 감시 (골4) 15683
브루트포스
1. 각 cctv가 볼 수 있는 방향을 상수화하기
2. 현재 있는 cctv에서 각 방향을 조합하여 list를 만든다.
3. 6을 만나기 전까지 각 방향으로 직진하며 0을 #으로 만든다.
4. 0의 개수를 세준다.(0은 사각지대)
4. 스타트링크 (실1) 5014
BFS
1차원 BFS이다. S부터 시작하여 위로는 U, 아래로는 D를 진행하고, G에 방문한 적이 없으면 계단을 이용하면 된다.
5. 벽 부수고 이동하기 (골3) 2206
BFS
• z가 1일 때는 벽을 한번도 부순 적이 없을 때
• z가 0일 때는 벽을 부수고 이동한 적이 있을 때
※ visited 두 개 쓰는 이유
벽을 부순 후에 왔던 길을 다시 갔을 때 더 빨라지는 경우가 있는데
visited를 하나 쓰게 되면 왔던 길은 다시 갈 수 없기 때문에
초기화 되어있는 새로운 visited를 쓰는 것이다.
💻230106~240112 (실1 ~ 골4)
1. 에너지 모으기 (실1) 16198
백트래킹
앞 뒤로 곱하고 현재 수를 지운 배열과 결괏값에 r을 더한 값을 인자로 넘겨주면서 백트래킹을 진행한다.
2. 부분합 (골4) 1806
투 포인터
1. start는 배열 시작 인덱스, end는 배열 끝 인덱스
2. total이 S 이상이면 현재 배열 길이 갱신하고 start를 하나 뒤로 옮긴다.
3. total이 S 보다 작으면 end를 하나 뒤로 옮긴다.
3. 나무 탈출 (실1) 15900
DFS
현재 노드와 이어져 있는 노드가 하나이고, 그것이 이미 방문된 노드라면 그 노드는 현재 노드의 부모 노드이다. 따라서 현재 노드는 리프 노드이다.
4. 색종이 올려 놓기 (골4) 2643
DP
[0] 기준으로 sort했기 때문에 (arr[i].sort())
arr[j][0] <= arr[i][0]은 자명함, 따라서 [1]만 비교해주면 된다.
💻230127~240202 (실4 ~ 골3)
1. 사다리 조작 (골3) 15684
백트래킹
사다리가 놓여져 있는 곳은 1, 아닌 곳은 0
겹치지 않게 하기 위해 가로가 x일 때는 세로를 y부터 돌리고, 아닐 때는 y를 1부터 돌린다.
2. 인구 이동 (골4) 16234
DFS
백트래킹 돌면서 연합하는 곳의 위치를 저장한 후 연합할 때 그 곳들을 평균으로 갱신해주면 된다.
3. 주사위 쌓기 (골5) 2116
브루트포스
1. 제일 밑면이 될 수 있는 주사위를 완전 탐색으로 돌린다.
2. 밑면과 윗면을 제외한 수 중 최댓값을 더해나간 후 그 값들의 최댓값을 구하면 된다.
4. 오큰수 (골4) 17298
스택
stack에는 0, 1, 2, 3, ··· 숫자들이 차례대로 들어간다.
현재 시점보다 왼쪽에 있는 수들 중 가장 오른쪽에 있는 수보다 현재 수가 크면 그 수의 정답은 현재 수가 된다.
※ 예제1 예시 [3, 5, 2, 7]
i=1) 5, stack: [0], answer: [5, -1, -1, -1]
i=2) 2, stack: [1], answer: [5, -1, -1, -1]
i=3) 7, stack: [1, 2], answer: [5, 7, 7, -1]
※ 예제2 예시 [9, 5, 4, 8]
i=1) 9, stack: [0], answer: [-1, -1, -1, -1]
i=2) 5, stack: [0, 1], answer: [-1, -1, -1, -1]
i=3) 8, stack: [0, 1, 2], answer: [-1, 8, 8, -1]
댓글남기기