알고리즘16 알고리즘 문제 풀이 순서, 공부 방법 (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. 알고리즘(코테) 스터디 [포도농사] 파일 공유 및 사용법 목차 1. 파일 공유 2. 구글 드라이브 이용 스터디 세팅 법 지난 게시글에서 알고리즘(코테) 공부법을 소개해 드렸습니다. 이번에는 지난 게시글에서 소개해드린 포도농사 스터디법에 사용된 양식을 공유하고자 합니다. 아래는 엑셀 파일입니다. 이 파일을 가지고 혼자 공부하셔도 좋지만!! 스터디를 하시는 경우 공유가 필요합니다. 이 때 구글 드라이브 공유 문서를 이용합니다!! 1. 구글 드라이브 들어가기 2. 새로 만들기 > 스프레드 시트 > 빈 스프레드 시트 3. 파일 > 열기 > 업로드 새로 생성된 빈 스프레드 시트에서 파일 > 열기를 누르면 파일열기 창이 뜨는데 거기에서 업로드 탭을 누른 후 다운받은 포도농사 엑셀파일 (알고리즘 공부 엑셀파일) 을 선택합니다. 그러면 다음과 같이 업로드가 됩니다!! 4. .. 2021. 8. 26. 알고리즘 공부, 코테 스터디 하는 법 공유!! - 알고리즘 문제 풀이 순서, 공부 방법 (1) - 비전공자/문제풀이 처음: https://waytocse.tistory.com/114 - 알고리즘 문제 풀이 순서, 공부 방법 (2) - 전공자/문제풀이 초보: https://waytocse.tistory.com/115 아래에서 다루는 것은 위에 다루는 내용도 일부 포함되어있고 다른점은 3번!입니다 :) 목차 1. 알고리즘 공부 사이트 2. 알고리즘 공부 시작 하는 법 3. 코테 공부 / 스터디 하는 법 공유 1. 알고리즘 공부 사이트 보통 알고리즘을 공부할 때 백준(https://www.acmicpc.net/), 프로그래머스(https://programmers.co.kr/)를 많이 이용합니다. 삼성 역량테스트에 관심있는 분들은 SW Expert Acad.. 2021. 8. 26. 이전 1 2 다음
