Share
Sign In
TIL 웹개발 - 알고리즘이란?
서경태
파이썬 과정을 마치고 알고리즘과 자료구조에 대한 강의를 시작했다.
알고리즘이란?
같은 문제를 풀더라도 공간적으로 시간적으로 더 효율적으로 풀기 위한 것
시간 복잡도
입력값과 문제를 해결하는데 걸리는 시간과의 상관관계를 말한다. 입력갓이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 ㅐ로 늘어나는지 보는 것.
공간 복잡도
입력값과 문제를 해결하는데 걸리는 공간과의 상관관계를 말한다. 입력값이 2ㅐ로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것.
점근 표기법
알고리즘의 성능을 수학적으로 표기하는 기법으로 알고리즘의 '효율성'을 평가하는 방법이다.
빅오(Big-O) 표기범
최악의 성능이 나올때 어느정도 연산량이 걸릴지
표기 방법: O(N)
N은 얼마나 계산하냐를 말하기 때문에 for문이 한번 있으면 O(N)으로 사용하고 for문이 2개 중첩된 알고리즘은 O(N제곱) 으로 표기한다.
빅 오메가(Big -Ω) 표기법
최선의 성능이 나올때 어느정도의 연산량이 걸릴지
표기 방법: Ω(1)
빅 오메가는 거의 사용하지 않는다. 왜냐하면 보통 최악의 경우를 대비하기때문. 최선은 가장 좋으면 1이지만 최악은.... 상상하기 싫다.
알파벳 찾기 문제
작동은 하는데.... 해설을 보니 좀 변태같이 푼것 같다.
화이팅...
💬
오늘의 교훈!
구현을 많이 해보자
/kyugntae-ai
Subscribe
Other posts in 'TIL 웹개발'See all
TIL-웹개발 리스트(list)와 세트(set)의 시간 복잡도 차이
백준 11725번 문제를 푸는데 계속해서 시간초과로 난항을 겪고 있었다. 이 문제를 풀기 위해 내가 짠 코드는 다음과 같다. 파이참에서 실행시켰을때는 입출력 예제와 똑같이 나왔기에 이제 여기서 줄일 만한 곳을 찾기 시작했다. graph를 딕셔너리로 만들었는데 리스트로 변경하면 좀 더 시간이 줄어들까 싶어 시도했지만 역시나 실패였다. 그후 몇 가지 시도를 하다보니 코드가 아예 틀리기도 했다. 결국 나는 그를 찾아갔다. 거의 솔루션은 간단했다. 리스트(list)를 세트(set)로 변경하는 것이다. 위 코드 중 일부를 보면 입력값을 받아 그래프를 만든 후 부모 노드를 찾기 위해 bfs를 사용했다. def bfs_queue(start): parent = [0] * (n+1) visited = [start] q = deque([start]) while q: node = q.popleft() for adj in graph[node]: if adj not in visited: parent[adj] = node q.append(adj) visited.append(adj) def bfs_queue(start): parent = [0] * (n+1) visited = set([start]) q = deque([start]) while q: node = q.popleft() for adj in graph[node]: if adj not in visited: parent[adj] = node q.append(adj) visited.add(adj) visited는 방문한 노드를 중복 방문하지 않기 위해 만든 리스트다. if문에 인접 노드가 이미 visited에 없다면 아래 코드를 반복해서 실행한다. 이때 if adj not in visited의 시간 복잡도는 O(n)이다. 하지만 visited를 세트(set)로 바꾸면 시간 복잡도는 O(1)이 된다. 리스트와 세트의 연산 차이점을 나타낸 표를 참고해보면, 리스트(list)
서경태
TIL 웹개발 - 파이썬 scope
Scope 파이썬에서 변수의 유효 범위를 말한다. 위치에 따라 작성한 코드가 작동하거나 작동하지 않을 수도 있고 때로는 원하는 대로 값이 안나올 수도 있다. 변수의 위치를 알맞게 작성해야 한다. LEGB rule 이 규칙에 따라 순서대로 작동한다. Local scope 함수 내부에서 선언된 변수나 함수로 그 범위에만 유효하다. Enclosed scope 외부함수에 정의되었지만 내부함수까지 사용된다. 주로 중첩 함수가 정의될 때 사용된다. Global scope 외부에 선언된 변수로 전체적인 범위에 유효하다. Built-in scope 파이썬 설치 파일 안에 바로 내장된 것으로 별다른 선언없이 실행된다. ex) len(), input(), print() 등
서경태
TIL 웹개발 - 해시테이블
해시테이블(해시 맵) 키, 밸류 구조로 딕셔너리형태의 자료형 자료를 저장하고 검색하는데 사용하는 중요한 기법 좋은 해시 함수의 조건 해시 함수 값 충돌의 최소화 쉽고 빠른 연산 해시 테이블 전체에 해시 값이 균일하게 분포 사용할 키의 모든 정보를 이용하여 해싱 해시 테이블 사용 효율이 높아야함 로드 팩터 해시테이블에 저장된 데이터 개수 n을 버킷의 개수 k 로 나눈 것 로드 팩터 비율에 따라 해시 함수를 재작성 할지, 크기를 조정할 지 결정한다. 로드팩터가 증가할 수록 해시 테이블 성능은 점점 감소하기에 해시테이블의 공간을 재할당한다. 해시 함수 해시 함수를 통해 키가 해시 값으로 변경되는 과정을 도식화 한 것이다. 윤아와 서현의 값은 해시 함수를 통해 동일한 2를 가지며 충동한 것을 알 수 있다.
서경태