[Algorithm] 순차 탐색(Sequential Search)과 이진 탐색(Binary Search)

순차 탐색 앞에서부터 하나씩 차례대로 탐색하는 방법 array = [3, 1, 7, 5, 9] for i in range(len(array)): if array[i] == 7: print(i) break 리스트를 차례대로 순회하므로 시간 복잡도는 O(N)이다. 이진 탐색 정렬된 리스트에 대하여 찾으려는 데이터와 중간 지점의 데이터를 비교해나가며 탐색하는 방법 순차 탐색과 달리 정렬이 되어 있어야 사용할 수 있다. 중간이 정확히 안 나누어질 때는 소수점 이하를 버린다. 시간 복잡도는 O(logN)이다. 구현 def binary_search(array, target, start, end): while start array[middle]: start = middle + 1 elif target < array[..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 16.
• textsms

2020 부스트캠프를 마치고

상당히 늦은 수료 후기이지만... 그동안 배운 내용들을 정리하고 다시 되짚어보고 하느라 바빴당 😅 부캠과의 첫 만남 딱 부캠을 시작할 무렵 썼던 글을 찾았다. 이 전에는 정말 나 뭐 해 먹고 살지?라는 고민으로 매일매일 굴러다니며 살았던 것 같다. 막연히 코딩 너무 재밌는데? 하면서 컴퓨터공학과에 왔더니 몇 년을 다니고서도 막연히 이야! 코딩 너무 재밌다! 라고만 하고 있었기 때문이다. 챌린지 (7~8월) 선발 과정 챌린지 과정은 서류 전형, 1차 코딩 테스트, 2차 코딩 테스트를 거쳐 선발된다. 부스트캠프 5기는 코로나에 의해 부캠 최초로! 모든 과정이 온라인으로 진행되었기 때문에, 1차와 2차 코딩 테스트 역시 모두 온라인으로 치뤄졌다. 난이도는 어렵지는 않다. 정말 얘가 기본만큼은 확실하게 아는가?..

• format_list_bulleted 일상
• · 2021. 2. 16.
• textsms

[Python] 파이썬에서의 0, False, None

파이썬에서 정수 0, boolean인 False, null로 사용되는 None의 성질이 궁금해져서 테스트해보았다. zero = 0 false = False none = None print(zero == false) # True print(false == none) # False print(zero == none) # False 결론적으로 0과 False는 같은 값으로 취급되나 None과는 모두 다른 값으로 취급된다. zero = 0 false = False none = None # print nothing if zero: print(&#39;zero&#39;) if false: print(&#39;false&#39;) if none: print(&#39;none&#39;) 또한 조건문에서는 위의 세 가지..

• format_list_bulleted 개발 일지/Python
• · 2021. 2. 6.
• textsms

[Algorithm] 정렬(Sorting)

정렬 알고리즘(Sorting Algorithm) 데이터를 일정한 순서대로 열거하는 알고리즘 어떤 정렬을 쓰냐에 따라 프로그램의 효율성이 좌지우지될 수 있다. 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬, 병합 정렬, 힙 정렬 정도까지는 알고 있으면 좋다. 선택 정렬(Selection Sort) 순회하며 제일 작은 데이터를 맨 앞으로 옮김으로써 왼쪽부터 정렬을 완성해가는 방식 코드 def selection_sort(array): for i in range(len(array)): min_index = i for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = arra..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 2.
• textsms

[Algorithm] DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

사전 지식 탐색 많은 양의 데이터 중 원하는 데이터를 찾는 과정 자료구조 데이터를 표현하고, 관리하고, 처리하기 위한 구조 스택과 큐에 대해 잘 모른다면 아래 글을 참고할 것 2021/02/01 - [개발 일지/Algorithm] - 파이썬에서의 스택(Stack)과 큐(Queue) 재귀함수 자기 자신을 호출하는 함수. 수학의 점화식을 코드화한 것 점화식: 특정 함수를 자기보다 더 작은 변수와 함수의 관계로 표현한 것 재귀 함수는 점점 작아지는 자기 자신 + 종료 조건을 통해 동작한다. 그래프 그래프에 대해 잘 모른다면 아래 글을 참고할 것 2021/02/01 - [개발 일지/Algorithm] - [Data Structure] 그래프(Graph) DFS (깊이 우선 탐색, Depth-First Searc..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 1.
• textsms

[Data Structure] 그래프(Graph)

그래프(Graph) vertex(정점)과 edge(간선)으로 이루어진 자료구조 프로그래밍에서 이를 표현하는 방식으로는 인접 행렬과 인접 리스트가 있다. 인접 행렬 2차원 배열로 그래프의 연결 관계를 표현 INF = 987654321 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] # 0과 1의 연결 관계 graph[0][1] ( == graph[1][0]) 인접 리스트 연결 리스트 자료구조로 그래프의 연결 관계 표현 파이썬에서는 일반 리스트 자료형이 연결 리스트의 역할을 하므로 다음과 같이 구현한다. vertex = 3 graph = [[] for i in range(vertex)] # 0번 간선과의 연결 정보 graph[0].append((1, 7)) graph[0..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 1.
• textsms

[Data Structure] 파이썬에서의 스택(Stack)과 큐(Queue)

스택(Stack) 후입선출(LIFO) 구조라고도 한다. 나중에 들어온 게 먼저 나간다. 파이썬에서는 다음과 같이 리스트 자료형을 통해 구현할 수 있다. stack = [] stack.append(0) # [0] stack.append(1) # [0, 1] stack.pop() # [0], return 1 큐 (Queue) 선입선출(FIFO) 구조라고도 한다. 먼저 들어온 게 먼저 나간다. 파이썬에서는 큐를 구현하기 위해 collections 모듈의 deque(덱)을 이용한다. 덱(deque)이란 스택과 큐를 합친 자료구조로, 양 방향에서 삽입/삭제가 가능하다. from collections import deque queue = deque() queue.append(0) # [0] queue.append(..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 1.
• textsms

[Algorithm] 구현(Implementation)

구현 알고리즘 실생활의 문제를 코드로 나타내 해결하는 방식 완전 탐색과 시뮬레이션 유형으로 나뉜다. 완전 탐색 (Brute-force search) 모든 경우의 수를 다 계산하는 방식 즉 로직을 간단하게 하기 위해 시간, 공간 복잡도를 늘리는 방식이다. 따라서 주어진 입력의 범위가 적을 때만 사용해야 한다. 시뮬레이션 (Simulation) 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행하는 방식 자주 등장하는 유형 실생활의 문제를 코드로 나타내기 위해서는 수식화 단계를 거쳐야 한다. 좌표로 나타내기 이동 가능한 경로를 계산하는 등의 방식에서 사용된다. # 상하좌우 dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] literal = ['Up', 'Down', 'Left', 'Righ..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 1.
• textsms