2025.03.26

TIL(TODAY I LEARN)

---

• WEEK02 :
  이분 탐색, 분할 정복, 스택, 큐, 우선순위 큐, Linked List, 해시 테이블
• 분할정복과 이분탐색의 새로운 알고리즘 문제를 풀어보자

---

1300 - K번째 수 - 골드1

문제 링크 - https://www.acmicpc.net/problem/1300

내 코드

import sys

input = sys.stdin.readline


N = int(input().strip())

k = int(input().strip())

low = 1
high = N*N
result = 0

def check(mid):
 cnt = 0
 
 for i in range(1,N+1):
     cnt += min(mid//i, N)  
 
 return cnt
 
while low <= high:
 mid = (low + high) // 2
 if check(mid) >= k:
     result = mid
     high = mid -1
 else:
     low = mid + 1
     
print(result)  
    

문제 분류

• 이분 탐색
• 매개 변수 탐색

• 이차원 배열에서 정렬을 수행하지 않고 mid 값을 결정한 뒤 mid 값 보다 작은 값의 개수를 세는 방식
• 작은 값의 개수가 곧 k 번째 수인 경우니까
• 떠올리기 어려운 방식이라고 생각함.

1780 - 종이의 개수 - 실버2

문제 링크 - https://www.acmicpc.net/problem/1780

내 코드

import sys
input = sys.stdin.readline

N = int(input().strip())

matrix = [list(map(int,input().split())) for _ in range(N)]


cnt1 = 0 # -1
cnt2 = 0 # 0
cnt3 = 0 # 1

def sol(mat):
   global cnt1,cnt2,cnt3
   
   if mat[0][0] == -1:
       if 0 in [x for row in mat for x in row] or 1 in [x for row in mat for x in row]:
           pass
       else:
           cnt1 +=1
           return
   elif mat[0][0] == 0:
       if -1 in [x for row in mat for x in row] or 1 in [x for row in mat for x in row]:
           pass
       else:
           cnt2 +=1
           return
   elif mat[0][0] == 1:
       if 0 in [x for row in mat for x in row] or -1 in [x for row in mat for x in row]:
           pass
       else:
           cnt3 +=1
           return
           
   for i in range(0,len(mat),len(mat)//3):
       for j in range(0,len(mat),len(mat)//3):
           submat = [row[j:j+len(mat)//3] for row in mat[i:i+len(mat)//3]]
           sol(submat)
           
sol(matrix)
print(cnt1)
print(cnt2)
print(cnt3)

문제 분류

• 분할 정복
• 재귀

• 내 코드는 현재 메모리를 불필요하게 사용하는 부분이 있음
• 검사 함수를 따로 짜던가/ 파이썬의 all 함수를 사용해보자

---

매개변수 탐색 문제가 너무 어렵다.
어떤걸 이진탐색으로 해야하는가. 결정문제로 바꾸는 그 아이디어 떠올리기가 안된다.