본문 바로가기

컴퓨터/알고리즘24

알고리즘 문제 풀이 순서, 공부 방법 (2) - 전공자/문제풀이 초보 지난 글에서는 알고리즘 문제 풀이 공부 방법에 대해서 비전공자/문제풀이 처음이신 분들을 기준으로 어떤 문제들로 시작해서 문제풀이를 해보면 좋을지, 문제 풀이 시간과 문제 수에 대해 간단하게 작성했다 (이전글) https://waytocse.tistory.com/114 알고리즘 문제 풀이 순서, 공부 방법 (1) - 비전공자/문제풀이 처음 SSAFY멘토링을 진행하면서 많은 분들이 '비전공자로서 문제풀이 로드맵', '공부 방법 혹은 순서', '공부하는 법'을 궁금해한다는 것을 알게 됐다. 전공자도 처음 시작한다면 그러하겠지만 비전공 waytocse.tistory.com 이번 글에서는 전공자이거나 문제 풀이 경험이 적은 분들에 대해서 코딩테스트 대비 알고리즘 문제 풀이를 공부하는 방법에 대해서 글을 써보고자한.. 2024. 3. 25.
알고리즘 문제 풀이 순서, 공부 방법 (1) - 비전공자/문제풀이 처음 SSAFY멘토링을 진행하면서 많은 분들이 '비전공자로서 문제풀이 로드맵', '공부 방법 혹은 순서', '공부하는 법'을 궁금해한다는 것을 알게 됐다. 전공자도 처음 시작한다면 그러하겠지만 비전공자로서 PS에 입문하시는 분들은 정말로 뭐부터 해야할지 모를 수 있겠구나 깨달았다. 그래서 교육생분들께 관련하여 소개할 컬럼을 작성하면서 블로그에도 글을 남겨본다. 나 역시 알고리즘 문제 풀이 전문가도아니고 실력자도 아니지만, 오히려 그렇기 때문에 나의 처음과 비슷한 시작점에 계신 분들에게는 같은 눈높이에서 적힌 글이 될거고, 도움이 되지 않을까..하고 기대해본다. 목차 1. 알고리즘 공부 방법 1-1. 비전공자이거나 문제풀이가 처음인 분 1-2. 전공자이거나 문제풀이 경험이 적은 분 1-3. 문제풀이를 꽤 해봤으.. 2024. 3. 24.
[C언어] Heap기반 연결리스트(Linked list) 연결리스트 목차 연결리스트 구조체 선언 연결리스트 CRUD 이중 연결 리스트 이중 연결 리스트 CRUD Heap으로 구현한 연결리스트 Heap으로 구현한 이중 연결 리스트 동적 할당 기반 연결리스트 동적할당을 하면 Heap 공간에 데이터가 저장된다. 이전에 다뤘던 배열기반 연결리스트는 데이터 공간을 미리 선언해두고 이용했기 때문에 데이터의 수를 삽입/삭제할 때 유동적으로 융통성있게 활용하는 것이 어려웠다. 그래서 이번에는 calloc을 이용해서 연결리스트를 구현해보고자한다. 동적할당이기 때문에 자료를 삭제할 때 free를 해주어서 메모리 공간을 다시 확보해줘야 하는 것을 기억해야한다. C언어  동적 할당 기반 연결리스트 구현 간단히 새 노드를 삽입하여 연결하는 부분만 살펴보면 다음과 같다. //새노드 .. 2022. 7. 12.
[C언어] 배열 기반 연결리스트(Linked List) 연결리스트 목차 연결리스트 구조체 선언 연결리스트 CRUD 이중 연결 리스트 이중 연결 리스트 CRUD Heap으로 구현한 연결리스트 Heap으로 구현한 이중 연결 리스트 연결리스트 배열의 경우 자료를 읽기는 쉽지만 삽입/삭제는 어렵다. 많은 자료의 이동을 동반하기 때문이다. 이에 반해 연결리스트는 자료를 중간에 삽입하고 삭제하는데 꽤 편리하다. 연결리스트는 next라는 자기참조객체를 통해서 구현된다. 개체 하나를 삽입하고 싶다면 삽입할 위치의 전의 next 연결을 끊고 삽입하려는 개체와 연결한다. 삽입한 개체는 다음의 개체에 next연결을 넣는다. 삭제의 경우는 이전과 다음의 개체를 연결하고 삭제하려는 개체의 연결을 끊으면 된다. C언어 배열 기반 연결리스트 구현 C언어를 이용해서 배열기반의 연결리스트.. 2022. 7. 11.
Stack/Queue - 스택과 큐, 스택의 종류 스택과 큐는 선형자료구조(Linear List)이다. 스택은 LIFO(Last In First Out)구조로 동작한다. 먼저 들어 온게 쌓이고 나중에 들어온게 위로가서 나중에 데이터를 뽑을 때, 나중에 들어온 데이터가 먼저 나가는 형식으로 접시나 책을 쌓는다고 생각하면 이해하기 쉽다. 예시로는 아래와 같다. C언어로 구현할 때, 스택의 종류에는 4가지가 있음을 고려해 볼 수 있다. 종류를 나누는 기준은 2 가지가 있다. 1. SP(stack pointer)의 위치 - Data의 앞에 위치하느냐 (FULL), 빈 공간에 위치하느냐(Empty) 2. SP의 조작 - SP를 감소시키느냐 (Descending), 증가시키느냐 (Ascending) 이에 따라 스택은 FD stack, ED stack, FA sta.. 2022. 7. 10.
Binary Search - 이진 탐색 기법과 Lower/Upper bound 오름차순으로 정렬된 배열이 있다고 할 때 이 배열에서 원하는 값을 찾으려고한다. 얼마만에 찾을 수 있을까? 처음 값부터 끝 값까지 순차적으로 탐색한다고 했을 때, 경우를 나누어 보면 다음과 같을 것이다. 1. 최선: 원하는 값이 배열의 맨 앞에 있음 2. 최악: 원하는 값이 배열의 맨 끝에 있음 3. 평균: 가운데 특히나 배열의 크기가 클 수록 탐색이 어려워질 것이다. 이럴 경우 이진 탐색 기법을 사용하면 효율적으로 원하는 값을 찾을 수 있다. 이진 탐색의 방법은 low와 high를 두고 mid값을 구해서 탐색 범위를 좁혀가는 것이다. mid값이 탐색값보다 작다면 low에 mid+1값을 넣어서 다시 탐색을 할 수 있고 mid값이 탐색값보다 크다면 high에 mid-1값을 넣어서 탐색을 하면 된다. 이런 .. 2022. 7. 7.
Merge Sort - 합병 정렬과 코드 병합정렬이라고도 하고 합병정렬이라고도 한다. 합병정렬은 퀵소트와 비슷하면서도 2배의 메모리 공간을 차지한다. 하지만 최선/평균/최악의 경우 시간복잡도가 모두 O(NlogN)으로 같다. 합병정렬은 1. 영역 나누기 2. 각 영역을 Merge Sort 3. 두개의 영역을 Merge 하는 순으로 진행된다. 간단한 예를 그림과 함께 보면 다음과 같다. 배열을 쪼갤 수 있을 때까지 쪼갠후 합친다. 합칠 때는 값을 비교하면서 순서를 맞춰 합친다. 의사코드를 작성해보면 다음과 같다. MergeSort(start, end, arr[], tmp[]){ if(start >= end) return; //분리 mid = (start + end)/2; //합병정렬 MergeSort(start, mid, arr); MergeSo.. 2022. 7. 7.
Quick Sort - 퀵 정렬과 코드 앞서 다른 정렬들은 영어부분을 번역해서 "ㅁㅁ정렬" 이렇게 부르던데 퀵소트는 그냥 퀵정렬이라고 부르는부분이 약간 웃기다. 퀵정렬은 분할 정복을 사용한다. 1. 배열의 끝에 있는 수를 Pivot으로 설정한다. (기준값) 그리고 맨 처음에 Pivot보다 작은 수를 세기위한 low와 (오름차순) 차례 차례 수를 확인하고 비교하기위한 ptr 을 둔다. 2. ptr에 있는 값과 Pivot값을 비교한다. 오름차순의 경우 ptr값이 더 작으면 low값을 뒤로 한칸 옮긴다. (++ 그리고 이때 만약 ptr값과 low값이 다르면 두 값을 Swap한다) 비교가 끝나면 ptr을 한 칸 뒤로 옮긴다. 3. 계속해서 ptr과 Pivot값을 비교한다. ptr에 있는 값이 더 크다면 low는 그대로 두고 ptr을 뒤로 옮긴다. .. 2022. 7. 6.
Insertion Sort - 삽입 정렬과 코드 삽입 정렬은 정렬하려는 배열의 두 번째 원소부터 확인한다. 선택된 원소에서 앞과 비교해서 오름차순의 경우 앞의 원소가 더 크면 선택된 원소와 자리를 교환한다. 위 그림에서 파란 화살표가 가리키는 게 Key라고해보자. 두번째부터 시작해서 앞과 비교한다. 비교와 바꾸기가 끝나면 다음 반복에서 Key가 한칸 뒤로 옮겨진다. 이에 대해서 의사코드를 작성해보면 다음과 같다. for ( i = 1 ; i 0; j--){ if(key < arr[i-1]) arr[j] = arr[i-1] else break; } arr[j] = key } 바깥 반복문은 2번째 원소부터 끝까지 돌고 안쪽 반복문은 바깥 반복문의 앞쪽을 돈다. 앞쪽을 돌다가 key값보.. 2022. 7. 6.
Select Sort - 선택 정렬과 코드 선택정렬은 거품정렬과 비슷하다. 둘다 반복문을 완전히 2번 돈다는 점에서 최선/평균/최악의 시간복잡도가 n^2로 같다. 다른 점은 선택정렬이 거품정렬보다는 swap 횟수(메모리 이동)이 적을 수 있다는 것이다. 예를 들어 2 3 5 1 과 같은 배열을 오름차순으로 정렬한다고 하면 선택 정렬로 정렬하는 과정은 다음과 같다. 선택 정렬은 각 반복마다 가장 끝에 최대값을 찾아 넣는다. 그래서 N길이의 배열의 경우 첫 반복에는 arr[N-1] = MAX(arr[0] ~ arr[N-1]) 이 들어가고 다음 반복에는 arr[N-2] = Max(arr[0] ~ arr[N-2]) 가 들어가게 된다. 의사코드를 작성해보면 아래 같은 느낌이다. for ( i = 0 ~ N-1 ){ for( j = 1 ~ N-1-i ){ .. 2022. 7. 5.
Bubble Sort - 거품 정렬과 코드 지금까지 내가 알고있기로는 버블 소트는 앞으로 다룰 정렬중에서 가장 정직하고(?) 가장 비효율적인 정렬이다. 그래서 이 정렬이 실제로 쓰이는지 궁금하기도하다. 오름차순의 경우, 거품 정렬은 뒤에 있는 데이터와 값을 비교하면서 앞의 데이터가 뒤의 데이터보다 크면 위치를 교환한다. 처음에는 주어진 배열의 처음에서 끝(N)까지 탐색, 그 뒤로는 처음부터 N-1까지 탐색, 그 뒤로는 N-2까지 탐색하며 탐색 범위를 줄여나간다. 그래서 처음 탐색을 완료하면 N번째에는 제일 큰 수가 오고 다음으로 탐색을 완료하면 N-1번째에는 그 다음으로 큰 수가 온다. 예를 들어 1, 5, 3, 2, 4 라는 배열이 있을 때 이를 거품정렬을 한다면 다음과 같을 것이다. 이 과정을 의사코드로 나타내면 for(int i = 0; i.. 2022. 7. 5.
새내기 자료구조 멘토링 - Stack,Queue,Tree,Graph 오늘은 교내 학술동아리 신입회원분들을 대상으로한 멘토링에서 자료구조 멘토링을 진행했습니다. Stack, Queue, Tree, Graph를 위주로 퀴즈를 풀어가면서 자료구조를 빠르고 쉽게 찍어먹어 봤습니다. 제 소개를 드리고 배울 내용에 대해 소개드렸습니다. (멘토 소개 생략) 인터넷에 검색해보면 Primitive Data Structure는 char, integer, real, string, pointer.. 처럼 다양하게 적혀있습니다. 아마 프로그래밍 언어별로 다를 수도 있는 것 같습니다. 그래서 그냥 크게 신경쓰지 않고 Boolean, Char, Integer, Floating-Point로 나눴습니다. Non-Primitive Data Structure도 검색해보면 많이 다르게 나뉘는데 그냥 대충!.. 2021. 11. 14.

티스토리툴바