[인프런 워밍업 클럽 4기 - CS] - 1주차 발자국
📕 자료구조와 알고리즘(심화)✅ P-NP문제가 어려운 지, 쉬운 지 혹은 해결이 가능한 지 불가한 지 판단하는 것.결정 문제: 참 혹은 거짓을 대답할 수 있는 문제최적화 문제: 최적의 해를 찾을 수 있는 문제 (대부분의 최적화 문제는 결정 문제가 된다)결정론적 튜링 머신: 다음 상태가 유일한(오직 하나의) 상태로 결정되는 것비결정론적 튜링 머신: 현재 상태와 기호에 대해 여러 개의 가능한 다음 상태가 존재할 수 있는 것 (현실에는 존재 X 가정으로 상상)다항 시간: 어떤 문제의 해결 시간을 다항식으로 표현이 가능한 것다항 시간 내 1. 상수 시간: O(1) 2. 로그 시간: O(log n) 3. 선형 시간: O(n) 4. 로그-선형 시간: O(nlog n) 5. 다항 시간: O(n^k) 다항 시간 외 1. 지수 시간: O(k^n) 2. 팩토리얼 시간: O(n!) P 문제: 결정문제에 대해 결정론적 튜링 머신을 통해 다항 시간 내에 답을 구할 수 있는 문제NP 문제: 결정문제에 대해 비결정론적 튜링 머신을 사용하여 다항 시간 내에 답을 구할 수 있는 문제NP Hard: 모든 NP문제들을 다항 시간 내에 어떤 문제 A로 환원이 가능한 것NP Complete: NP-Hard이면서 NP에 포함되는 문제결정론적 / 비결정론적 문제ex) 완전 이진 트리 형태로 되어 있고 깊이가 k인 갈림길에 하나의 리프에만 보물이 있다고 가정결정론적: 한 번씩 모든 길을 거쳐서 보물을 확인 > 최악의 경우 2^k의 시간이 걸린다.비결정론적: 갈림길을 마주할 때마다 분신술을 사용하여 동시에 모든 리프 확인 > k의 시간이 걸린다.어떠한 힌트가 주어지게 된다면 비결정론적 문제들은 결정론적 문제로 검증이 가능모든 결정론적 문제들은 비결정론적 문제들에 속함 (P⊆NP) ✅ 트리와 이진 트리트리: 하나의 노드에서 점차 내려가는 자료구조Edge: 각 노드를 연결하는 선루트 노드: 트리에서 최상위 노드터미널 노드: 자식 노드가 없는 노드인터널 노드: 터미널 노드를 제외한 노드서브 트리: 트리 구조 내에 작은 트리 (터미널 노드 또한 루트 노드만 있는 트리라고 판단)레벨: 각트리의 높이이진 트리: 각 노드는 최대 2개의 자식 노드를 갖는 트리포화 이진 트리: 트리의 최대 레벨에 있는 모든 터미널 노드가 꽉 찬 트리완전 이진 트리: 최대 레벨을 제외한 나머지 레벨에는 모두 노드가 존재하고 최대 레벨의 노드는 왼쪽부터 채워진 트리순회: 트리의 노드들을 순회전위: 루트 노드 먼저 순회중위: 루트 노드를 중간에 순회후위: 루트 노드를 마지막에 순회 ✅ 이진 탐색 트리이진 탐색 알고리즘: 정렬되어 있는 배열에서 반씩 나눠 탐색을 해가며 범위를 줄여나가는 알고리즘이진 탐색 트리이진 탐색은 정렬된 상태에서만 가능하며 배열의 경우 데이터 삽입, 삭제가 비효율적이다.해시 테이블은 데이터 조회, 삽입, 제거가 빠르지만 해시 함수에 따라 성능이 달라지고 데이터를 저장할 메모리가 필요하다.이진 탐색 테이블은 데이터 조회, 삽입, 제거가 빠르고 해시 테이블에 비해 메모리 사용량이 적다규칙자식 노드는 모두 이진 트리여야 한다.중복된 노드의 데이터는 없어야 한다.A 노드의 왼쪽 자식 노드값은 A 노드값보다 작아야 한다.A 노드의 오른쪽 자식 노드값은 A 노드값보다 커야 한다.자식 트리도 상위 규칙을 따라야 한다.평가:트리가 만들어졌을 때 : O(logn)트리가 잘 만들어지지 않을 때 : O(n)이진 트리는 균형을 유지하는 것이 성능에 중요삽입, 삭제 시 트리의 균형이 깨질 가능성이 크다.✅ AVL 트리이진 트리에서는 균형을 유지하는 것이 중요하다.규칙:왼쪽과 오른쪽 자식트리의 높이가 최대 1까지만 차이가 날 수 있다.균형이 맞지 않는 트리는 회전을 통해 균형을 다시 맞출 수 있다.(못 맞추는 경우도 존재)회전LL회전: 오른쪽으로 뻗은 트리에 대해 적용 가능RR회전: 왼쪽으로 뻗은 트리에 대해 적용 가능LR회전: 왼쪽으로 꺾였다가 안쪽으로 꺾인 트리 적용 가능RL회전: 오른쪽으로 꺾였다가 안쪽으로 꺾인 트리 적용 가능📕 컴퓨터 구조✅ 컴퓨터 구조블랙박스: 내부 작동 원리는 모르더라도 입력에 따라 출력이 예측 가능한 것들모듈화: 큰 문제를 작은 문제로 분할하여 복잡함을 단순화 시키는 방법역사:수동식 계산기- 주판기계식 계산기- 계산봉, 파스칼린, 라이프니츠 휠자동 계산기- 차분 기관(톱니바퀴로 계산 결과 활용), 해석 기관(프로그래밍 가능)디지털 계산기- ENIAC- 폰노이만 구조(중앙 처리 장치, 메모리, 입출력 장치)- 트랜지스터 (진공관 대체)- 집척 회로- ,,, 동작방식컴퓨터는 0,1로 이루어진 명령어만 해석이 가능하다.기계어: 0,1로 이루어진 명령어컴파일러: 정적 코드를 기계어로 변환하는 과정에서 에러 발견 가능하고 실행속도가 매우 빠름 (c, C++) / 변환 과정이 오래 걸림인터프리터: 한 줄씩 기계어로 변환하기에 프로그램 실행 도중 문법 오류 발생 가능, 실행 속도가 느림✅ 컴퓨터 구성 요소CPU:프로그램 카운터: 다음 실행할 명령어 저장제어 유닛: 명령어 해석 및 실행산술 논리 연산장치: 산술, 논리 연산을 수행레지스터: 용량은 적지만 속도가 빠른 CPU 내장 메모리버스: 데이터 전송 통로Memory:RAM(Random Access Memory): 어떤 메모리에 접근하여도 접근 시간이 동일하며 휘발성ROM(Read Only Memory): 쓰기가 불가하며 비휘발성이기 때문에 컴퓨터 동작을 위한 BIOS가 저장 1. CPU가 프로그램 실행 시, 코드와 데이터를 RAM에서 가져온다. 2. 연산에 필요한 데이터 레지스터 저장 3. 연산 이후 결과를 RAM에 저장 4. 자주 사용되는 데이터 CPU 내부에 캐시 메모리 저장 (< 레지스터) / > RAM) 주변 장치:입출력 장치1. 키보드 / 마우스2. 모니터 / 스피커 / 프린터보조기억 장치1. HDD / SSD32, 64bit 컴퓨터:1bit (0,1 표현) = 21byte = 8bit = 2564byte = 32bit = 약 42억8byte = 64bit = 약 18경플리플롭: 1비트를 저장할 수 있는 회로컴퓨터 비트에 맞춰서 레지스터와 버스의 비트 수가 맞춰짐- 64비트 -> 64비트 레지스터 / 64개의 버스비트 수에 따라 저장할 수 있는, 계산할 수 있는 한계가 정해짐RAM이 여러개를 갖고 있더라도 CPU에서 처리할 수 있는 한계가 있음컴퓨터의 성능은 클럭, 명령어 최적화, 메모리, 레지스터 속도가 중요✅ 불 대수디지털 장치들은 불 대수 기반으로 작동한다.true: 1false: 0 불 연산:NOT: 입력값의 반대AND: A와 B가 같을 때만 1 (논리곱)OR: A와 B중 하나만 1이면 1 (논리합)NAND: AND 연산의 반대NOR: 하나라도 1이면 1XOR: 하나만 1일 경우에만 1 (두 입력이 다를 때)불 대수의 성질과 법칙항등원:원산 결과가 자기 자신이 되는 수AND (⋅) / A ⋅ 1 = AOR (+) / A + 0 = A교환법칙: 피연산자의 순서를 바꿔도 결과는 동일하다A ⋅ B = B ⋅ A결합법칙: 괄호의 위치를 바꿔도 결과 동일(A ⋅ B) ⋅ C = A ⋅ (B ⋅ C)분배법칙A ⋅ (B + C) = A⋅B + A⋅C동일법칙: 동일한 값을 두 번 연산해도 원래 값A ⋅ A = A이중 부정법칙: 두 번 부정하면 원래 값으로 돌아감흡수법칙A(A + B)= AA + AB ← 분배법칙= A + AB ← AA = A (동일법칙)= A(1 + B). ← A로 묶음 (결합법칙의 역)= A(1) ← 1 + B = 1 (항등원)= A 드모르간 법칙AND = NOT A OR NOT BA NOR B = NOT A AND NOT B불 함수함수: 입력 값에 따라 출력 값이 변하는 것불함수: 입력 값과 출력 값 모두 boolean 진리표 변환결과가 0인 행은 제외(Don't care 행)모든 행을 AND 연산으로 만들고결과값에 맞춰서 수정✅ 비트10진법과 2진법1개의 비트로 표현할 수 있는 수의 개수 = 2^1개2개의 비트로 표현할 수 있는 수의 개수 = 2^2개3개의 비트로 표현할 수 있는 수의 개수 = 2^3개,,, 10진법 > 2진법 변환10진수를 2로 나눌 수 있을 때까지 나누는 것ex) 9 > 9/2 = 4...1 > 4/2 > 2...0 > 2/2 > 1...09(10) = 1001(2) 16진법0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F16진법을 사용하는 이유는 2진수를 10진법으로 표현하는 것보다 더 간단하기 때문16은 2^4이기 때문에 간단히 변환 가능11111111(2) = FF(16)Ox1001 => 16진수 표기법 빅 엔디안과 리틀 엔디안MSB: 가장 왼쪽 비트LSB: 가장 오른쪽 비트 빅 엔디안: MSB를 가장 낮은 주소부터 채우는 방식리틀 엔디안: LSB를 가장 낮은 주소부터 채우는 방식하나의 방식으로 통일해서 사용해야 함. 오버플로우와 인터럽트오버플로우: 값이 데이터 타입(또는 레지스터)이 표현할 수 있는 범위를 초과했을 때 발생하는 현상인터럽트: CPU가 실행 중인 작업을 중단하고 인터럽트 서비스를 실행 음수- 부호없는 정수 (양수만 표현 가능)0000 ~ 1111 = 0 ~ 15까지 16개 값 표현- 부호있는 정수 (양수, 음수 표현 가능)0000 ~ 1111 = -8 ~ 7까지 16개 값 표현MSB가 부호를 표현(0이면 양수, 1이면 음수) > 나머지 3비트로만 값 표현 가능예: +5 → 00000101 (8비트 기준)음수 표현 만들기 (예: -5)① 비트를 반전 (1의 보수): 11111010② +1 더함: 11111010 + 1 = 11111011 00000101 ( +5 ) + 11111011 ( -5 ) ----------- 00000000 → 결과: 0 후기직접 프로그램을 통해 불 연산을 시각화해볼 수 있다는 것이 가장 인상깊었다. 기존에는 논리 연산을 통해서 조건문을 작성할 때를 제외하고는 생각해본 적이 없었는데, 더 하위 레벨에서 불대수, 불함수, 그리고 불 연산에서 자주 사용되는 수학적인 법칙까지 직접 공부해보고 이를 통해 간단한 프로그램을 만들어 보는 경험이 어렵지 않으면서 가장 크게 체감을 할 수 있었던 것 같다. 자료구조와 알고리즘 또한 트리가 나오게된 배경부터 AVL 트리가 탄생하게 된 계기까지 그 흐름을 잘 따라갈 수 있었고 AVL 트리만의 특징과 균형을 잡기 위한 여러 회전 원리에 대해서도 탄탄히 공부해볼 수 있었다.