CS+PS27 [알고리즘] 정렬 (선택, 삽입, 퀵정렬..) 정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.(ex. 오름차순, 내림차순) 정렬 알고리즘으로 데이터를 정렬하면 다음장에서 배울 이진탐색(binary search)가 가능해진다. 정렬 알고리즘은 이진탐색의 전처리 과정이라고도 볼 수 있다. 코딩테스트를 대비하기 위해선 크게 5가지 정렬 방법에 대해서 알고 있으면 좋다! 선택정렬 / 삽입정렬 / 퀵정렬 / 계수정렬 / 파이썬 기본 라이브러리 정렬 정렬 알고리즘은 알고리즘 전공 시간때 배운바 있는데, 그때는 c++ 위주로 알고리즘 의사코드를 통해 공부를 했었다.(중간고사 대비를 위해 pseudocode 전체를 외웠던 악몽이...) 그 기억을 떠올려보면서 python에서의 코드 구현에는 어떤 이점이 있는지 알아보고 싶은 .. 2023. 11. 13. [알고리즘] BFS/DFS (feat. stack, queue) 꼭 필요한 자료구조 기초 BFS/DFS를 들어가기에 앞서, 데이터를 표현하고 관리하기 위한 구조에 대해서 간단히 얘기해보고 넘어가자. Stack 박스 쌓기에 비유할 수 있다 선입후출, 후입선출 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하기 동작한다. Queue 대기줄에 비유할 수 있다. 선입선출 구조 파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자. deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다. 큐와 같은 경우 push_bac.. 2023. 10. 11. [C++] 연결리스트 (feat.바킹독) 연결 리스트의 정의 연결 리스트란, 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 연결 리스트의 성질 k 번째 원소를 확인/변경하기 위해 O(k)가 필요 (배열과 다르게 공간에 원소들이 연속해서 위치하고 있지 않기 때문) 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) ⭐️ 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트의 종류 단일 연결 리스트: 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트 이중 연결 리스트: 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘다 들고 있다. 단일 연결 리스트에서는 주어진 원소의 이전 원소가 무엇인지를 알 수 없는데, 이중 연결 리스트에서는 .. 2023. 9. 19. [C++] 배열 (feat. 바킹독) 배열의 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양(오버헤드)가 거의 없음 cache hit rate가 높음 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 시간 복잡도 임의의 위치에 있는 원소를 확인/변경 : O(1) 원소를 끝에 추가/제거 : O(1) 임의의 위치에 원소를 추가/제거 : O(N) 실제로 임의의 위치에 원소를 추가/제거하는 함수를 작성해보자 void insert(int idx, int num, int arr[], int& len){ len++; int tmp; for(int i=len; i>idx; i--){ //맨 끝에서부터 반복문 arr[i] = arr[i-1]; } arr[idx]=num; } void erase(int idx, int .. 2023. 9. 13. [알고리즘]구현 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 구현 하기 까다로운 문제 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력해야하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는(파싱을 해야 하는) 문제 등 알고리즘 중 "구현"은 어떻게 풀면 될지 대략 감은 오는데, 막상 코드로 옮기려니 무엇부터 작성해야 할지 모를 수 있다.. 또한 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀 때 불리하다. 예를 들어, 파이썬으로 코테를 보는데 N개의 원소가 들어 있는 리스트에서 R개의 원소를 뽑아 한줄로 세우는 경우(순열)을 구해야 하는 문제를 만나면 어떻게 할것인가?? 무작정 기능을 전.. 2023. 9. 13. [알고리즘]그리디 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 🧤 그리디(탐욕법)이란? ⇒ 나머지 경우의 수를 다 제쳐두고 가장 최선의 방법 한개만 파고 들어서 문제를 푸는 방법이다. 예를 들면 최소동전 문제가 있다. (ex. 동전으로 1400을 만들때 동전을 가장 적게 쓰는 경우의 수 찾기) ⇒ 매 순간 가장 좋아보이는 방법을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 💡 그리디문제는 이 문제가 그리디인가? 반례가 있는것은 아닐까? 라는 고민하는 것이 가장 어렵다고 한다. 그래서 끊임없이 이 문제를 그리디로 풀 수 있는지, 반례가 있을지 없을지 고민하는것이 정상이라고 한다. 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다. 대표적인 문제 유형이 "거스름돈을 동전으.. 2023. 9. 11. 이전 1 2 3 4 5 다음
