Silver Random Defense
💻230408~230414 (실4~실3)
1. 차의 개수 (실3)
25562
첫 번째 줄과 세 번째 줄은 답이 정해져 있고, 두 번째 줄과 네 번째 줄은 알맞은 예시 중 하나만 들면 됨
1. 최댓값
모든 쌍의 차가 다르면 됨 -> N(N-1)/2
앞 수들의 제일 큰 차이보다 더 크게 차이나는 수가 온다면 차가 겹치지 않음
예시1) 1, 2, 4, 8, 16 - - -
예시2) 1, 10, 100, 1000, 10000 - - -
1. 최솟값
등차수열이면 됨 -> N-1
한 칸 차이나는 것이 다 겹치고, 두 칸 차이나는 것이 다 겹치고, 이를 반복
예시) 1, 2, 3, 4, 5 - - -
2. 국영수 (실4)
10825
arr.sort(key = lambda x: (-x[1], x[2]))
1열에 대해 내림차순 한 후
같은 값이 있다면 2열에 대해 오름차순
3. 다음 순열 (실3)
10972
N이 1이면 정렬할 게 없으므로 -1 출력
dic이 사전 순 첫 번째면 마지막 두 개 위치 바꾸기
dic이 사전 순 마지막이면 -1 출력
그 외 일반적인 경우에는
1)내림차순이 시작되는 지점 찾기(더이상 dic[i-1] < dic[i]가 안 되는 곳)
2)내림차순이 시작된 지점 그 이후 값 중에 내림차순 바로 직전 값보다 크면서 제일 뒤에 있는 수랑 위치 바꾸기
3)새로운 수로 갱신 했으니 내림차순 되어있던 값들을 오름차순으로 바꾸기
예시 7 2 3 6 5 4 1
1)7 2 3 [ 6 5 4 1 ] -> idx = 3
2)7 2 4 [ 6 5 3 1 ] -> 맨 뒤부터 비교하다가 3보다 큰 4가 나와서 위치 바꾸고 break
3)7 2 4 [ 1 3 5 6 ] -> 뒤에 부분 오름차순으로 변경
💻230415~230421 (실4~실3)
1. 십자카드 문제 (실3)
2659
시계수는 한 번씩 돌려보면서 4가지 경우 중 하나로 찾아야 함
1121은 시계수인가? → 아니다. 1112가 시계수
1313은 시계수인가? → 맞다. 오름차순 정렬이 시계수인 것이 아님
2. 킹 (실3)
1063
※ 문제 잘 읽기
돌은 평소에 움직이지 않음
킹이 돌의 위치와 같아질 때만 킹이 움직인 방향으로 움직임
3. 요세푸스 문제 (실4)
1158
3번째 사람을 제거한다고 하면
현재 사람을 제거하므로 거기서 2를 더한 사람을 제거해야 함
원을 이루면서 앉아있기 때문에
남은 사람 수와 나머지 연산자를 사용해야 함
입력 예시: 7 3
idx = 0
[1, 2, 3, 4, 5, 6, 7]
idx = (0+2)%7 = 2
[1, 2, 3, 4, 5, 6, 7]
idx = (2+2)%6 = 4
[1, 2, 4, 5, 6, 7]
idx = (4+2)%5 = 1
[1, 2, 4, 5, 7]
idx = (1+2)%4 = 3
[1, 4, 5, 7]
idx = (3+2)%3 = 2
[1, 4, 5]
idx = (2+2)%2 = 0
[1, 4]
idx = (0+2)%1 = 0
[4]
💻230422~230428 (실4~실1)
1. 아기 상어 2(실2)
17086
1부터 시작하기
처음에 1인 위치를 다 넣고
1 주위 중 0인 곳을 하나씩 늘리면서 세줌
2. 캡틴 이다솜 (실1)
1660
자기 보다 작은 사면체를 다 돌면서
가장 작은 수에 +1을 하면 됨
dp2는 [0, 1, 4, 10, 20, 35, 56, 84, 120, ...]
91보다 작은 사면체 중 가장 큰 수는 84이지만
84+4+1+1+1 → 5이고
56+35 → 2이므로 정답은 2이다
3. 온라인 판매(실4)
1246
가장 큰 수 부터 작은 수로 돌면서
가장 결괏값이 큰 걸 저장 후 출력
💻230429~230505 (실3~실3)
1. 눈치우기(실3)
26215
주의 1. 남은 집 수가 0이나 1일 때 break
주의 2. a[1]을 먼저 pop하고 a[0] pop하기(a[0]을 먼저 pop하면 a[1]에 값이 없을 수도 있음)
주의 3. 반복문 돌 때마다 계속 내림차순 정렬 해줘야 함 (100 100 100 일 때가 그 예시)
2. 섬의 개수(실2)
4963
1. 범위 벗어나면 False 반환
2. 값이 1일 때 주변 8곳을 다 재귀로 돌리면서 0으로 만들고 True 반환
3. 0이면 바로 False 반환
dfs는 그냥 1을 0으로 바꿔 주는 함수
True로 반환될 때의 개수만 세면 됨
3. RGB거리(실1)
1149
첫 번째 dp에는 바로 전 단계의 두 번째와 세 번째 중 더 작은 수를 현재 첫번째 값과 더한 것
두 번째, 세 번째도 똑같이 한다
예제 입력5의 dp 출력 결과
[71, 39, 44]
[71, 127, 94]
[145, 108, 134]
[197, 163, 208]
[246, 255, 174]
[239, 187, 261]
[234, 264, 216]
[276, 282, 253]
💻230506~230512 (실3~실1)
1. 퇴사(실3)
14501
뒤에서부터 구하는 것이 효율적이지만
앞에서부터 구함 → 이차원 dp 테이블 사용
상담 O: dp[i][0]==dp[i-소요기간][0]+오늘 수익(소요기간 수 만큼 전에 상담을 안 했을 때에 수익을 더한다)
상담 X: dp[i][1]==dp[i-1][0]
예제 입력4의 dp 출력 결과
[0, 0, 0, 0, 0, 50, 60, 60, 80, 80, 90]
[0, 0, 0, 0, 0, 0, 50, 60, 60, 80, 80]
예제 입력4 설명
dp[10][0] = dp[7][1]+30 = 60 + 30
7일에 상담을 하지 않으면 8일에 상담을 안 한 것으로 되고 8, 9, 10일에 상담을 하여 30을 벌 수 있다
2. 동물원(실1)
1309
첫 번째 풀이(사자 몇 마리?)
N=0) 1
N=1) 0마리:1 + 1마리:2 = 3
N=2) 0마리:1 + 1마리:4 + 2마리:2 = 7 = 3x2 + 1
N=3) 0마리:1 + 1마리:6 + 2마리:8 + 3마리:2 = 17 = 7x2 + 3
N=4) 41 = 17x2 + 7
두 번째 풀이(전 도형에 두 칸 추가)
전전도형에서 빈칸 두개 붙인거==dp[i-2]
전도형에서 새로운 빈칸에 사자 들어가는 경우 두 가지==dp[i-1]*2
dp[i] = dp[i-2] + dp[i-1]*2
n = 2일 때
n = 3일 때
3. 카드 놓기(실3)
18115
1 2 3 4 5 순서대로 기술 반대로 적용하면 됨
1일 때) 앞에서 넣기
2일 때) 앞에서 두 번째에 넣기(insert 가능)
3일 때) 뒤에서 넣기
※주의 : for문으로 출력하면 시간초과 → *(언패킹 연산자) 사용
💻230513~230519 (실5~실1)
1. N번째 큰 수(실2)
2075
※주의※
다 입력받고 결괏값 구하면 메모리 초과남
하나 입력이 될 때마다 힙 길이는 N으로 맞춰주어야 함
큰 N개의 값 중 제일 작은 것을 출력하면
그것이 N번째 큰 수이다
2. 태권왕(실1)
14562
bfs 사용
if S*2 > T+3: → 미리 예외처리를 해주어 시간 초과 방지
if s < t: → s가 t보다 커버리면 계산을 더이상 진행하지 않게 하여 메모리 초과 방지
10 20 예시 그림
3. 수들의 합(실5)
1789
제일 작은 수인 1부터 더해가다가 그 값이 S보다 커지면 N-1이 답
💻230520~230526 (실4~실2)
1. 덱(실4)
10866
리스트로 받아야 함 → 한 개 받는 경우와 두 개 받는 경우가 있기 때문
2. 한 줄로 서기(실2)
1138
-1은 아직 사람이 서지 않은 곳
-1인 곳에서 cnt값과 arr[i]값이 같으면 사람을 베치하고
아니라면 cnt값 하나 더함
3. 후위 표기식2(실3)
1935
format(값, ".2f") → 3.00으로 출력
💻230527~230602 (실3~실3)
1. NBA 농구(실3)
2852
분:초를 초로 바꾸기
score배열은 현재 이기고 있는 팀을 나타냄(동점이면 0)
마지막은 계산이 안 되므로 for문 나와서 48분으로 계산해줌
print('{:0>2}:{:0>2}'.format(time1 // 60, time1 % 60))이 더 간단한 표현
2. 회전하는큐 (실3)
1021
idx: a배열, 찾으려는 값의 인덱스
start: 큐의 제일 처음 값, 여기서는 뽑아낸 값의 다음 값
min(abs(idx-start), len(arr)-abs(idx-start))
오른쪽과 왼쪽 중 더 가까운 곳 찾는 식
3. 로마 숫자 만들기 (실3)
16922
백트래킹
1+1+5와 1+5+1은 값은 값
이전에 5를 택했으면 다음엔 5보다 크거나 같은 수를 골라야 시간 초과가 안 남
💻230603~230609 (실4~실2)
1. 점프왕 쩰리 (Small)(실4)
16173
board[x][y] == 0 예외처리 안 하면 무한루프 → 런타임 에러
2. 수강신청(실3)
13414
dict.fromkeys(arr)를 사용하여 arr 배열의 요소들을 키(key)로 가지는 새로운 사전을 생성하고, list() 함수를 사용하여 다시 리스트로 변환
중복된 값은 제거, 앞에가 남음
수강 가능 인원 K 출력이지만
그보다 대기목록의 길이 L이나 결괏값이 더 적으면 그 개수를 출력해야 함
3. 과제는 끝나지 않아!(실3)
17952
stack 사용해서 제일 마지막에 있는 값을 계산
4. 놀라운 문자열(실3)
1972
두 개씩 다 만들어보고 중복이 하나라도 있으면 not 출력
이중 포문+'어느 하나라도' → 함수에서 return하는게 flag보다 좋음
5. I AM IRONMAN(실3)
17264
점수가 음수가 될 수 없기 때문에 result = max(0, result-L)
6. 전쟁 - 땅따먹기(실3)
1270
개수 제일 많은 것이 과반수를 넘기는지 알아야 하기 때문에
sorted(dic.items(), key = lambda x: x[1], reverse=True)
x[0]은 key, x[1]은 value, value로 내림차순 정렬을 한 후의
dic[0][1]은 제일 큰 값
7. 달팽이(실3)
1913
첫 길이는 한 번, 나머지 길이는 두 번 반복되므로
1+(N-1)*2
i가 홀수일 때는 방향을 바꾼다
d = 1은 오른쪽이나 아래로 이동
d = -1은 왼쪽이나 위로 이동
i가 짝수일 때는 길이를 하나 줄인다
i=0)N = 5, d = 1
i=1)N = 4, d = 1
i=2)N = 4, d = -1
i=3)N = 3, d = -1
i=4)N = 3, d = 1
i=5)N = 2, d = 1
i=6)N = 2, d = -1
i=7)N = 1, d = -1
i=8)N = 1, d = 1
8. 마인크래프트(실2)
18111
제일 낮은 곳부터 제일 높은 곳 사이에 무조건 정답이 있음
인벤토리에 블록이 없거나
쌓는게 더 시간이 적게 걸리기 때문에 전보다 시간이 커지면 break
9. 싸이버개강총회(실2)
19583
입력 더이상 안 하면 끝일 때
while True: try: except: 구문
set일 때 add는 안에 값이 없을 때만 추가됨
10. 앵무새(실2)
14713
문장 L 완성 + 앵무새가 문장 외의 것을 말하지 않음 → Possible
둘 중 하나라도 충족되지 않으면 → Impossible
11. 부당한 퍼즐(실2)
15501
한 방향으로만 밀기때문에 한 번 밀고 원래 값과 원래 값의 reverse 값을 비교해보면서 for문 돌리면 됨
puzzle의 양끝 원소를 먼저 비교해보고 배열 전체 비교 → 시간 초과 해결
12. 기차가 어둠을 헤치고 은하수를(실2)
15787
visited 리스트를 만들어서 중복일 떈 계산 안 하기 → 시간초과 해결
💻230610~230616 (실1)
1. 트럭(실1)
13335
큐의 제일 앞에 있는 트럭이 다리를 다 건너면 popleft 해줌
큐가 비어있거나 다음 트럭이 올라가도 무게가 L을 넘지 않으면 append 해줌
마지막 트럭이 다리 위로 올라가는 순간 break
time에 마지막 트럭이 건너야 할 다리 길이 더해주면 됨
2. 추월(실1)
2002
back 리스트는 들어간 차의 순서를 나타냄
0부터 돌면서 0의 앞에 있는 것 중 0보다 큰 수의 개수를 센 후 0부터 뒤에만 리스트를 남김
예제 3 back출력
[4, 2, 0, 1, 3]
[0, 1, 3] → result:2
[1, 3]
[3]
3. 배열 돌리기 1(실1)
16926
달팽이로 한 껍질씩 큐로 변환하여 arr에 넣기
각 큐를 rotate한 후 arr를 일차원 배열로 바꿈
다시 달팽이로 arr 출력
4. 경비원(실1)
2564
북→동→남→서 시계방향으로 일차원 배열 만들기
※주의: 남과 서는 M-loc[i][1] 이렇게 길이에서 빼주고 배열에 넣어줘야 함
5. 봄버맨(실1)
16918
계산을 해주기 위해 'O'을 0으로 바꿈 → 0초에 생긴 폭탄이라는 뜻
짝수 시간 때에 모든 폭탄을 설치하면 되는데 이때 폭탄은 시간임
홀수 시간 때에 현재 시각의 3초 전 숫자인 폭탄을 모두 터뜨림
※주의: 폭탄 터뜨릴 때 'arr[j+dx[l]][k+dy[l]] != i-3' 이 조건을 넣어주어야 하는데 현재 터져야 하는 폭탄이 '.'으로 바껴서 안 터지는 상황을 방지하기 위해서임
예제 3 arr배열 출력
초기 상태
.......
...0...
....0..
.......
00.....
00.....
1초 후
.......
...0...
....0..
.......
00.....
00.....
2초 후
2222222
2220222
2222022
2222222
0022222
0022222
3초 후
222.222
22...22
222...2
..22.22
...2222
...2222
4초 후
2224222
2244422
2224442
4422422
4442222
4442222
5초 후
.......
...4...
....4..
.......
44.....
44.....
💻240304~240310 (실5)
1. 집합 (실5)
11723
비트 마스킹
add
1. 1 << int(c[1]): c[1] 자리에 1이 들어간다.
2. S |= (1 << int(c[1])): S에 변경사항이 들어간다.
remove
1. ~(1 << int(c[1])): c[1] 자리에만 0, 다른 수는 다 1인 2진수가 만들어진다.
2. S &= ~(1 << int(c[1])): 나머지는 그대로고 c[1] 자리는 0과 &연산이 되면서 0으로 바뀐다.
check
S & (1 << int(c[1])) == 0: S의 c[1] 자리가 0이라는 뜻, 즉 그 수는 없다.
또는) S & (1 << int(c[1])) == 1 << int(c[1]): print(1)
toggle
xor: 서로 다를 때 1 반환
S ^= (1 << int(c[1])): 서로 다를 때, 즉 S에 없는 것을 추가할 때는 0과 1이 만나 1이 되고,
S에 있는 것을 삭제할 때는 1과 1이 만나 0이 된다.
all
1 << 21: 1000···000
(1 << 21) - 1: 111···111
2. 막대기 (실5)
1094
댓글남기기