[코딩테스트] 섹션1 - INTRO

1. 코딩테스트 꿀팁

자료구조란

데이터를 저장하고 관리하는 방식

자료구조의 장점

데이터를 체계적으로 저장

메모리를 효율적으로 사용

빠르고 안정적으로 데이터 처리

 

ex) 30의 숫자를 저장한다고 가정했을때 Array자료구조를 사용하면 데이터를 효율적으로 저장하고 관리할 수 있다.

A = [1, 30, 50, 80]

자료구조의 종류 (선형, 비선형)

자료구조를 배워야 하는 이유

특정 알고리즘을 구현하기 위해서 꼭 사용해야 하는 자료구조가 있을 수 있다.
또한 어떤 자료구조를 선택했는지에 따라서 사용할 수 있는 알고리즘이 달라진다.

알고리즘이란

문제를 해결하는 방법이다. 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법이다.

자주 쓰이는 문제 해결 방법(알고리즘)은 패턴화 → BFS, DFS, Binary, Search, Dijkstra 등

한 문제를 해결할 수 있는 알고리즘은 다양하다.

각 문제에 적합한 알고리즘을 선택할 수 있어야 한다.

알고리즘을 평가할 수 있어야 한다.

평가 기준

시간 복잡도(Time complexity)

공간 복잡도(Space Complexity)

구현 복잡도

 

시간 복잡도와 공간복잡도는 보통 trade-off 관계이다. 실행시간을 줄이기 위해서는 메모리를 더 사용해야 하고, 메모리 사용량을 줄이다보면 실행시간이 늘어나게 된다.

코딩 테스트에서는 보통 실행시간을 줄이는게 중요.

또한 시간복잡도를 미리 계산하여 문제 조건을 딱 맞추면서도 구현하기 쉬운 알고리즘을 선택할 수 있는 방법도 훈련하기

 

 

---

2. 자료구조와 메모리 구조 이해하기

자료구조란

데이터를 저장하고 관리하는 방식

데이터를 저장하는 곳

메모리

메모리(종류)

HDD , RAM

코드를 적고 저장하면 HDD에 저장
저장된 코드를 실행하면 RAM에 데이터가 올라감

 

우리의 관심 : RAM
비효율적인 자료구조를 사용하면 RAM 메모리 낭비, 프로그램 성능 저해 → 용도와 상황에 맞는 자료구조를 잘 선택해야 함

List

데이터를 순차적으로 나열해 놓은 집합

 

list를 array로 저장한다면 데이터가 메모리상에 연속적으로 저장됨

→ array는 데이터 접근이 쉽다.

list를 Linked list로 저장한다면 데이터가 메모리상에서는 불연속적으로 저장되지만, 다음 데이터의 위치를 가리킴으로서 연속성을 유지함

→ linked list는 데이터 추가, 삭제가 쉽다.

---

RAM 메모리는 전기신호를 저장할 수 있는 트랜지스터라는 작은 반도체 소재로 이루어져있음

트랜지스터의 전기가 ON인경우 → 1

트랜지스터의 전기가 OFF인경우 → 0

이를 이용해서 

이진수(binary Digit) 0과 1을 표현할 수 있다. → bit 라고 한다.

 

1bit : 01 → 2가지 숫자표현 가능

2bit : 01 01 → 4가지 숫자표현 가능

8bit = 1byte → 2^8 가지 숫자표현 가능

 

 

2진수는 앞에 0b를 붙여주고,

16진수는 앞에 0x를 붙여줌

 

하지만 편의상 2진수는 0b를 생략, 16진수는 0x를 생략하지 않음

 

 

2진수 → 1101 1001

10진수 → 13 9

16진수 → D 9

 

 

노트북 RAM 메모리는 1MB 이다.

1byte * 1024 = 1KB

1KB * 1024 = 1MB

 

이 넓은 메모리 공간 속에서 컴퓨터가 데이터를 찾으려면 지표가 있어야 함

그래서 하나하나의 byte마다 주소값(address)이 존재함

10진법으로 표현하면 너무 길어서 16진법으로 표현

 

 

1번째 Byte → 0x0 (주소 값)

2번째 Byte → 0x1 (주소 값)

820,101번째 Byte → 0xC8352 (주소 값)

2^20번째 Byte → 0xFFFFF (주소 값)

---

메모리 할당

 

int(정수) 데이터 타입 할당

C언어에서는 정수를 저장하는 int 데이터 타입이 있다.

Int 는 메모리에서 4byte를 차지하게 된다.

 

 

 

 

 

 

 

Char(문자) 데이터 타입 할당

컴퓨터는 숫자 밖에 저장을 할 수 없다.

Character(문자)를 숫자로 표현할 땐 ASCIIcode를 이용함

 

 

 

LIST

list를 구현하는 방법 : array / Linked list

 

 

 

 

Array

continuous(연속적)

 

입력: int array[4] = {1, 2, 3, 4}

 

각각 4byte씩 총 16byte의 메모리 차지

16byte 메모리에 2진법으로 저장

각 데이터를 가장 작은 address를 대표 address로 설정

 

 

Linked List

discontinuous(불연속적)

 

한 개의 노드당 메모리는 8byte(value + address)

 

 

 

 

 

 

---

3. [기본] 시간복잡도 Time Complexity

알고리즘

문제 해결 방법

 

문제 상황: 공 5개 오름차순 정렬

해결 방법 -> 알고리즘

1. 가장 작은 숫자를 찾아서 맨 앞에 놓는다

2. 남은 공들에 대해서 (1) 방법 반복

 

알고리즘을 보완할 때는 실행시간(Running Time)을 미리 계산할 수 있어야 한다.

 

예시1

int num1 = 57;        -> 2
int num2 = 50;        -> 2
int sum = num1 +num2; -> 3

print(sum)            -> 27

Running Time : 2+2+3+27 = 34

 

예시2

반복문의 실행시간은 반복횟수를 곱해주어야 한다.
100번 반복할 경우

int sum = 0;     -> 3

for i = 1 to 100 -> 3*100
    sum += 1     -> 2*100
    
print(sum);      -> 27

Running Time : 3+300+200+27 = 530

 

예시3

n번 반복할 경우

int sum = 0;     -> 3

for i = 1 to 100 -> 3*n
    sum += 1     -> 2*n
    
print(sum);      -> 27

Running Time : 3+3n+2n+27 = 5n+30

 

예시4

2중 반복문이 있을 경우

int sum = 0;         -> 3

for j = 1 to n -> 3  -> 3n
    for i = 1 to 100 -> 3n + 2n -> 5n^2 (5n을 n번 반복)
        sum += 1 
    
print(sum);          -> 27

Running Time : 3+3n+5n^2+27 = 5n^2+3n+30

---

복잡한 시간 복잡도를 간단히 표현하기 위해,

시간복잡도의 최고차수만을 이용해서 BIG-O 표기법을 쓸 수 있다.

 

BIG-O는 시간복잡도를 간단히 나타낼 수 있는 점근 표기법 중 하나

입력값의 형태에 따라서 시간복잡도는 달라질 수 있다.

예를 들면 숫자가 1,2,3,4,5 일때와, 5,4,3,2,1 일때는 시간복잡도가 다르다.

---

4. [심화] 시간복잡도 Time Complexity

앞으론 알고리즘 문제를 풀 때 4단계로 나누어서 풀 예정이다.

4단계

step1 : 문제 이해하기

step2. 접근 방법

step3. 코드 설계

step4. 코드 구현

코딩테스트에서 시간복잡도 활용법

1. 시간복잡도 이해하고 외우기

2. 제한 조건 보는 법(문제 이해하기)

3. 다양한 접근

제한 조건 보는 법

시간복잡도에 데이터의 크기를 넣어서 나 온 값이 10^8이 넘으면 시간제한 초과할 가능성이 있다. 

제약조건이 없는 문제들은 정답만 도출하면 되기 때문에, 효율적인 알고리즘을 고려할 필요는 없다.

 

Two sum 문제

----------[문제]------------------
정수가 저장된 배열 nums이 주어졌을 때, 
nums의 원소중 두 숫자를 더해서 target이 될 수 있으면 True 불가능하면 False를 반환하세요.
같은 원소를 두 번 사용할 수 없습니다.

input: nums = {4, 1, 9, 7, 5, 3, 16}, target : 14
input: nums = {2, 1, 5, 7},           target : 4

----------[제약조건]----------------
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

n을 찾는 방법 : 그 숫자가 커질수록 실행시간이 증가하는지를 확인하면 된다.

 

이 문제에서 nums의 길이가 길어질수록 연산을 해야 하는 횟수가 증가하고 결국 실행시간이 증가하기 때문에 원소는 nums.length라고 할 수 있을 것이다. 

그럼 nums.length가 원소이고, 원소는 10^8을 넘을 수 없으므로 시간복잡도는 O(1), O(logN), O(N), O(NlogN), O(N^2) 이 가능하다.