Study
- 본 프로젝트는 자료구조에 대한 이해와 알고리즘 구현 방안에 대해 학습한 내용을 담고있다.
Computer Science
- 단순 자료구조 및 알고리즘에 대한 학습을 넘어, CS기반을 함양하고 구현방식에 대해 이해하면서 실무적으로 적용하기 위한 역량을 향상한다.
- 아키텍칭(설계)적인 부분과 함께 구현/전략구체화 시 응용가능한 방안들을 고민하면서 기록한다.
프로그램의 본질적 의미이자, 문제를 해결하는 과정은
- 어떤 자료구조를 활용하여
- 어떤 알고리즘을 통해 해를 도출할 것인가에 대한 과정이다.
자료구조는 데이터를 어떠한 구조로 어떻게 사용할 것인지에 대한 기본적인 방법이다.
- 변수와 배열도 하나의 자료구조이며, 어떠한 자료구조를 선택하느냐에 따라 구현방법 및 적용 알고리즘이 달라진다.
알고리즘은 문제에 대한 고민 부터 해결까지 일련의 서사를 모두 담고 있는 쳬계이자 과정이다.
- 중요한 것은 예외없이 특정 자료구조 및 데이터에 따라 확실하게 원하는 해를 도출해야 한다는 것.
- 변수 3개의 평균을 구하는 알고리즘과 변수 n개, 변수 n개에 대한 배열의 평균을 구하는 알고리즘은 다르다.
더 좋은 알고리즘은 사용자 요구에 따라 달라질 수 있지만, 보통은 처리속도를 성능의 척도로 간주한다.
- 이때 성능의 척도를 시간복잡도라 한다.
컴퓨터 사양마다 알고리즘의 실행 시간은 다를 수 있기에, 알고리즘의 실행시간이 아닌 알고리즘 실행시간(성능)에 영향을 줄 수 있는 부분을 찾아 실행시간을 예측한다.
- 이때 보통 반복문의 개수가 성능에 많은 영향을 준다.
빅오 표기법에 따른 시간복잡도 나타내기
- 특정 자료구조에 대한 알고리즘은 입력값이 늘어나거나 주어진 자료구조의 크기가 늘어남에 따라 그 성능척도가 달라질 수 있다.
- 최선의 경우를 Big-Omega, 최악의 경우를 Big-O, 평균의 경우를 Big-Theta로 표현하며 보통은 Big-O 표기법(최악의 경우)을 많이 활용한다.
- 입력크기에 비례하여 선형적으로 소요시간이 늘어나는 O(N), 입력에 상관없이 일정한 O(1) 등을 시작으로, O(logN), O(NlogN), O(N^2), O(2^N), O(N!) 등의 시간복잡도가 존재한다.
- Big-O 표기법의 경우 입력량에 따라 늘어나는 계산량을 최악의 경우로 표현한 것이고, 가장 영향을 많이 주는 척도 하나를 대표하여 표기한다.
읽기 : O(1), 쓰기 : O(N)
- 운영체제 측에선 최초 주소값을 기억하여 offset을 활용하여 데이터를 탐색하고 읽기에, 읽기(참조) 측면에서는 성능이 나쁘지 않다(배열크기 상관없이 O(1)의 시간복잡도를 지닌다).
- 크기를 미리 지정해두어야 하기에 메모리 공간적 효율이 좋지 않으며, 이후 데이터 쓰기 및 삭제작업이 별도로 이루어져 성능이 좋지 않다.
읽기 : O(N), 쓰기 : O(N)
- 기존 배열의 메모리 연속적 할당과 크기 확장 등에 대한 단점을 보완하고자 도입된 자료구조이다.
- 과정적으로 노드의 데이터는 건드리지 않고 다음 포인터 주소만 변경하면 되기에 간단하지만, 이러한 데이터를 탐색하는 과정에서 순차적인 이동이 필요하여 O(N)의 선형복잡도를 가진다.
- 탐색작업이 오래 걸리기에 쓰기 작업의 시간 복잡도에도 영향을 주지만, 메모리 공간적 할당이나 절차적으로 보았을때는 기존 배열보다 더 간편하고 효율적이다.
First In, Last Out
- 되돌리기를 위한 수행작업 임시 저장, 문법검사 등 여러 알고리즘에 사용 가능.
First In, First Out
- head, tail을 사용하여 이중 연결리스트(양방향)을 활용해야 효과적 활용 가능(O(1)).
- 운영체제의 FIFO 스케쥴링 등 여러 알고리즘에서 사용 가능.
Head In/Out and Tail In/Out
- 자유로운 데이터 삽입 및 제거가 가능한 자료구조.
다수의 데이터를 메모리 공간의 낭비없이 효율적으로 저장하고자 해시함수를 통해 도출한 key값을 인덱스로 매핑하여 배열기반으로 저장하는 자료구조.
- 해시함수를 이용하여 추출한 key값과 인덱스를 매핑하여 저장한다.
- 배열을 기반으로 데이터를 저장하는 구조이지만, 배열이 가진 기존 메모리 효율 측면의 단점을 보완하기 위해 도입된 자료구조이다.
- 해시함수로 인한 충돌발생 시 체이닝(동일 key값에 대하여 연결리스트로 연결) 및 개방주소법으로 파훼한다.
- 해시함수가 그만큼 중요하고, 배열 기반 자료구조이며 "저장"의 효율에 중점을 두었기에 메모리 공간 자체는 많이 필요하다.
- 읽기 : O(1), 쓰기 : O(1)
[체이닝을 통한 데이터 탐색]
- 동일 key(인덱스)에 여러개의 데이터를 연결리스트로 연결하여, 원하는 데이터를 찾을 때까지 데이터를 탐색한다.
- 이 경우 시간복잡도는 O(N)
데이터 중복을 허용하지 않는 자료구조.
- 해쉬테이블 자료구조를 사용하여 해쉬셋이라고도 한다.
- key = value, 즉 데이터를 제거한다는 것은 결국 이와 동일한 key를 찾아 해당 요소를 제거하겠다는 의미.
[동작]
자기자신을 참조한다.
- 재귀적 호출/재귀적 함수 - 이러한 재귀용법을 사용하여 로직을 구성하였을 경우.
[CS]
Call Stack
- 변수선언 및 함수호출 시 적재되는 메모리 공간.
- 재귀적 동작 진행할 경우 모함수가 종료될때까지 계속 적재된다.
- 종료 시에는 이미 실행완료한 자함수들은 순차적으로 Stack에서 제거된다.
[재귀적 관점]
- 패턴A : 단순반복
- 함수 호출할때마다 Stack 적재, 메모리 공간 낭비 및 성능 하락
- 패턴B : 하위 문제의 결과를 상위 문제 해 도출
- 하위 문제의 결과를 활용하는 하향식 접근의 관점(*단순반복 : 상향식 접근)
- 재귀함수를 사용하는 이유!
- 팩토리얼
- 배열의 합
- 지수함수
- 하노이탑
- 무작위로 섞여있는 배열의 원소들을 정렬하는 방법
[버블정렬]
- 앞의 숫자와 뒤의 숫자를 비교해가면서 정렬, 한 단계마다 가장 오른쪽의 숫자가 정렬이 완료된 상태이다.
- bigO = O(n^2)
[선택정렬]
- 정렬되지 않은 구간을 순회하면서 가장 작은 원소를 선택, 이를 정렬되지 않은 첫번째 요소에 원소를 배치한다.
- bigO = O(n^2)
[삽입정렬]
- 정렬된 구간과 정렬되지 않은 구간을 나누어, 정렬되지 않은 구간의 첫번째 원소를 정렬구간과 비교해가며 덮어쓰기 및 적절한 위치로의 삽입하는 과정을 반복한다.
- bigO = O(n^2)
[병합정렬]
- 분할정복(divide and conquer), 문제를 분할하여 해결한다.
- 재귀적 접근을 통해 범위를 쪼갠 후에, 하향식으로 결과를 병합해나간다.
- 문제의 범위를 반으로 쪼개어 logN * 각 단계별 배열크기만큼 순회비교, 이에 대한 시간복잡도는 O(NlogN)
[퀵정렬]
- 병합정렬과 마찬가지로 분할정복으로 문제를 분할하여 해결
- 피벗 및 배열의 양 끝 인덱스, 비교를 위한 양쪽의 비교 인덱스
- 피벗과 비교해가면서 조건 만족 시 서로의 자리를 swap한다.
- 비교를 위한 양쪽의 비교 인덱스가 서로를 지나칠때, 피벗과 오른쪽 비교 인덱스를 바꾼다.
- 이 단계까지 완료하였을 시점에, 자리를 옮긴 피벗(오른쪽 비교 인덱스 자리)보다 왼쪽의 수들은 그보다 작고, 오른쪽의 수들은 그보다 큰 수들이다.
- 즉 피벗으로 지정한 수의 정렬이 완료, 이를 범위분할하여 정복한다.
- 평균적으로 O(NlogN)..범위분할 logN * 분할 후 N번 순회작업, 피벗이 치우칠 경우 log(N^2)이지만 평균적으로는 O(NlogN)의 성능을 보인다.
- 재귀는 문제를 쪼개는 관점이며, 여기에 기억을 더한 "재귀의 최적화 방법론"을 동적프로그래밍이라 한다.
- 하향식 접근 시 memoization, 상향식 접근 시 tabulation이라 한다.
[동적프로그래밍 - 메모이제이션]
- 분할정복 및 재귀를 통한 문제해결은 함수호출로 인한 콜스택 차지 및 성능적으로 그리 좋지 못한 단점이 존재할 수 있다. (다만 크기가 매우 크거나 분할범위가 치우쳐있을 경우이며, 만약 분할정복이 아닌 다른 문제의 해결과정을 그대로 활용할 경우 중복처리 발생 가능성도 존재한다.)
- 이러한 관점에서, 재귀적인 접근 방법이 곤란하다면 처리 결과를 기억하는 메모이제이션 방법을 사용하여 성능을 보완 할 수 있다.
- HashTable(O(1)) 활용하여 접근.
[동적프로그래밍 - 타뷸레이션]
- 하향식 접근으로 재귀의 문제해결을 최적화한 과정이 메모이제이션이라면, 상향식 접근으로 재귀의 문제해결을 최적화한 과정이 타뷸레이션이다.
- 필요한 값을 미리 모두 저장해두는 방식.
[트리]
- 각 노드들이 계층적 관계를 형성하여 최종적으로 이어진 모양이 나무와 같은 모양을 하는 자료구조.
- 트리는 다수의 서브트리로 구성할 수 있으며, 더이상의 자식이 없는 터미널 노드(리프 노드)와 루트노드가 동일한 그 자체의 서브트리구조도 볼 수 있다.
[이진트리]
- 각 노드들이 최대 2개의 자식노드만을 가지고 있는 트리구조(자식노드가 없거나 1개 보유해도 이진트리)
[포화이진트리]
- 이진트리의 최대레벨까지 존재하는 모든 노드가 꽉 채워져 있으며, 모든 리프노드가 동일한 깊이인 트리구조
[완전이진트리]
- 이진트리의 최대레벨까지 모든 노드가 채워져 있으며, 최하층 리프노드들은 왼쪽부터 채워져있는 상태의 트리구조.
[순회]
- 전위순회 : 루트노드를 최우선적으로 탐색, 그 후 왼쪽서브트리와 오른쪽서브트리를 순회하는 방법.
- 중위순회 : 왼쪽서브노드를 최우선적로 탐색, 그 후 루트노드와 오른쪽서브트리를 순회하는 방법.
- 후위순회 : 왼쪽서브노드를 최우선적으로 탐색, 그 후 오른쪽서브노드와 루트노드를 순회하는 방법.
- Binary Search, 찾고자 하는 특정 값을 배열의 범위를 반으로 줄여 나가면서 탐색해나가는 알고리즘
- 단, 배열이 정렬된 상태이어야 가능하다.
- 배열 자료구조의 특성상 메모리 효율이나 데이터 삽입/제거 성능 측면에서 비효율적이다.
데이터 삽입, 제거, 탐색 성능을 모두 보완하기 위해 활용하는 자료구조.
- 기존 이진탐색 알고리즘의 배열정렬조건 및 해시테이블의 메모리 효율 단점을 보완한다.
- 이진트리의 구조를 가지면서, 각 노드의 왼쪽트리에는 이보다 작은 값만, 오른쪽트리에는 큰 값만 들어갈 수 있다.
- 모든 노드들은 데이터 중복이 불가능하다.
[삽입]
- 이진탐색트리 자료구조의 정의를 활용하여 삽입할 노드 자리를 구할때까지(삽입하고자 하는 자리의 노드가 없을때까지) 자리를 찾아 삽입한다.
[결정문제]
- 어떠한 문제가 주어졌을때, Yes or No로 대답할 수 있는 문제
[최적화문제]
- Yes or No로 대답하기엔 어려운 문제이지만, 해당 문제의 최적의 해를 구하는 문제
- 최소비용, 가장 짧은 경로 등
- 다만 대부분의 경우 결정문제로 바꾸어 해결할 수 있다.
[P문제]
- 어떠한 문제가 주어졌을때 다항시간 내에 결정론적 튜링 방식을 활용하여 답을 구할 수 있는 문제
- 쉬운문제, 특정 조건 혹은 분기처리로 다음 상태를 유일하게 정할 수 있는 로직을 사용하여 해결한다.
[NP문제]
- 어떠한 문제가 주어졌을때 비결정론적 튜링 방식을 활용하여 다항시간 내 답을 구할 수 있는 문제
- 달리 말하면, 결정론적 튜링 방식을 활용할 경우 다항시간 내 답을 구하기 어려운 문제(지수시간 혹은 팩토리얼 복잡도를 보유할 경우)
- 다만, 결정론적 튜링 방식을 이용하여 힌트 혹은 특정 조건/상황에 대한 검증까지는 가능하다.
- 비결정론적 튜링 방식은 무한한 컴퓨팅 능력을 가져 동시탐색이 가능한 이상적인 경우를 말한다.
[NP-Hard 문제]
- 어떤 NP문제들이 있을때, 이 문제들을 해결하기 위해 다른 문제로 환원하여 접근 및 해를 도출할 수 있을 때 "그 환원한 문제들을" 일컫는다.
- 어려운 문제.
- 어떤 문제로 환원은 가능하지만, 그 문제를 풀 수 있는지 없는지 가늠조차 못한 문제들이다(비결정론적 튜링 머신으로도 다항 시간 내에 해를 도출할 수 없다).
[NP-Complete 문제]
- NP-Hard 문제들 중에 NP문제로 포함되는 문제(문제 환원이 가능한 경우).
- 어떻게든(비결정론적 튜링 방식으로 다항 시간 내) 해결 자체는 가능하다.
- 해결가능한 문제들 중 가장 어려운 문제.
전략 #1. 단계적 접근
- 예외의 경우 혹은 동작이 불가능한 상황에 대한 고려
- 경계상황 등을 중심으로 동작분기처리
- 분기 상황 별 구현
전략 #2. 이전의 구현로직을 활용한다.
- 활용도가 높은 부분적 로직을 먼저 정의
- 예외의 경우 혹은 동작이 불가능한 상황에 대한 고려
- 경계상황 등을 중심으로 동작분기처리
- 분기 상황 별 구현
- 구현 후 이후 추가저인 로직 구현 시 이전의 구현로직을 최대환 활용한다.
전략 #3. 재귀와 재귀적 접근
- 분할정복, 문제를 쪼개어 나간다의 접근은 재귀적 접근이다.
- 단, 재귀는 문제를 쪼갠다는 전략의 일종으로 "범위의 분할"에 적용하는 개념이며, 병합은 추가적인 접근이 필요하다.
- 큰 문제를 작은 문제로 일단 쪼개어 나간다면 하향식, 문제 쪼개기(분할) 보다는 처음부터 작은 문제부터 접근하여 이를 table에 기록하여 활용한다면 상향식.
- 재귀적 접근에 기억이 활용된다면 DP(Dynamic Programming), 접근 방식에 따라 memoization(하향식), tabulation(상향식).
- String : 불변한 객체, 변수 로딩시 상수풀(Interned pool)에 저장된 불변 String 객체 지정, 동일 리터럴이면 재사용, 가장 빠르지만 상수 사용
- StringBuilder : 내부버퍼가 가변적(char[]), 내부 버퍼가 가득 차거나 append 시 다른 문자배열에 복사 후 교체, 내부구조 자체는 배열성격(연속된 할당공간/block), 데이터 쓰기작업이 어려운 대신 참조(읽기) 작업은 O(1).
- StringBuffer : StringBuilder와 유사하나 멀티 스레드의 동기처리를 보장하기 위한 synchronized 기반 동작에서 차이, 스레드 안전성, 단일 스레드 상황에선 그만큼의 오버헤드 발생.