2025.03.15
TIL(TODAY I LEARN)
WEEK01 :
배열, 문자열, 반복문과 재귀 함수, 복잡도(BigO,시간,공간), 정렬, 완전 탐색, 정수론
첫주차의 이론 키워드들이다.
이론 공부를 해보자
어제 기존에 알고있던 지식으로 알고리즘 문제풀이를 해보았는데
재귀함수 n-queen 문제에서 벽을 느꼈다..
하노이탑에서는 어찌어찌 해낼 수 있었는데
자료구조와 함계 배우는 알고리즘 입문 책과 함께이론을 다시 해보자😊
📖 1. 알고리즘 기초
입출력 기본
int(문자열,진수) 입력하면 N진수 정수형으로 변경 가능
문자열
파이썬에서는 문자열의 곱연산이 된다.
ex)
print('*' * 5)
> *****두 값 교환하기
파이썬에서는 temp 설정안하고 그냥 튜플 형식으로 바로 교환 가능
a,b = b,a반복문에서 효율을 생각하자
같은 결과를 내는 코드라도 반복문안의 if문을 최소화하는 방향으로
파이썬의 변수
파이썬에서는 데이터, 함수, 클래스, 모듈, 패키지 등 모두 '객체(object)'로 취급
객체 - 자료형을 가짐, 메모리를 차지함
다른 프로그래밍 언어와 다르게 변수에 값을 복사하는 개념이 아니라
객체를 변수가 참조하는 형태
ex)
n = 17
c언어
int 형 변수 선언 후 17이라는 값을 복사함
----
| n | <-- 17
----파이썬
이미 존재하는 17이라는 객체를 n이라는 이름으로 참조
n(단순한 이름) --> 17(int형 객체)
------
n --> | 17 |
------ 이말인 즉슨 for i in range(1,100)의 경우에는
변수 i에 1~100까지 각 객체들이 i에 참조되는 것
따라서 파이썬에는 자료형을 선언 하지 않아도 자동으로 선언되는 효과를 가짐
📖 2. 기본 자료구조와 배열
리스트[list] / 튜플(tuple) / 집합{set}
-
리스트 : mutable(수정가능한) 객체 / [ ] 로 둘러쌈
튜플 : immutable(수정불가능한) 객체 / ( )로 둘러쌈 < 괄호 생략 가능 / 원소가 1개 일때 (1,) 와 같이 쉼표 필수
집합 : 중복된 값이 없는 mutable한 객체 / { }로 뚤러쌈 -
list 와 tuple은 unpack을 통해 대입을 편하게 할 수 있음
ex) a, b, c = [1, 2, 3] -
list 와 tuple은 index를 통해접근이 가능함
index는 0부터 시작
-1 index는 맨 뒤의 원소를 의미 -
리스트 슬라이싱 list[start : end : step]
슬라이싱에서
s = [0, 1, 2, 3, 4, 5, 6]
s[:3] → [0, 1, 2]
s[3:] → [3, 4, 5, 6]
s[::2] → [0, 2, 4, 6]
s[1::2] → [1, 3, 5]
s[::-1] → [6, 5, 4, 3, 2, 1, 0] ← 역순!
| step 값 | 방향 조건 | (start, stop) |
|---|---|---|
| > 0 | 오른쪽 → | start < stop 이어야 순회 발생 |
| < 0 | 왼쪽 ← | start > stop 이어야 순회 발생 |
-
리스트를 함수의 인자로 넘기면?
파이썬에서 함수는 참조(주소)를 넘겨 받기 때문에 인자가 mutable / immutable 한지 판단해 동작이 달라짐함수에 인자를 전달할때
mutable하면? 내부값 변경됨 (원본이 변경됨)
immutable하면? 새로운 객체를 생성함
-> call by object refernce(객체 참조에 의한 전달) -
깊은 복사(deep copy) vs 얕은 복사(shallow copy)
위와 비슷한 개념 리스트를 복사할때 그냥 copy를 하게 되면 주소값만 참조하기 때문에 참조값만 복사하는 얕은 복사가 됨
새로운 객체를 만들고 싶다면
import copy
x = [1,2]
y = copy.deepcopy(x)
print(y)위와 같이 deepcopy를 수행해야 완전히 새로운 리스트 객체를 만들 수 있음
- enumerate(list, 시작숫자)
시작숫자를 설정하게 되면 출력되는 index의 시작숫자를 바꿀 수 있음
📖 3. 검색 알고리즘
선형 검색
배열에서 index 0부터 배열의 끝까지 순차적으로 순회하면서 검색을 진행함
for or while 문을 사용해서 전체를 순회함
- 보초법(sentinel mehod)
선형 검색은 반복할 때마다 2개의 종료 조건(배열의 끝= 검색 실패, 검색 성공 // if문이 두개)을 가짐
종료조건을 검색하는 비용을 무시할 수 없음
-> 반복문 내의 조건문을 줄이자
-> 비용을 반으로 줄이는 보초법찾고자 하는 배열의 끝에 검색하고자하는 키값을 넣어서
배열의 끝을 검사하는 if 문을 없애버려 cost를 반으로 줄이자!
=> 결론적으로 찾아냈을 때 index가 len(list)와 같으면 검색값이 존재하지 않는 것
이진 검색
이미 정렬된 배열에서 중앙 원소를 기준으로 절반씩 나누어 찾는 법
find(9)
list = [1,2,3,4,5,6,7,8,9,10] <- 오름차순으로 정렬된 배열
1,2,3,4,5 / 6,7,8,9,10
검색범위에서 제외 / 검색범위
6,7,8 / 9, 10
검색범위에서 제외 / 검색범위
9 / 10
검색 성공!- 시간복잡도(time complexity) / 공간복잡도(space complexity)
실행시간을 평가 / 메모리 공간이 얼마나 필요한가
내가 참고한 설명
big-O Notation
이진탐색의 시간복잡도
전체 데이터의 수를
N 이라고 하자.
1) 첫 번째 탐색 후 절반만 남아 남은 수가
N/2개.
2) 두 번째 탐색에서 다시 절반만 남아 남은 수가
N/2 × 1/2개.
3) 세 번째 탐색에서 다시 절반이 남아 남은 수가
N/2 × 1/2 × 1/2개.
k) 규칙을 찾아보면 k번째 탐색에서 남은 데이터 수는
(1/2)^k × N 이 된다.
k에 대해서 정리하면 k = logN
k의 시간복잡도는 O(logN)해시법
어렵다 추가 공부 요망
저장소에 바로 저장하는게 아니고 해시 테이블이라는 저장장소를 바로 가리키는 저장장소를 만들어서 어디에 있는지 알려줌
collision 발생 시 처리 기법으로는 두가지(체인법, 오픈 주소법) 존재
보통 해시테이블은 나머지 연산을 이용하여 만들고
체인법
충돌이 발생한 위치에 연결리스트를 이용해 계속 붙여나감
노드는 키, 값, 다음 노드를 가짐
오픈 주소법
충돌이 발생하면 다음 해시테이블 위치를 보고 비어있다면 거기에 넣음.
다음 위치도 비어있지 않다면 다다음 위치로 이동
📖 4. 스택과 큐
스택
LIFO( Last In First Out) : 후입 선출
스택 포인터( ptr ) : 현재 스택 안에 있는 데이터의 개수를 나타내는 정숫값
- 구현시
push() : 스택에 데이터를 넣음
pop() : 스택에서 데이터를 꺼냄
is_empty(), is_full(),len() 등 구현 필요
큐
FIFO( Fisrt In First Out) : 선입 선출
-
구현시
enqueue() : 큐에 데이터를 넣음
dequeqe() : 큐에서 데이터를 꺼냄
front / rear : 데이터를 꺼내는 쪽 / 데이터를 넣는 쪽우선순위 큐
-
인큐할 때 : 데이터에 우선순위를 부여해 추가
디큐할 때 : 데이터의 우선순위가 높은 데이터를 꺼냄heapq 모듈을 통해 구현가능
링 버퍼를 이용한 큐 구현(원형 큐)
front와 rear 위치만을 옮겨 인큐와 디큐를 수행할 수 있음.
-
collection.deque를 통해 스택과 큐를 간단하게 구현 가능함.
from collections import deque
📖 5. 재귀 알고리즘
재귀(recursion) 함수 : 어떤 원소에 대한 함수의 결과를 다시 원소로 삼는 함수
-
팩토리얼 , 유클리드 호제법
재귀 알고리즘 분석
def recur(n): if n> 0: recur(n-1) print(n) recur(n-2) recur(4)하향식 분석
가장 위쪽에 위치한 함수의 호출부터 아래로 내려가면서 분석
recur(4)의 실행순서 1 recur(3) 2 print(4) 3 recur(2)상향식 분석
아래쪽부터 쌓아 올리며 분석
recur 함수는 n이 양수일때만 실행하므로 recur(1)부터 분석
recur(1)의 실행순서
1 recur(0)
2 print(1) -> 이것만 수행됨
3 recur(-1)
recur(2)의 실행순서
1 recur(1)
2 print(2) -> 이것만 수행됨
3 recur(0)
1 2 가 출력됨을 알 수 있음
recur(4)까지 쌓아올리며 분석을 진행추천 문제 : 백준 1914: 하노이 탑, 9663: N-Queen
