기록과 정리

얼마 전 정렬 알고리즘의 기본적인 5가지를 알아보았다. ( 선택, 삽입, 버블, 합병, 퀵 ) 하지만 빠르다는 합병이나 퀵의 시간 복잡도는 O(nlogN)으로 더 빠른 정렬이 있다는 사실을 알게되었고 , 그러한 알고리즘으로 Counting Sort에 대해 정리해보려한다. ( Counting Sort의 시간복잡도는 O(n)) 소개 앞서 소개한 5개의 알고리즘 ( 하단 글 참고 )https://zepettoworld.tistory.com/71 정렬알고리즘 얼마 전 , 정렬알고리즘의 공부 필요성을 느끼고 이 글을 정리한다. 정렬 알고리즘 정렬알고리즘이란 원소들을 번호 순이나 사전순서대로 일정한 순서대로 열거하는 알고리즘 을 말한다. 이때 zepettoworld.tistory.com 에서 O(n²)의 시간복잡도..

얼마 전 , 정렬알고리즘의 공부 필요성을 느끼고 이 글을 정리한다. 정렬 알고리즘 정렬알고리즘이란 원소들을 번호 순이나 사전순서대로 일정한 순서대로 열거하는 알고리즘 을 말한다. 이때 두 조건을 만족해야하는데, 1. 출력은 비 내림차순 2. 출력은 입력을 재배열하여 만든 순열이다. 예를 들어 [ 5, 3, 4, 1, 6, 2 ] 이라는 배열이 있을 경우, 결과값은 [1, 2 ,3 ,4 ,5 ,6] 이 나오도록 일련의 과정을 거친다. 이 과정을 우리는 정렬알고리즘이라고 부르며 이에 해당하는 조사된 정렬알고리즘의 종류는 삽입, 선택, 합병, 힙, 퀵,타임....... 1956년 거품정렬 분석과 더불어 지금까지도 발명되고 발견되고 있다. 많은 정렬알고리즘을 알고 있으면 좋으나.. 기본적인 5가지의 정렬알고리즘..

그래프 DFS와 BFS를 설명하기 앞서 자료구조인 '그래프'를 이해해야 한다. 그래프란 단순히 노드와 그 노드를 연결하는 간선으로 이루어진 비선형 자료구조이다. DFS Depth-First Search , 깊이 우선 탐색으로 위 그래프 기준으로 설명을 해보도록 한다. 위 그래프를 DFS로 탐색을 하게 된다면 다음과 같은 순서를 가지게 될 것이다. DFS 구현의 주로 스택과 재귀함수를 사용하는데, 탐색 순서는 다음과 같다. 주로 재귀함수를 사용해서 보편적인 풀이를 이끌어 낸다. 1. 1번에서 2번, 3번, 4번을 순차적으로 탐색 2. 4번에서 더이상 찾을 순번이 없기 때문에 2번의 다른 노드인 5번을 탐색 3. 5번에서 더 이상 찾을 순번이 없기 떄문에 6번, 7번 순으로 탐색 BFS Breadth-Fi..

그리디(Greedy) 알고리즘은 이름에서 나온 것 같이 '탐욕적으로 당장의 눈 앞에 보이는 최고의 결과만을 구하려는 알고리즘' 이다. 여러 경우 중 하나를 결정해야할 때마다 그 순간 최적의 것이라고 생각되는 것들을 선택해야하는데 이는 항상 최적의 결과만을 가져오지는 않는다. 무슨 말인고.. 하면 이는 동적계획법(Dynamic Programming)과 비교가 되는 경우가 많은데, 우리 약속에 의해 어떤한 길을 찾는다고 가정해보자. 서울->대전 , 대전->부산 - 서울에서 대전을 갈 경우 세 갈래 길이 나왔다. 첫번째 길 부터 차근 차근 탐색해본다. ( Dynamic Programmin ) , 아니다 본능적으로 직진길이 우선이다 (Greedy) . - 대전까지는 직진을 했다. 다행히 제일 빠른 길이였고 대전..

해시(hash) 해시? 해시는 key-value 의 형태로 이루어져 있는 자료구조를 말한다. 파이썬에서의 해시 구현 파이썬에서의 해시 구현은 딕셔너리를 이용한다. 배열은 [] , 튜플은 () , 딕셔너리는 {}의 형태를 가지고 있으며 다음과 같은 선언 방식을 가진다. value = { 'color' : 'green', 'name' : 'smyoo' } color라는 키값의 green이라는 value, name이라는 키값에 smyoo라는 value값을 가진다. 이하 파이썬에서 자주 사용하는 해시 사용법 - value[color] = red -> color라는 키 값에 red 라는 value 할당 - value.keys() -> 키를 전부 리스트 형태로 호출 - value.values() -> 값을 전부 리..

스택 (stack)? - LIFO(Last In First Out) 후입선출 - Push&Pop 으로 자료를 넣고 꺼내는 작업을 할 수 있다. - 파이썬은 스택 자료구조는 따로 제공하지 않는다. 다만 기본 클래스인 list를 통해 스택을 흉내 낼 수 있다. Stack - push 스택에 원소를 넣을 때에는 append 메서드를 이용해 리스트의 가장 마지막에 원소를 넣도록 한다. Stack - pop 스택에서 원소를 제거할 때에는 pop 메소드를 이용해 리스트의 가장 마지막 원소를 제거해준다. 이때, pop 메서드에 의해 제거한 원소를 리턴 받을 수 있다. Stack - top 스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1]을 이용하도록 한다. https://www.acmicpc.net/pro..