To-do List
🔃 백준 문제 최소 1개 풀기
🔃 지금까지 썼던 TIL 옵시디언에 정리할 거 정리
☑️ 직접 코딩해보기 : 사냥꾼, 하노이탑, nQueen
☑️ Do it! ~ 읽기 : 하노이탑, 8queen
☑️ Do it! ~ 구현 연습 : 큐, 스택, 퀵 정렬(피봇 3선발), 병합 정렬, 힙 정렬, 백트래킹
☑️ 슈도 코드 변환 : 버블 정렬, 이분 탐색, 백트래킹
☑️ 지금까지 썼던 TIL 옵시디언에 정리
✅ Do it! ~ 구현 연습 : 퀵 정렬
✅ 백준 : 2630 색종이 만들기, 10828 스택, 2493 탑
✅ 시간 복잡도 어떻게 구하는지 알아내기 : 개잘하는 동기분이 알려주심
✅ 지금까지 썼던 TIL 옵시디언에 정리할 거 정리 : 0701 ~ 0705
배운 것들
.sort()는 NoneType 반환
gun = list(map(int, input().strip().split())).sort()는 안된다.
gun = list(map(int, input().strip().split()))
gun.sort()로 해야 오류가 안 난다
시간 복잡도 구하는 법
O(n) : for문 하나
O(n^2) : for문 두개
O(nlogn) : for문 범위 하나가 점점 줄어듦
nQueen
- 직관으로 풀면 안된다. 시간 복잡도를 생각해야된다. O(n^3)은 안된다고 보면 됨.
- 한 줄에 하나씩만 들어갈 수 있다 : for문으로 풀 수도 있다.
- 한 줄에 하나만 들어갈 수 있으니 이차원 배열을 일차원 배열로 바꿔서 넣을 수 있다. (각 인덱스가 가로 위치도 겸하게 삽입)
Git 짤막 특강
git checkout : 브랜치 바꾸기
git add filename.py : 파일 인지시키기
git commit
-a : 변경된 트래킹된 파일을 자동으로 스테이징
-m : 커밋 메시지를 인라인으로 제공
-am : -a, -m 두 개 합침
git push --set-upstream origin exercise/lazyArtisangit push: 로컬 저장소의 변경 사항을 원격 저장소에 푸시.
--set-upstream 또는 -u: 로컬 브랜치와 원격 브랜치를 연결하여, 이후 git push나 git pull 명령어를 단순하게 사용 가능.
origin: 원격 저장소의 이름.
exercise/lazyArtisan: 원격 저장소의 브랜치 이름.
clone한 로컬 저장소에서 github에 push하고
main branch 관리하는 시니어에게 pull request해서 merge
퀵 정렬
정렬 과정
- 피봇(pivot)값 하나를 고른다
- 피봇값 기준으로 작으면 왼쪽, 크면 오른쪽에 넣는다
- 피봇값 왼쪽에 있는거, 오른쪽에 있는거에서 또 각각 피봇값 고르고 정렬한다
- 숫자 3개 크기(ex. 7,8,9)까지 쪼개진 조각들을 다 정렬하면 정렬 완료
1회 정렬하는 코드
def partition(a: MutableSequence) -> None:
"""배열을 나누어 출력"""
n = len(a)
pl = 0 # 왼쪽 커서
pr = n - 1 # 오른쪽 커서
x = a[n // 2] # 피벗(가운데 원소)
while pl <= pr:
while a[pl] < x: pl += 1 # 피벗보다 큰걸 찾을때까지 처음부터 위로 올린다
while a[pr] > x: pr -= 1 # 피벗보다 작은걸 찾을때까지 끝부터 아래로 내린다
# 인덱스 pl에서의 값은 피벗보다 크거나 같은 값,
# 인덱스 pr에서의 값은 피벗보다 작거나 같은 값이 선택됨
if pl <= pr:
# pl과 pr의 값을 교환한다
a[pl], a[pr] = a[pr], a[pl]
# 교환한 인덱스 바로 다음 인덱스부터 탐색 재개
pl += 1
pr -= 1이 함수를 실행하면 배열이 가운데 값을 기준으로 왼쪽과 오른쪽으로 정렬된다.
이 과정을 3개짜리 조각들도 정렬될 때까지 진행하면 전체 배열의 정렬이 완료된다.
이 코드는 배열 가운데에 있는 원소를 피벗으로 선택했다.
피벗을 어떤 값으로 선택하느냐에 따라 성능에 영향을 미친다.
완전한 코드
def qsort(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 퀵 정렬"""
pl = left # 왼쪽 커서 초기화
pr = right # 오른쪽 커서 초기화
x = a[(left+right)//2] # 피벗(가운데 원소)
while pl <= pr:
while a[pl] < x: pl += 1 # 피벗보다 큰 값 찾으며 올라오기
while a[pr] > x: pr -= 1 # 피벗보다 작은 값 찾으며 내려가기
if pl <= pr: # 탐색 끝난게 아니라면
a[pl], a[pr] = a[pr], a[pl] # 값을 교환
# 다음 인덱스들부터 탐색 시작
pl += 1
pr -= 1
# 크기가 3개인 조각을 정렬 완료한게 아니라면
if left < pr: qsort(a, left, pr) # left는 그대로, pr까지를 쪼갠다
if pl < right: qsort(a, pl, right) # right는 그대로, pl까지를 쪼갠다
def quick_sort(a: MutableSequence) -> None:
"""퀵 정렬"""
qsort(a, 0, len(a) - 1)비재귀적 퀵 정렬
# 비재귀적인 퀵 정렬 구현하기
from typing import MutableSequence
def qsort(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 퀵 정렬(비재귀적인 퀵 정렬)"""
Stack = [i for i in range(left, right+1)]
while not len(Stack) == 0:
pl, pr = left, right = Stack.pop() # 왼쪽, 오른쪽 커서를 꺼냄
x = a[(left+right) // 2] # 피벗(가운데 원소)
while pl <= pr:
while a[pl] < x: pl += 1 # 큰 값을 찾을 때까지 인덱스 위로 올리기
while a[pr] > x: pr -= 1 # 작은 값을 찾을 때까지 인덱스 아래로 내리기
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl] # 두 값을 교환
pl += 1
pr -= 1
if left < pr: 책에서는 이걸 구현할 때 이전 단원에서 직접 구현한 스택을 사용하는데,
나는 곧장 여기로 와서 그런거 구현한 적이 없었다.
직접 구현해보려고 하니 시간이 너무 오래 걸릴 것 같아서
list를 스택으로 사용했는데 어느 순간 구현에 한계를 느낌.
일단 패스하고 퀵 정렬 자체에 집중하기로 함.
(딴 거 먼저 하느라 오늘은 못함)
백준
2630 색종이 만들기
# def 색종이함수
# 종이의 길이가 1이라면 sum에 1을 더하고 return
# 전체 종이를 순회하며 같은 색인지 확인한다 (색이 달라지는지 확인한다)
# 전체 종이가 같다면
# sum에 1을 더하고 return
# 전체 종이가 같은 색이 아니라면
# 1/4, 2/4, 3/4, 4/4 영역을 훑는다풀기 전에 짠 슈도 코드
import sys
input = sys.stdin.readline
N = int(input())
P = [list(map(int, input().strip().split())) for _ in range(N)]
def color_paper(x_s, x_e, y_s, y_e):
global blue, white
# 종이가 전부 같은 색깔인지 판별
all_same = True
color = P[x_s][y_s]
# 범위를 훑으며 첫번째 셀과 같은 색깔인지 확인
for x in range(x_s, x_e):
# 모두 같지 않았다면 for문 취소
if not all_same: break
for y in range(y_s, y_e):
if color != P[x][y]:
all_same = False
break
# 종이가 전부 파란색이었다면
if all_same:
if color == 1:
blue += 1
return
else:
white += 1
return
# 하나라도 다른 색깔이 있었다면
else:
x_mid = (x_s+x_e)//2
y_mid = (y_s+y_e)//2
color_paper(x_s, x_mid, y_s, y_mid) # 1/4
color_paper(x_mid, x_e, y_s, y_mid) # 2/4
color_paper(x_s, x_mid, y_mid, y_e) # 3/4
color_paper(x_mid, x_e, y_mid, y_e) # 4/4
white = 0
blue = 0
color_paper(0, N, 0, N)
print(white)
print(blue)범위 설정에서 조금 헤맸다.
태블릿으로 직접 그려가며 해보니 금방 감이 잡혔다.
머리로만 어떻게 할지 생각하지 말고 직접 써보면서 해야
더 빨리 풀 수 있는 것 같다.
# 코드 출처 : https://wlstyql.tistory.com/133
for i in range(x, x + N):
for j in range(y, y + N):
(생략)
div_conq(x, y + N // 2, N // 2)범위 설정할 때 이렇게 했으면 더 간단했을듯.
2493 탑
import sys
input = sys.stdin.readline
N = int(input())
Tower = list(map(int, input().split()))
valid_idx = [0]
print(0, end='')
for i in range(1, len(Tower)):
h = Tower[i]
zeroEnd = True
# 유효한 타워 높이의 인덱스들이 담긴 배열을 아래로 내려가며 순회
for j in range(len(valid_idx)-1,-1,-1):
# 타워 높이가 송신지보다 낮으면
if Tower[valid_idx[j]] < h:
del valid_idx[-1]
if j == 0:
valid_idx.append(i)
print('', 0, end='')
break
# 타워 높이가 송신지보다 높으면
else:
print('', valid_idx[j]+1, end='')
valid_idx.append(i)
break난생 처음 자력으로 골드 문제를 풀어봤다.
질문 게시판에서 힌트를 좀 보긴 했지만 발상부터 시작해서 거의 다 내가 품.
계속 '틀렸습니다!'가 뜨길래 절망스러웠지만
2,3시간 동안 뚫어져라 보면서 이것저것 고쳐보다가
이유는 알지 못하고 직관적으로 0이 예외 케이스임을 알아냈다.
틀렸던 이유와 피드백
아래로 내리며 타워를 다 돌았는데 송신지보다 높은 타워가 없었다면
valid_idx에 송신지의 인덱스를 추가하고 0을 프린트 해야 함.
하지만 0부터 시작할 땐 이것이 제대로 이루어지지 않음
만약 정상 작동하고 있는 현재의 코드에서
i의 range를 0으로 바꾸고, valid_idx도 빈 리스트로 시작한다면
예외처리해놓은 print(0)을 제외하곤 아무것도 출력하지 않음
i=0으로 첫 for문을 돈다고 가정해보겠음
valid_idx의 크기가 0이므로 j의 for문은 작동하지 않고 패스함
이렇게 되면 valid_idx는 영원히 업데이트될 수가 없음
즉, for문 역시 영원히 작동하지 않음
if zeroEnd:
valid_idx.append(0)
print('', 0, end='')처음엔 인덱스가 0으로 끝나는 상황이 문제라고 생각해서
처음 생략되는 for문을 if zeroEnd:로 대체했음
하지만 valid_idx에 0 값을 넣어 초기화시켜주자마자
원래는 생략되던 for문이 생략되지 않고 작동하기 시작함
인덱스 0에 의한 코드가 2번 작동했고, 원하는 결과가 나오지 않음
이때는 주석이 주렁주렁 달리더라도
내가 원하는 바를 명확히 적었으면 좋았을 것 같음
