남민우의 공부 블로그

리스트의 이해리스트는 크게 두 가지, 1. 순차 리스트와 2. 연결 리스트로 나눌 수 있다.1. 순차 리스트는 '배열'을 기반으로 구현된 리스트를 말하며,2. 연결 리스트는 '메모리의 동적 할당'을 기반으로 구현된 리스트로이 두가지는 '구현 방법'을 기준으로 구분지었다는 것을 알 수 있다.다만 이 구현 방법이 '어떻게 구현을 하느냐' 가 달라지는 것이지 그에 따라 제공되는 기능이 달라지는 것은 아님을 알고 가야 한다. 이러한 리스트는 두가지 특징을 가지고 있는데1. 저장 형태는 '데이터를 나란히(하나의 열로) 저장한다는 것과2, 중복되는 데이터의 저장을 허용하는 특성이 있어이 특징들을 유지하려다 보니 배열과 연결의 형태가 갖춰지는 것이라고 이해할 수 있다. 리스트 자료구조의 ADT여기서 LData는 저장..

프로그래밍 및 언어/자료구조 학습 2025. 1. 17. 22:57

추상 자료형이 추상 자료형(이하 ADT)이란, 말 그대로는 자료형(기능)을 추상적으로 정의한 것으로 '구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지 나열한 구조' 를 의미한다.이러한 ADT를 자료구조에 반영하였다는 것은 보다 더 좋은 코드를 만들어냈다 라는 뜻을 가지고도 있다. 먼저 자료형이란? '기능'을 말한다.키보드의 입력, 핸드폰의 알람 등 여러 기능이 있을텐데, 지갑의 추상 자료형을 예시로 들어보자면- 카드의 삽입/추출 이 가능하다.- 현금의 삽입/추출이 가능하다.라는 하나하나의 기능을 설명할 수 있다.다만 여기서 카드의 삽입이 어떤 동작으로 이루어지고, 추출이 어떤 동작으로 이루어지는지 그에 대한 진행 과정은 언급하지 않았는데, 이렇게 기능을 나열하되 진행 과정에 대해서는 ..

프로그래밍 및 언어/자료구조 학습 2025. 1. 14. 00:30

하노이 타워란?원반을 한 번에 하나씩 옮기면서 최종적으로 초기 상태를 유지한 채로 두 칸 옆의 기둥으로 옮기는 퍼즐이 퍼즐을 현실에서 푸는 동작은 사실 어렵지 않다.문제는 이 과정에서 재귀의 특성을 찾고, 그걸 프로그래밍적으로 해결하는 것이다. 크기가 큰 순서부터 3, 2, 1 이라고 할 때제일 먼저 해결해야 하는 것은 3 원반을 C로 옮기는 것. 다만 그렇게 하려니 2번과 1번을 B로 치워야 한다.2번과 1번 원반을 옮기면, 또 1번을 C로 옮겨야 한다.처음 이 문제를 보면서 프로그래밍적으로는 큰 문제를 해결하기 위해 작은 문제부터 해결하는 분할 정복(Divide/Conquer) 알고리즘을 사용해야 하나 싶었는데, 조금 다른 결의 풀이다. 내가 생각했던 이유로는 4개의 원판이 있다고 했을 때 3개를 먼..

프로그래밍 및 언어/자료구조 학습 2024. 10. 21. 02:21

재귀의 이해재귀란? 어떤 코드를 정의할 때 그 안에서 자기 자신을 참조하는 것을 말한다.흐름 상 반복문과 혼동하거나 호출 구조를 헷갈리기 쉬운데, 먼저 반복문은 한번 함수 호출 시 그 함수의 본문을 계속적으로 반복하는 코드 동작이라 별개의 방식이고호출 구조를 봤을 때 같은 자기 자신을 계속 호출하는 재진입의 구조로도 보이지만정확하게는 원본 함수를 한번 호출하고, 같은 함수의 복사본을 계속 생성해내는 Copy&Paste -> Call 의 과정이라고 보는 것이 정확하다.모든 코드 동작은 동작 시 컴퓨터에 메모리를 차지한다.이때 재귀함수의 메모리 호출 - 해제 순서는원본 - 복사본A - 복사본B - 복사본C ... 으로 소요됐을 경우... - 복사본C - 복사본B - 복사본A - 원본 순으로 역방향으로 메모리..

프로그래밍 및 언어/자료구조 학습 2024. 10. 20. 23:30

순차 탐색의 최악의 경우 시간 복잡도는T(n) = n 으로 나타내고 이는 빅-오 표기법으로 O(n) 으로 나타낸다. 이진 탐색의 최악의 경우 시간 복잡도는T(n) = Log2N + 1 로 나타내고 이는 빅-오 표기법으로 O(LogN) 으로 나타낸다. 둘을 비교하기 위해선 n에 증가량에 따른 연산 횟수를 살펴봐야 하는데단순 계산만 보더라도순차 탐색의 연산횟수보다 이진 탐색의 연산 횟수가 극단적으로 적다는 것을 알 수 있다 특히 이진 탐색의 연산 횟수는 n의 값이 증가함에 따라 그 상승폭이 점점 더 줄어드는 모습으로이는 사용하기 좋은, 매우 뛰어난 알고리즘이다 라고 결론 내릴 수 있다.

프로그래밍 및 언어/자료구조 학습 2024. 10. 19. 01:21

이전 #5의 마지막 문단, +1을 생략하는 이유에 이어서 진행된다. 빅-오 표기법T(n) 의 수식에서 실제로 영향력을 끼치는 부분을 '빅-오(Big-Oh)' 라고 부른다.이 영향력을 끼치는 부분만 표기하는 방법이다. 이전 +1 을 생략하는 질문을 다르게 생각해서+1 이 너무 작은 수치라 생략하는 거라면 +100, +500 과 같이 숫자가 커져도 똑같이 생략하는거냐?라는 질문을 던질 수 있다. 이 대답을 하기에 앞서, 시간 복잡도 함수를 보는데 있어서 그 관점이 어디에 있냐 를 먼저 판단해야 한다.그 관점이 어딘가 하면 항상 가정하는 최악의 경우, 즉 데이터 표본이 셀 수 없을 많을 때 이다. 데이터 표본이 너무 많아서, 예를 들어 10만, 100만의 데이터 중 원하는 값을 찾는다고 할 때과연 +100, ..

프로그래밍 및 언어/자료구조 학습 2024. 10. 18. 03:34

이진 탐색 알고리즘기본적으로 이차원으로 정렬된 배열에서 탐색하는 알고리즘이다.순차 탐색 알고리즘보다 좋은 성능을 보이지만 배열이 정렬되어 있어야 한다는 제약이 있다.이때 정렬은 반드시 오름차순/내림차순 이어야 한다 가 아니라 정해진 기준이 있으면 상관없다. 이러한 배열이 있다고 할 때 3 이라는 값을 찾는 알고리즘을 설계한다고 해보자. 이진 탐색 알고리즘의 기본 골격은 다음과 같다.1. 처음 인덱스 + 끝 인덱스 값을 더한다2. 그 값을 2로 나눈다.3. 해당 결과값을 인덱스로 하여 배열의 값을 탐색한다. 이 골격을 가지고 순서를 다시 생각해본다면1. 처음 인덱스 : 0 / 끝 인덱스 : 8 => 82. 8 / 2 = 43. arr[4] = 9의 과정을 거치게 된다. 만약 여기서 arr[4] 가 우리가 ..

프로그래밍 및 언어/자료구조 학습 2024. 10. 18. 02:27

순차 탐색 알고리즘말 그래도 순차적으로, 정해진 순서에 따라 탐색하는 알고리즘이다. 예를 들어 길이가 5인 배열이 존재하고, 이 중 3 이라는 숫자를 찾는다 가정할 때첫 인덱스부터 마지막 인덱스까지 순차적으로 탐색할 것이다. int LSerach(int ar[], int len, int target){ int i; for(i = 0; iar[] 배열에서 target 과 동일한 인덱스를 찾기 위해 순차적으로 탐색하는 알고리즘이다. 이 코드에서 시간 복잡도를 결정할 연산자는 if(ar[i] == target) 의 '==' 가 된다.Why?코드의 목적 자체가 target 과 값이 같은지 '확인' 하는 알고리즘이다.이 확인에서 가장 중요한 연산자가 시간 복잡도를 결정한다. 여기서 중심이 되는 연산자의 특징 을 ..

프로그래밍 및 언어/자료구조 학습 2024. 10. 17. 23:50