2025.03.27
TIL(TODAY I LEARN)
- WEEK02 :
이분 탐색, 분할 정복, 스택, 큐, 우선순위 큐, Linked List, 해시 테이블 - week 2 의 마지막날, 오전에 시험을 치뤘다. 시험문제는 아래와 같다.
- 다음주의 키워드는 이렇다
WEEK03 :
그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬
10815 - 숫자 카드 - 실버5
문제 링크 - https://www.acmicpc.net/problem/10815
내 코드
import sys
from bisect import bisect_left
input = sys.stdin.readline
N = int(input().strip())
cards = list(map(int,input().split()))
M = int(input().strip())
isSang = list(map(int,input().split()))
cards.sort()
for i in isSang:
x = bisect_left(cards,i)
if 0 <= x <= len(cards)-1 and cards[x] == i:
print(1,end=" ")
else:
print(0, end=" ")- 이분 탐색이 아닌 해시를 이용하면 더 빠른시간에 탐색이 가능할 것. 이라고 코치님이 말씀해주셨다.
문제 분류
1966 - 프린터 큐 - 실버3
문제 링크 - https://www.acmicpc.net/problem/1966
내 코드
import sys
from collections import deque
from heapq import heapify,heappop,heappush
input = sys.stdin.readline
T = int(input().strip())
for _ in range(T):
N,M = map(int,input().split())
important = deque(map(int,input().split()))
important[M] = -important[M]
target = important[M]
cnt = 0
while True:
x = max(map(abs,important))
if abs(x) == abs(important[0]):
cnt += 1
if important[0] == target:
break
important.popleft()
else:
important.append(important.popleft())
print(cnt)
문제 분류
- 이 문제와 같은 경우에는 보통 인덱스와 큐의 값을 같이 튜플로 저장하는 방식으로 문제를 해결한다고 하더라. 또는 인덱스를 추적해서 해결한다고 하더라.
9935 - 문자열 폭발 - 골드4
문제 링크 - https://www.acmicpc.net/problem/9935
내 코드
import sys
input = sys.stdin.readline
first = input().strip()
bomb = input().strip()
# 시간초과
# while True:
# if bomb in first:
# for i in range(len(first)):
# if first[i:i + len(bomb)] == bomb:
# first = first[:i] + first[i+len(bomb):]
# else:
# if len(first) == 0:
# print('FRULA')
# else:
# print(first)
# break
#스택
stk = []
for i in range(len(first)):
stk.append(first[i])
if len(stk) >= len(bomb):
x = "".join(stk[-len(bomb):])
if x== bomb:
for _ in range(len(bomb)):
stk.pop()
if len(stk) == 0:
print('FRULA')
else:
print("".join(stk))
문제 분류
다행히 이번주는 3개의 문제를 다 풀어낼 수 있었다.
다음 주차를 위해 파이썬 자료형에 대해 공부해보자.
🧠 딕셔너리란?
student = {
"name": "철수",
"age": 18,
"grade": "A"
}
"name"→ 키 (key)"철수"→ 값 (value)
👉 이 딕셔너리는 "name"이라는 키로 "철수"라는 값을 저장한 거예요.
✅ 특징 요약
| 항목 | 설명 |
|---|---|
| 순서 | Python 3.7 이후부터는 입력 순서를 유지해요 |
| 중복 키 | ❌ 불가능 (덮어씌워짐) |
| 가변성 | ✅ 값을 자유롭게 변경 가능 |
| 검색 속도 | 매우 빠름 (해시 기반: 평균 O(1)) |
✨ 기본 사용법
1. 딕셔너리 생성
d = {'a': 1, 'b': 2}
2. 값 접근
print(d['a']) # 1
3. 값 추가/변경
d['c'] = 3 # 추가
d['a'] = 10 # 변경4. 키 존재 확인
if 'b' in d:
print('있음')5. 삭제
del d['a']🔁 반복문 활용
for key in d:
print(key, d[key])
# 혹은
for key, value in d.items():
print(f"{key}: {value}")
🧪 자주 쓰는 함수
| 함수 | 설명 |
|---|---|
d.get('key') | 키가 없을 때 에러 대신 None 반환 |
d.keys() | 키 목록 반환 |
d.values() | 값 목록 반환 |
d.items() | (키, 값) 튜플 목록 반환 |
d.clear() | 딕셔너리 전체 비우기 |
📌 활용 예시 (트리, 그래프, 카운팅 등)
# 빈 딕셔너리 + 루프 활용
count = {}
for ch in 'banana':
count[ch] = count.get(ch, 0) + 1
print(count) # {'b': 1, 'a': 3, 'n': 2}
🧠 딕셔너리 vs 리스트
| 구분 | 딕셔너리 (dict) | 리스트 (list) |
|---|---|---|
| 인덱스 | 키(Key)로 접근 | 숫자(Index)로 접근 |
| 데이터 구조 | 키-값 쌍 | 순서 있는 값들의 집합 |
| 검색 속도 | 평균 O(1) (빠름) | O(n) (느림) |
챗 지피티의 도움을 받아서 딕셔너리에 대한 정보를 얻어볼 수 있었다.
그래프를 인접리스트 방식으로 구현하거나,
트리를 표현할 때는 파이썬에서 딕셔너리 자료형을 많이 쓴다고 한다. 잘 익혀놓아야겠다.
^_^