파이썬(일부분 코틀린)으로 구현한 알고리즘, 자료구조(이론, 알고리즘 테스트)를 한눈에 볼 수 있도록 유형별로 정리한 게시글입니다. 알고리즘과 자료구조 이론 알고리즘 정렬 파이썬으로 정렬 알고리즘 구현하기 검색 자료구조 정리본 : 파이썬으로 자료구조 구현하기 Hash (해시) Stack (스택) Queue (큐) Heap (힙) 알고리즘 테스트 문제 알고리즘 그리디 알고리즘 정렬 [Programmers] 정렬 - 가장 큰 수 찾기 [Programmers] 정렬 - H Index 자료구조 해시 Python 에서는 Dictionary, Set 이용 [Programmers] 해시 - 완주하지 못한 선수 [Programmers] 해시 - 전화번호 목록 ㅇ

/* 본 게시물은 ' 이것이 코딩 테스트다 with Python | 나동빈 ' 의 내용과 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ # 그리디 알고리즘 그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형' 이라는 특징이 있다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족 시킬 수 있으므로 그리디 알고리즘 문제는 자주 정..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [BoostCourse] 자바로 구현하고 배우는 자료구조 - 힙 정렬 : https://www.boostcourse.org/cs204 힙 정렬 힙 규칙에 맞게 숫자의 순서를 맞추는 과정을 힙 정렬 알고리즘이라고 한다. *힙에 대해 자세히 알고 싶다면 다음 글을 확인하면 된다. 만약 데이터가 힙 규칙에 따라 있다면, trickleDown을 반복하면 숫자들이 정렬된다. 이때 최대힙 이면 오름차순으로, 최소힙이면 내림차순으로 정렬된다. 코드는 다음과 같다. fun heapSort(): E{ val removeVal = array[1] as E if (arr..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [BoostCourse] 자바로 구현하고 배우는 자료구조 - Heap : https://www.boostcourse.org/cs204 1. 힙이란? 힙은 '최댓값 및 최솟값을 찾아내는 연산'을 빠르게 하기 위해 고안된 '완전이진트리를 기반으로 한 자료구조'이다. 완전이진트리 조건 1. 마지막 레벨을 제외한 모든 노드가 채워져야한다. 2. 모든 노드들은 왼쪽부터 채워져야한다. 힙에는 최대 힙(max heap)과 최소 힙(min heap)이 있다. 부모 노드가 자식 노드보다 크면 최대 힙, 반대이면 최소 힙이다. 가장 큰 숫자가 뿌리에 있게 하려면 최대 ..

/* 본 게시물은 ' ' 의 내용과 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 15650번 - N과 M (2) : https://www.acmicpc.net/problem/15650 [AeroCode] 순열과 조합 알고리즘 : https://aerocode.net/376 1. 조합이란? 표현 : nCr 정의 : 서로 다른 n개 중의 r 개를 뽑을때, 순서의 상관없이 뽑는 경우의 수 예시 : [1,2,3,4] 중 2개 뽑을 때 [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] 2. 조합 구현 백준 15650번 문제를 통해 조합을 구현해보자. 문제 자연수 N과 M이 주어졌을 때, ..

/* 본 게시물은 ' ' 의 내용과 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [AeroCode] 순열과 조합 알고리즘 : https://aerocode.net/376 [백준] 15649번 - N 과 M (1) : https://www.acmicpc.net/problem/15649 1. 순열이란? 표현 : nPr 정의 : 서로 다른 n개 중의 r개를 뽑을 때, 순서를 포함한 경우의 수 예시 : [1, 2, 3] 배열의 순열 경우의 수 [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] 2. 순열 구현 (with 백준 15649번) 문제 자연수 N과 M이 주..

/* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 18258번 - 큐2 : https://www.acmicpc.net/problem/18258 1. 큐(Queue)란? 큐는 스택과는 반대로 입력과 출력 창구가 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나오는 자료구조(First In First Out / 선입 선출)이다. 이는 우리가 먼저 온 차례대로 줄을 세우는 것과 같다. 큐는 작업을 처리하는 요소에 부하를 주지 않으면서도 처리 능력을 넘어서는 작업들을 놓치지 않고 수용할 수 있게 한다. 이러한 특성으로 큐는 '완충장치(대기열)'로 사용되는 경우가 많다. 큐의 기능 스택과 마찬가지로 큐의 주요 기능도 삽입(Enqueue), 제거(De..

/* 본 게시물은 ' 뇌를 자극하는 알고리즘 | with 박상현 ' 의 내용과 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 10028번 - 스택 : https://www.acmicpc.net/problem/10828 1. 스택이란? '스택'의 사전적 의미는 건초나 짚더미와 같은 뭔가를 쌓아놓은 더미를 뜻한다. 자료구조의 스택 또한 데이터를 아래에서부터 위로 쌓아 얹어 올리도록 하는 자료구조이다. 스택은 중간에 데이터를 삽입하거나 삭제하는 것을 허용하지 않는다. 데이터의 입/출력은 오로지 스택의 꼭대기에서만 이루어진다. 즉, 스택은 '선입후출' (First In - Last out) 의 특징을 가진다. 스..

/* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 1929번 - 소수 구하기 : https://www.acmicpc.net/problem/1929 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 1. Mysolution 기존에 내가 소수를 구하는 방식은 다음과 같다. 소수는 1과 자기 자신만을 약수로 가진다. -> 2부터 N-1 까지의 수로 나누었을 때 나머지가 0이 되면 안 된다. 위 방식을 코드로 구현하면 다음과 같다. fun isPrimeNum(n : Int):..

/* 본 게시물은 ' BoostCourse - 자바로 배우는 자료구조 ' 의 내용과 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [genius-dev] Linked List에 대하여 : https://genius-dev.tistory.com/entry/Kotlin%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-List%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC1-%EA%B5%AC%ED%98%84%EA%B3%BC-%ED%95%A8%EA%BB%98 1. Linked List 구조 이번에는 코틀린으로 Linked List를 구현해보자. (LinkedList 에 대한..

/* 본 게시물은 ' BoostCourse - 자바로 구현하고 배우는 자료구조 - 경계조건 ' 의 내용과 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [URL] : https://www.boostcourse.org/cs204/lecture/625940 우리가 자료구조를 만들 때 생각해야하는 것을 '경계 조건' 이라 한다. 그러면 경계 조건에는 무엇이 있을까? 자료 구조가 비어있는 경우 자료 구조에 단 하나의 요소가 들어있을 때 자료 구조의 첫 번째 요소를 제거하거나 추가할 때 자료 구조의 마지막 요소를 제거하거나 추가할 때 자료 구조의 중간 부분을 처리할 때 예시로 우리가 첫 번째 요소를 제거(추가)한다고 가정해..

참고 자료 [BoostCourse - cs50 - linked list] : https://www.boostcourse.org/cs112 [초보몽키의 개발공부로그] Array와 리스트 : https://wayhome25.github.io/cs/2017/04/17/cs-18-1/ [Java의 LinkedList와 ArrayList 에 대한 비교] : https://www.holaxprogramming.com/2014/02/12/java-list-interface/ [에러지우개] Array vs ArrayList : https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Array-vs-ArrayList #List 이번에 공부할 자료구조는 Lis..