날짜
2023년 7월 12일
계획
- 알고리즘 3문제 공부하기
- C 프로그래밍 Red-Black Tree 복습하기
- 애들코딩 프로젝트 보안하기
- 코드잇 배포하기
결과
- 스택과 관련된 알고리즘 3문제를 공부하고 이해하였음
- Red-Black tree의 정의에 대하여 정리하였음
- 애들코딩 프로젝트는 우선 코드잇 배포를 위해 연기하였음
- 코드잇 배포는 배포 과정이 처음이라 공부하면서 진행중인 상태
Today I Learned
알고리즘
백준 2493번(링크)
문제 해석과 풀이 방식(X)
우선 타워의 번호와 index를 헷갈려선 안된다. 타워 번호는 1번부터 5번까지지만 리스트에 담을 때 index는 0부터 4이다.
또한 타워의 번호는 왼쪽부터 시작하는 반면, 레이저는 오른쪽을 향해 발사한다.
나는 우선 오른쪽을 기준으로 생각하여 문제를 풀었다.
오른쪽부터 자신의 왼쪽 타워와 높이를 비교하여 옆이 더 높거나 같을 때는 그 타워의 번호를 빈 배열에 넣어주고 그렇지 않으면 스택에 넣어주었다.
점차 진행될수록 스택에 있는 타워들도 비교하여 신호룰 수신할 수 있다면 스택에서 제거하고 알맞은 타워 번호를 배열에 넣어 정답을 구하고자 하였다.
코드(X)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys # 시간초과로 오답
n = int(sys.stdin.readline())
towers = list(map(int,sys.stdin.readline().split()))
arr = []
result = [0] * n
for i in range(n-1,-1,-1):
if i == n-1:
tmp = towers[i]
arr.append(i)
continue
else:
arr.append(i)
if towers[i] >= tmp:
tmp = towers[i]
for j in arr:
if towers[j] <= tmp:
arr.remove(j)
result[j] = i+1
print(*result, sep=' ')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys # 메모리 초과로 오답
n = int(sys.stdin.readline())
towers = list(map(int,sys.stdin.readline().split()))
stk = [n-1]
ans = [0 for _ in range(n)]
for i in range(n-2,-1,-1):
for j in stk[-1::-1]:
if towers[j] <= towers[i]:
ans[j] = i+1
stk.pop()
stk.append(i)
print(*ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys # 시간 초과로 오답
n = int(sys.stdin.readline())
towers = list(map(int,sys.stdin.readline().split()))
ans = [0 for _ in range(n)]
stk = []
stk.append(n-1)
for i in range(n-2,-1,-1):
j = len(stk)-1
while j >= 0:
tmp = stk[j]
if towers[i] >= towers[tmp]:
tgt = stk.pop(j)
ans[tgt] = i+1
j -= 1
stk.append(i)
print(ans)
문제 해석과 풀이 방식(O)
모두 오른쪽부터 타워를 살폈고, 가장 오른쪽에 있는 타워는 스택에 넣고 시작하는 방법이였다. 사실 타워의 index와 높이 값을 둘 다 신경쓰고 있어야 하는게 여러모로 불편했다. 세번이나 시도했지만 틀렸다.
방향을 바꿔 index를 0부터 시작하고, 스택에 타워번호와 높이를 넣어서 기존에 가지고 있던 문제를 해결하였다.
코드(O)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
n = int(sys.stdin.readline())
towers = list(map(int, sys.stdin.readline().split()))
stk = []
ans = [0 for _ in range(n)]
for i in range(n):
while stk:
if stk[-1][1] > towers[i]: # 0번째 : index , 1번째 : 높이
ans[i] = stk[-1][0] + 1 # 몇번쨰 타워인지와 index는 1차이나니까
break
else:
stk.pop()
stk.append([i, towers[i]])
print(*ans)
백준 2504번(링크)
문제해석과 풀이방식(X)
임시값과 정답을 따로 변수로 지정했다. 여는 괄호인 ‘(‘와 ‘[‘는 스택에 넣었고 닫는 괄호일 때는 가장 최근에 스택에 들어간 원소가 같은 종류의 괄호인지 확인하고 알맞으면 숫자를 곱해주었다.그리고 스택의 길이가 0이면 새로운 괄호가 시작되어서 더하기를 해야 한다고 생각해서 정답 변수에 임시값을 더해주고 임시값을 초기화하였다.
코드(X)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys
str = sys.stdin.readline().rstrip()
arr = []
ans = 0
tmp = 1
for i in range(len(str)):
if i and len(arr) == 0:
ans += tmp
tmp = 1
k = str[i]
if k == '(':
arr.append(k)
elif k == '[':
arr.append(k)
elif k == ')':
if arr[-1] == '[':
ans = 0
break
else:
arr.pop()
tmp *= 2
else:
if arr[-1] == '(':
ans = 0
break
else:
arr.pop()
tmp *= 3
if not arr:
print(ans)
else:
print(0)
문제해석과 풀이방식(O)
너무 쉽게 생각했던 것 같다. 위 방식이 잘못된 예제는 넘치고 넘쳤다. 손으로 그리면서 생각해보니 이해가 되었다. 우선 여는 괄호에서 알맞은 숫자를 곱해주고, 닫는 괄호를 만났을 때 경우의 수를 더 생각해야한다. 스택에 방금 들어간 것이 알맞은 괄호가 아니라면 이 괄호는 올바르지 못한 괄호열이므로 0을 출력한다. 알맞은 괄호를 만나더라도 스택이 아닌 실제 괄호열에서 바로 전에 같은 종류의 여는 괄호였는지를 생각해야한다. 바로 이전에 같은 종류의 여는 괄호열이였으면 한 묶음의 괄호가 내부와 상관없이 끝났다는 얘기니 정답값에 임시값을 더해줘야 한다. 그 후 임시값에서 여는 괄호때 곱했던 값을 나눠서 제거해준다. 만약 바로 이전이 같은 종류의 여는 괄호가 아니라면 더해줄 필요없이 바로 나눠주면 된다. 예시로 좀 더 설명해보자면
( ( ) [ [ ] ] ) 이런 괄호열을 생각해보자. 가장 밖의 소괄호는 내부의 값을 2 곱하겠다는 뜻이다. 따라서 2 _ ( ) [ [ ] ] 로 생각할 수 있다. 이번 괄호열은 두 올바른 괄호열이 나란히 있는 모양이므로 덧셈으로 생각해보자. 그렇다면 2_ {2+[[]]} 와 같다. 곱셈을 분배하면 4 + 2[[]]이다. 맨뒤 대괄호를 생각해보면 처음 닫는 괄호가 나왔을때 괄호열에서 바로 이전이 알맞은 여는 괄호였으므로 정답값에 임시값을 더해주고 그 후 나눈다. 반면 두번 째 닫는 대괄호는 괄호열에서 바로 이전이 닫는괄호였으므로 이번엔 더해주지 않는다. 그냥 나누기만 한다. 그럼 임시값은 초기 설정인 1로 돌아오게 되고, 원하는 답을 추론할 수 있다. 저 2개의 겹친 대괄호는 한몸이기에 한번만 더해주면 되기 때문이다. 따라서 정답 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys
word = sys.stdin.readline().rstrip()
stk = []
tmp = 1
ans = 0
for i in range(len(word)):
if word[i] == '(':
stk.append('(')
tmp *= 2
elif word[i] == '[':
stk.append('[')
tmp *= 3
elif word[i] == ')':
if not stk or stk[-1] != '(':
ans = 0
break
if word[i-1] == '(': # 여기를 stk[-1]과 word[i-1]로 하냐에 따라 달라진다.
ans += tmp
tmp //= 2
stk.pop()
elif word[i] == ']':
if not stk or stk[-1] != '[':
ans = 0
break
if word[i-1] == '[': # 여기를 stk[-1]과 word[i-1]로 하냐에 따라 달라진다.
ans += tmp
tmp //= 3
stk.pop()
if stk:
print(0)
else:
print(ans)
백준 2812번(링크)
문제해석과 풀이방식(X)
가장 큰 수가 되기 위해선 가장 높은 자리의 수가 큰게 중요하다고 생각하였다. 따라서 가장 높은 수라 판단되면 스택에 집어넣으면서 새로운 수를 만들었다. 문제는 가장 높은 자리 수를 또 바꿀 수 있는 상황에서 스택에 더 들어가있는 상황을 해결하는게 골치아팠다. 예를들어 [6,5] 라고 가장 높은자리와 두번째 자리를 저장한 상황에서 k가 2라면? 2번 더 지울 수 있는데 다음 숫자가 7이라면? 7을 가장 높은자리에 둬야 문제를 맞출 수 있는데 저 5를 어떻게 뺄것이며 2개가 아니라 더 많다면? 이 부분을 반복문으로만 해결하기엔 힘들었다.
코드(X)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys
n,k = map(int,sys.stdin.readline().split())
num = int(sys.stdin.readline())
num = list(str(num))
tmp = num[0]
arr = []
cnt = 0
while k > 0:
tmp = num[cnt]
flag = False
for i in range(1+cnt,k+cnt+1):
if tmp < num[i]:
tmp = num[i]
cnt = i
flag = True
if flag:
arr.append(tmp)
k -= cnt
else:
cnt += 1
if k == 0:
break
print(*arr, sep='')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
n, k = map(int, sys.stdin.readline().split())
num = list(sys.stdin.readline().rstrip())
stk = [num[0]]
tmp = 0
cnt = 0
for i in range(1, n):
if cnt == k or n-i:
stk.append(num[i])
continue
if stk[-1] < num[i]:
stk.pop()
stk.append(num[i])
cnt += 1
elif stk[-1] == num[i]:
stk.append(num[i])
else:
cnt += 1
print(*stk, sep='')
문제해석과 풀이방식(O)
따라서 for문의 약간의 로직을 수정하였다.
-
k가 0보다 커서 아직 더 지울 수 있을 때
- 현재 스택 원소가 존재할 때
- 가장 최근에 들어간 스택의 숫자보다 지금 숫자가 더 클때.
스택의 top에서 pop하고 수 하나를 지운것이니 k를 1 빼주었다. 이 과정을 조건이 만족하지 않을때까지 while문을 통해 반복하였다. 더이상 조건이 맞지 않으면, 스택에 현재 숫자를 추가하였다. 하나 생각해야하는 경우가 있는데, 끝까지 탐색한 이후에 k가 0이 아니고 남아있을 때이다. 위 while반복문에 걸리지 않고 다 통과해야 끝나는 전체 for문이므로 그동안 저 3가지 조건이 다 만족했다는 뜻인데, k가 남았으니 1은 통과, 2도 당연히 결과가 나왔으니 통과이다. 그럼 3이 계속 만족되지 않았다는 뜻인데 그말은 내림차순으로 정렬되있다는 것을 의미한다. 따라서 k가 남았다면 가장 낮은자리수부터 삭제하면 된다.
코드(O)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys
n,k = map(int,sys.stdin.readline().split())
num = sys.stdin.readline().rstrip()
stk = []
for i in range(n):
while k > 0 and stk and stk[-1] < num[i]:
stk.pop()
k -= 1
stk.append(num[i])
# k가 0보다 크다 위 while문의 조건을 통해 내림차순으로 정렬되어있어서 계속 추가되었음을 알수있다. 따라서 맨뒤부터 빼면 가장작은수부터 뺄수있음.
if k > 0:
while k >0:
stk.pop()
k -= 1
if k == 0 :
print(*stk,sep='')
Red-Black Tree
회고
처음으로 정성들여 쓴 TIL인데 힘들다.. 그래도 내가 공부한 것을 확실히 이해한 것 같아 기쁘다!
