2022-03-02 T.I.L 옮겨야됨

정종훈·2022년 3월 2일

임시

목록 보기

2/11

알고리즘 테스트 Intro

“Life is C (Choice) between B (Birth) and D (Death).” - 프랑스 철학자 Jean-Paul Sartre -

사람은 인생을 살아가면서 항상 선택의 기로에 섭니다.

선택에 따라서 결과가 달라지고, 그 결과가 돌이킬 수 없는 경우도 있습니다.

그 많은 선택의 결과를 항상 확인할 수 있을까요?

영화 속의 히어로는 빌런으로부터 세상을 지키기 위해 수없이 많은 선택을 합니다.

그리고 그 선택의 결과가 의도와 다른 경우, 반복해서 시간을 되돌립니다. 수없이 많은 반복 끝에,

빌런으로부터 세상을 지킬 수 있는 딱 한 가지 경우의 수를 확인하고, 결국 빌런을 물리칩니다.

도르마무, 거래를 하러 왔다.

선택과 경우의 수는 영화뿐만이 아니라 우리 주변에서도 발견할 수 있습니다.

예를 들어 서울에 사는 B는 제주도에 사는 A를 만나기 위해 이동하는 과정에서 상대적으로 비싸지만

시간을 아낄 수 있는 비행기편과 시간이 많이 들지만 상대적으로 저렴한 배편 중에서 이동 수단을

선택할 수 있습니다. 이동수단으로 비행기를 선택할 때에도 가격대,

혹은 출발 시간대에 따라 많은 선택지가 있습니다

. 만약 최악의 선택을 한다면, 시간적으로 만족하지 못하고 가격도 비싼 교통편을 선택하는 일이 발생할 수 있습니다.

우리는 상황에 따라 매번 다른 문제를 마주치고, 이 문제를 해결하며 살아 갑니다.

영화에서처럼 모든 경우의 수를 경험하고 최선의 수를 선택한다면,

가장 좋은 선택이 될 수 있을 겁니다.

그러나 시간을 되돌리는 일은 현실적으로 일어날 수 없기 때문에,

알고리즘을 이용해 문제를 해결해야 합니다.

Achievement Goals

알고리즘이 무엇인지 설명할 수 있다.
알고리즘 문제를 이해하고 전략을 세울 수 있다.
알고리즘 풀이에 필요한 수도 코드를 작성할 수 있다.
수도 코드에서 세운 전략을 코드로 구현할 수 있다.
내가 구현한 알고리즘을 자바스크립트 언어로 설명할 수 있다.

prerequisite

기본적인 자료 구조(stack, queue, tree, graph 등)에 대한 이해
모듈 단위로 나누어 생각하는 법

Intro to Algorithm

알고리즘이란 무엇일까요?

알고리즘은 문제를 해결하는 최선의 선택

아니 그래서 최선이 뭐냐고?? 몰?루

그래도 최선을 선택할수있는 하나의 방법을 알려줄꺼임 ㄳ

문제를 이해하라

입출력, 제한사항, 주의사항을 토대로 문제가 무엇인지를 이해해야함

이거 완전 폴리아의 문제 해결전략 4단계???

문제를 어떻게 해결할 수 있을지, 전략 세우기.. 맞네.. 폴리아님... 그립습니다..

연습장에 전체적인 그림 그리기. 페어와 상의
수도코드를 작성하기 전, 인간의 사고로 문제를 해결할 수 있어야 함!
코드를 작성하기 전에 페어와 수도코드를 먼저 작성하자!
막혔던 생각이 페어에게 설명을 하면서 해결되는 경우도 있음!

문제를 코드로 옮기자.

코드의 최적화!

Notes(이사람이 한 말임)

그대로 옮겨놓겠음

앞으로 우리가 개발자로서 만나게 될 대부분의 개발 태스크는 알고리즘 문제만큼 어렵지 않습니다.

그러나 새로운 문제에 봉착했을 때, 전략과 알고리즘을 구상하여 실제로 코드로 구현해 보는 경험은

매우 중요합니다. 많은 기업에서 주니어 개발자를 채용할 때에, 알고리즘 풀이를 통해 지원자의 역량

을 가늠합니다. 알고리즘 풀이를 통해 지원자의 로직과 문제해결 방식을 확인하고, 이를 통해 개발자

다운 사고방식을 보게 됩니다. 이 스프린트를 통해 개발자의 사고방식을 연습하세요.

이번 유닛에서는 문제를 해결하여 정확한 답안을 출력해야 합니다. 그러나 정확한 답을 찾는 일이 최

종목표는 아닙니다. 이 유닛의 최종 목표는 문제를 해결하기 위해 고군분투하는 그 과정을 경험하고,

개발자로서 더 성장하는 겁니다. 어렵지만 끝까지 포기하지 않는 것이 답을 내는 것보다 더 중요합니

다. 문제를 풀지 못했다고 해서 절대로 좌절하지 마세요. 누구에게나 처음은 있는 법이니까요.

Time Complextity

문제를 해결한 다음에

효율적인 방법으로 문제를 해결했는지도 중요함! (나는 이떄까지인생은 반대였음...
효율적인 방법을 고민하다가 문제자체를 해결하지 못한경우가 너무 많음...)

시간 복잡도

시간 복잡도가 뭔데?

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

Big-O 표기법

시간 복잡도를 표기하는 방법은 다음과 같음.

Big-O(빅-오) : 최악의 시간 : 고객님 최대 1시간뒤에 오세요(10분뒤 끝날수도 있음)
Big-Ω(빅-오메가) : 최선의 시간 : 고객님 적어도 15분은 걸립니다(하루걸릴수도있음)
Big-θ(빅-세타) : 평균의 시간 ( 대충 30분정도 걸립니다 ...?)

딱 봐도 빅오가 일처리 할때 좋을것같음. 왜냐? 내 스케쥴을 예측 할수 있기 때문에

그래서 최악의 경우를 고려하자!

O(1)

입력값이 증가하더라도 시간이 늘어나지 않음. constant 상수함수임 ㅋㅋ

function O_1_algorithm(arr, index) {
	return arr[index];
}

let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

arr가 커지더라도 무조건 인덱스 딱 하나만 출력할 수 있음!

O(n)

linear 일차함수임 ㅋㅋㅋ

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

O(2n) , O(3n)은 없음. 일차 변환처럼 일차식의 계수는 필요없음 n이 커지면 의미가 없으니

O(log n)

여기서 log의 밑은 2임. 컴퓨터는 2진이니. 어 2진법?

되거나 안되거나? 밑이거나 위거나? 큰수거나 작은수거나? 반 가를떄!!

function func (num, arr,sIdx,eIdx){
  if (sIdx > eIdx){
    return -1;
  }
  let idx = parseInt((sIdx + eIdx)/2);
  if (arr[idx] === num){
    return idx;
  }else if (arr[idx] > num){
    return func(num, arr, sIdx,idx-1);
  }else{
    return func(num, arr, idx+1, eIdx);
  }
}

반갈죽 이진

O(n^2)

quadratic(이차임) 여기서 부터 큰일남...

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}

function another_O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
			// do something for 1 second
			}
		}
	}
}

O(2^n)

아 이건좀 아니지 않나요

그 종이42번 접으면 달까지 갈 수 있다는 논리 그거

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
  
  
	return fibonacci(n - 1) + fibonacci(n - 2);
}

코딩테스트때 시간복잡도 예측 방법

![](https://images.velog.io/images/mageboy/post/b13e0bd4-38ca-4775-831a-1a0576b60548/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7,%202022-03-02%2012-10-18.png

질문

가장 빠른/느린 시간 복잡도는 무엇일까요?
O(1) O(2^n)
효율적인 알고리즘을 구성했다 함은 무엇을 의미할까요?

내가 작성한 코드 내용에 비해 시간 복잡도가 얼마나 빠른가? xx
입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘

시간 복잡도는 A와 B의 비례함이 어느 정도인지를 나타냅니다. A와 B는 무엇일까요?

연산 횟수와 시간!

Greedy Algorithm

매 선택의 순간마다 무지성으로 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법.

아니 근데 최적의 상황이 머?임????

선택 절차 : 현재 상태에서의 최적의 해답을 선택(그건 본인의 과저의 경험으로인한 판단?)
적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사
해답 검사 : 원래의 문제가 해결되었는지 검사 후, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

뭐야 모르겠는데?? 그래서 예시 줄거임 . ㅇㅋ

Example1

김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.

문제상황 : 동전의 개수를 최소한으로 줘야함 =>

선택 절차 : 현재 가치가 가장 높은 동전을 우선 선택 :500원 무지성 집음
적절성 검사 : 500원 8개 까지는 괜찮은데 9개 집으면 안됨. 그러면 마지막 500원 동전은 삭제하고 1번으로 돌아가 한 단계 작은 동전을 선택
해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사.

액수가 부족하면 1번 과정부터 다시 반복.

결과 : 가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤,
이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 줍니다.

Example2

김코딩이 아르바이트를 하러 간 사이에, 안타깝게도 김코딩의 집에 도둑이 들었습니다. 도둑의 가방은 35kg까지의 물건만 담을 수 있고, 김코딩의 집에는 4개의 물건이 있습니다.

만약 탐욕 알고리즘을 쓴다면?

가방에 넣을 수 있는 가장 비싼 물건을 넣습니다.
그다음으로 넣을 수 있는 물건 중 가장 비싼 물건을 넣습니다. 이 과정을 반복함

근데 알다시피 이것으로는 최적의 답을 못찾음.

컴퓨터랑 반지를 가방에 넣는게 빠르거든.

그 방법은 수학적으로 나중에 하고 우선 그래서 목적은

탐욕 알고리즘은 항상최적의 결과를 보장하지 못한다 임

그럼 탐욕 알고리즘은 언제 쓰는데???

탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 주지 않음.
최적 부분 구조: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됨. 그게 뭔데?? 아 일단 나중에 할거임 ㅇㅋ

탐욕 알고리즘은 최적의 결과를 도출하지는 않지만 최적에 근사한 값을 빠르게 도출할수있는 장점이 있음.

이거 완전 뉴턴/랩슨 법????

Implementation(구현)

알고리즘 문제를 푼다는 것은,

내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것과 같음. 개꿀잼

근데 이걸 왜 코딩 테스트로 쓰냐고 현업에 쓸 것도 아니면서???? =>

정해진 시간 안에 빠르게 문제를 해결하는 능력 을 보기 위함.
본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야하고,
문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로!

지문을 매우 길게 작성하거나
까다로운 조건이나 상황을 붙인다거나
로직은 쉽지만 구현하려는 코드가 굉장히 길어진다거나

따라서 깊은 집중력과 끈기가 필요함!!

구현 능력을 보는 대표적인 사례에는 완전탐색(브루트 포스)와 시뮬레이션이 있음!

완전 탐색

그냥 1부터 100까지 다 스캔하는것 . 무조건 풀 수 있지만 시간이 많이 걸림...

우리는 두 가지를 고민해야함.

문제를 해결할 수 있는가
효율적으로 동작하는가

시뮬레이션

모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형

문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있음

Example

무엇을 위한 조직인지는 모르겠지만, 비밀스러운 비밀 조직 '시크릿 에이전시'는 소통의 흔적을 남기지 않기 위해 3 일에 한 번씩 사라지는 메신저 앱을 사용했습니다. 그러나 내부 스파이의 대화 유출로 인해 대화를 할 때 조건을 여러 개 붙이기로 했습니다. 해당 조건은 이렇습니다.

캐릭터는 아이디, 닉네임, 소속이 영문으로 담긴 배열로 구분합니다.

소속은 'true', 'false', 'null' 중 하나입니다.

소속이 셋 중 하나가 아니라면 아이디, 닉네임, 소속, 대화 내용의 문자열을 전부 X로 바꿉니다.

아이디와 닉네임은, 길이를 2진수로 바꾼 뒤, 바뀐 숫자를 더합니다.

캐릭터와 대화 내용을 구분할 땐 공백:공백으로 구분합니다: ['Blue', 'Green', 'null'] : hello.

띄어쓰기 포함, 대화 내용이 10 글자가 넘을 때, 내용에 .,-+ 이 있다면 삭제합니다.

띄어쓰기 포함, 대화 내용이 10 글자가 넘지 않을 때, 내용에 .,-+@#$%^&*?! 이 있다면 삭제합니다.

띄어쓰기를 기준으로 문자열을 반전합니다: 'abc' -> 'cba'

띄어쓰기를 기준으로 소문자와 대문자를 반전합니다: 'Abc' -> 'aBC'
시크릿 에이전시의 바뀌기 전 대화를 받아, 해당 조건들을 전부 수렴하여 수정한 대화를 객체에 키와 값으로 담아 반환하세요. 같은 캐릭터가 두 번 말했다면, 공백을 한 칸 둔 채로 대화 내용에 추가되어야 합니다. 대화는 문자열로 제공되며, 하이픈- 으로 구분됩니다.

문자열은 전부 싱글 쿼터로 제공되며, 전체를 감싸는 문자열은 더블 쿼터로 제공됩니다.

예: "['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'"

문제는 대화 내용이 담긴 문자열을 입력받아, 문자열을 파싱하여 재구성을 하려고 합니다.

예시를 이용하여 순차적으로 작성해 봅시다.

"['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'" 입력값으로 받은 문자열을 각 캐릭터와 대화에 맞게 문자열로 파싱을 하고, 파싱한 문자열을 상대로 캐릭터와 대화를 구분합니다.

첫 번째 파싱은 - 을 기준으로 ['Blue', 'Green', 'null'] : 'hello. im G.', ['Black', 'red', 'true']: '? what? who are you?' 두 부분으로 나눕니다.

두 번째 파싱은 : 을 기준으로 ['Blue', 'Green', 'null'] 배열과 'hello. im G.' 문자열로 나눕니다.

배열과 문자열을 사용해, 조건에 맞게 변형합니다.

소속이 셋 중 하나인가 판별합니다.
['Blue', 'Green', 'null'] 아이디와 닉네임의 길이를 2진수로 바꾼 뒤, 숫자를 더합니다: [1, 2, 'null']
'hello. im G.' 10 글자가 넘기 때문에, .,-+@#$%^&* 를 삭제합니다: 'hello im G'
'hello im G' 띄어쓰기를 기준으로 문자열을 반전합니다: 'olleh mi G'
'olleh mi G' 소문자와 대문자를 반전합니다: 'OLLEH MI g'
변형한 배열과 문자열을 키와 값으로 받아 객체에 넣습니다.
{ "[1, 2, 'null']": 'OLLEH MI g' }

음.... ㅇㅋ

여튼

문제에 대한 이해를 바탕으로 제시하는 조건을 하나도 빠짐없이 처리해야 하며

하나라도 놓치면 통과할 수 없게되고 길어진 코드 때문에 헷갈릴 수도 있으니 주의

Dynamic Programming 동적 계획법

작은 문제들아!

작은 문제에서 출발함. 근데 얘는 모든 경우의 수를 조합해 최적의 해법을 찾는 방식

주어진 문제를 여러 개의 하위 문제로 나누어 풀고
하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식!!

DP는 두 가지 가정이 만족해야함.

큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다

예를 들어

function fib(n) {
	if(n <= 2) return 1;
	return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...

피보나치는 작은 문제(fib(2), fib(3)) 의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있음!!

작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다!

이 그림에서 A - D까지 최단 경로는 A - B - C - D 임

근데 그것을 A - C 로 줄이고 다시 A - B 로 줄여서 먼저 최적의 해법을 찾은다음 결합하는 것!

Recursion + Memoization

Memorization의 정의

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술!

Example

function fibMemo(n, memo = []) {
		// 이미 해결한 하위 문제인지 찾아본다
    if(memo[n] !== undefined) return memo[n];
    if(n <= 2) return 1;
		// 없다면 재귀로 결괏값을 도출하여 res 에 할당
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
    memo[n] = res;
    return res;
}

큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 이 방식을 Top-down방식이라고도 함

Iteration + Tabulation

이번에는 반복문이다!

Example

function fibTab(n) {
    if(n <= 2) return 1;
    let fibNum = [0, 1, 1];
		// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다 
    }
    return fibNum[n];
}

이는 작은 문제에서 시작하여(i = 0, i = 1 ...) 큰 문제를 해결해 나가는 방법 Botton-up

크롬 개발자 도구에서 함수 실행 시간을 측정하는 하나의 방법

var t0 = performance.now();
fib(50); // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')

이걸로 측정해보면
Top-down(runtime: 0.20000000018626451ms)과
Bottom-up(runtime: 0.10000000009313226ms)의 소요시간은 Botton-up이 더 빠르네??

저의 개인적인 고견은.. Bottom-up은 재귀 호출하지 않기 때문에 시간과 메모리 사용량을 줄일수 있다는 것!

탑 다운의 장점은 설계가 쉬움 => 큰 것을 작은 요소로 분해하는 것에 익숙함.

정종훈

괴발개발자에서 개발자로 향해보자

이전 포스트

SEB Full 37기 75일차

다음 포스트

2022-03-02 T.I.L 옮겨야됨

임시

알고리즘 테스트 Intro

Achievement Goals

prerequisite

Intro to Algorithm

알고리즘이란 무엇일까요?

Notes(이사람이 한 말임)

Time Complextity

시간 복잡도

Big-O 표기법

O(1)

O(n)

O(log n)

O(n^2)

O(2^n)

코딩테스트때 시간복잡도 예측 방법

질문

Greedy Algorithm

Example1

Example2

Implementation(구현)

완전 탐색

시뮬레이션

Example

Dynamic Programming 동적 계획법

Recursion + Memoization

Example

Iteration + Tabulation

Example

크롬 개발자 도구에서 함수 실행 시간을 측정하는 하나의 방법

SEB Full 37기 75일차

SEB Full 37기 76일 차

0개의 댓글