| 1 |
24.09.03 |
BOJ 9935 |
[스택] LIFO 특성을 생각하면, 가장 최근에 들어간 문자열 중 bomb의 길이 만큼만 매번 확인하며 폭발시키면 된다. |
n이 너무 크니까 이중for문이면 시간초과..ㅠ |
파이썬은 리스트를 stack 처럼 사용 가능.
arr.pop()은 단일 요소만 제거 가능.
del arr[]는 부분 수열 제거 가능~ |
✅ |
| 2 |
24.09.08 |
BOJ 2042 |
[세그먼트 트리] 세그먼트 트리 초기화 -> 부모 노드 채우기 -> 질의값 구하기 & 데이터 업데이트 이 순서에 익숙해지자! |
Python3 로는 시간초과,, Pypy3 로는 통과된다;; |
구간합을 구하기 위해 부모 노드로 올라갈 때, start>end 두 인덱스가 엇갈릴 때에는 ans에 따로 값을 더할 필요가 없다! ==일 때에만 더해주기! |
|
| 3 |
24.09.08 |
BOJ 2357 |
[세그먼트 트리] 구간의 최댓값과 최솟값을 동시에 구해야 하므로 max_seg, min_seg 이렇게 2개의 트리를 초기화함! |
한 구간에 2개의 트리를 탐색해야 하므로 start, end 인덱스 자체가 변하면 안된다. -> s,e 변수를 도입 |
🚨 세그먼트 트리의 부모 노드를 채운 후start==end 일 때에만 추가 연산을 하면 됨!!! |
|
| 4 |
24.09.09 |
BOJ 10868 |
[세그먼트 트리] 최솟값 세그먼트 트리에서는 둘 중 하나의 값이 0일 때, 0이 아닌 값을 부모 노드에 넣어줘야 한다. |
Python3로는 시간초과, Pypy3로 할 때에만 통과하는 이유 -> |
입력받는 데이터가 많은 경우, input = sys.stdin.readline 코드를 통해 입력값 받는 속도를 최소화해야 한다. |
|
| 5 |
24.09.10 |
BOJ 11505 |
[세그먼트 트리] 연산 시간을 줄이기 위해 세그먼트 트리에 값을 저장/변경할 때마다 나머지 연산을 수행 |
이전 값이 0일 수도 있으므로, <기존값으로 나눈 후 새로운 값을 곱함> 방식에서 <곱하기 연산을 새롭게 수행해서 값을 넣어줌> 으로 변경 |
곱하기를 할 때 숫자가 너무 커지면 시간초과가 발생할 수 있다. |
|
| 6 |
24.09.11 |
BOJ 1275 |
[세그먼트 트리] 이제 세그먼트 트리 마스터한듯! 구간 연산 & 데이터 업데이트 => 세그먼트 트리! |
|
|
|
| 7 |
24.09.12 |
BOJ 2268 |
[세그먼트 트리] |
합을 구할 때, 주어진 구간 i, j에서 항상 i<j 가 보장되지 않음. 이 조건 확인 후 함수 호출해야함 |
|
|
| 8 |
24.09.13 |
BOJ 14428 |
[세그먼트 트리] 최솟값의 인덱스를 반환해야하므로 (데이터 값, 인덱스 번호) 튜플 형태로 세그먼트 트리에 저장 |
트리의 왼쪽에 있다고 무조건 더 작은 인덱스가 아님! 항상 인덱스 대소 비교해서 값 넣어주기~! |
|
|
| 9 |
24.09.14 |
BOJ 14438 |
[세그먼트 트리] |
|
|
|
| 10 |
24.09.15 |
BOJ 2243 |
[세그먼트 트리] 너무 어렵다.. |
세그먼트 트리로는 시간초과 발생! 이분탐색 (+재귀) 까지 사용해야됨 |
튜플은 한번 생성되면 그 이후로는 변경이 안된다!! 따라서 변경이 필요하면 리스트를 사용하자! |
✅ |
| 11 |
24.09.16 |
BOJ 5676 |
[세그먼트 트리] 음수/양수/0 중 무엇인지만 알면 되기 때문에 양수는 1, 음수는 -1로 바뀌어서 저장 (연산 시간 최소화하기) |
답을 출력할 때, 매 테스트케이스 사이에 띄어쓰기가 없으면 틀린다.. while 맨끝에 print() 추가하기.. |
입력의 개수가 주어지지 않았을 때 while 문 끝내는 법 : try-except 문 |
|
| 12 |
24.09.17 |
BOJ 14427 |
[세그먼트 트리] 데이터 수와 인덱스를 함께 트리에 저장하기! |
|
|
|
| 13 |
24.11.28 |
BOJ 13975 |
[우선순위 큐] 파일 합치기 (11066번 - DP) 문제를 풀려다가 요구사항 잘못 분석해서 이 문제를 풀어버림 |
|
|
|