algorithm study

< 프로그램 실행의 단계 >인간이 이해 가능한 코드 -> 컴파일러 -> 프로그램 실행인간이 이해 가능한 코드 : c, c++...컴파일러 : 작성된 코드를 컴퓨터가 이해하기 쉽게 바꾼다 = 어셈블리어프로그램 실행 : 어셈블리어로 작성된 코드 컴퓨터가 실행정수 :

\-> 특정 기준을 적용하여 나열하는 것선택정렬삽입정렬버블정렬합병정렬퀵정렬< 선택정렬 >\-> 최솟값을 앞으로 이동시킨다배열에서 선택 정렬 시 처음 찾은 최솟값과 맨 앞의 값과 위치를 서로 바꾼다그 다음 두 번째 위치부터 위와 같은 과정을 다시 반복위 사진과 같이

<삽입정렬>\-> 원소를 차례대로 정렬된 배열에 삽입< 버블정렬 >\-> 인접한 원소를 비교하여 큰 수를 뒤로 보낸다선택, 삽입정렬과 조금 다르게 오른쪽 부터 정렬이 된다오른쪽 부터 큰 값들이 순서대로 정렬되는 것을 볼 수 있다

시간복잡도 -> 똑같은 문제를 해결해도 빠르게 해결하는 것이 중요 -> 같은 입력을 제공했을 때, 어느 프로그램이 더 빠른가? O(100) = O(1) / 상수는 다 같다

정수의 성질을 연구하는 분야약수와 배수소수 판별에라토스테네스의 체소인수 분해유클리드 호제법파스칼 삼각형<약수 구하기 구현><소수> -> 약수가 자기 자신과 1만 존재하는 정수소수 판별 구현 < 에라토스테네스의 체 >\-> 소수를 구하는 알고리즘배수들을

-> 문자 하나를 담는다 && 출력형식 = %c 컴퓨터는 문자를 숫자로 저장한다 -> 아스키 코드 **ex> char x = 'a'; 'a'에 대응하는 아스키 코드값이 x에 들어있다!! ** 하나의 문자는 하나의 아스키 코드를 가지고 있다 printf("%c

\-> 값을 입력받아 특정 연산을 수행하여 결과를 반환ex>int getSum(int a, int b, int c){ return a+b+c;}getSum 왼쪽의 int = 반환형 / return a+b+c 는 inta,b,c = 인자{} = 함수의 bodymain

\-> 값을 저장하는 것이 아닌, 값의 위치(주소)를 저장하는 변수ex>int\* myPointer; -->> int형 변수의 위치int a;a = 5;myPointer = &a; -->> int형 변수 a가 있는 위치printf("%d\\n", \*myPointe

\-> 함수를 호출할 경우, 변수의 값을 복사해서 넘김값을 넘기는 장점과 단점 장점 : 서로 관여하지 않는 완벽한 작업을 할 수 있다 단점 : 서로 관여하지 않기 때문에 불편한 경우가 꽤 많다\-> 값을 넘기는 대신, 값을 가지고 있는 변수의 주소를 넘긴다하지만 주소를

\-> 자기 자신을 호출하는 함수<값의 계산을 위한 두 가지 방법>순차적 계산법귀납적 계산법 : 구하려고 하는 값을 f(x)라 가정 / f(x)를 구하기 위해 다시 f(x)를 사용한다ex> n! = n \* (n-1)! -->> 팩토리얼 정의!0! = 1n^m

n^m을 재귀함수를 이용하여 계산하라 getPower(n, m) = n^m 을 반환하는 함수 // 말로 정의getPower(n, 0) = 1 // 기저 조건(해보나 마나 뻔한 것들)getPower(n, m) = getPower(n, m-1) \* n // 가정

ex> N개의 카드가 있고, 각각 1부터 N까지 번호를 가진다.이를 한 줄로 세울 수 있는 모든 경우를 출력해라.N중 for문을 구현해야함But, 위 방식으로는 N이 더 커진다면 구현하기 까다롭다int n = 3;doRecursion(int x){  // x번째 for

더 빠른 속도의 정렬 합병 정렬 : 재귀호출, 혹은 재귀적 구조를 이용한 정렬 퀵 정렬 : 재귀호출, 혹은 재귀적 구조를 이용한 정렬 힙 정렬 -->> O(nlogn) 만에 정렬 가능!! -> 지수함수의 역함수 보통 컴퓨터 공학에서 log를 쓰는 경우 그 밑이

\-> 정렬되어 있는 숫자들 중에서 특정 숫자를 찾는다숫자를 절반씩 지워나가면서 찾는다\-> 숫자를 몇번 2로 나눠야 1이되냐 = O(logn)숫자 찾기를 매우 많이 해야하는 경우에는 정렬을 한 뒤에 Binary Search를 하는 것이 좋다!ex> 배열에 숫자가 1

\-> Binary Search를 이용하여 문제를 해결하는 테크닉 ex> n개의 숫자와 s가 주어질 때, 몇 개의 연속된 값을 합해야 그 합이 s 이상이 되는가? (단, 1 <= n <= 100,000) \-->> Idea : 처음부터 끝까지 다 해봐야 하

\-> 자료를 저장하기 위한 주머니(자료를 저장하는 구조)\-> 목적에 맞는 이 주머니를 어떻게 디자인 할 것인가를 중점적으로 고민!목적을 성취하기 위한 자료구조를 디자인하는 능력 기르기\-> 가장 기본적인 자료구조\-> 변수의 나열 / 배열 또한 자료구조장점 : i

\-> 선형 자료구조LIFO - Last in First Out가장 최근에 삽입(push)한 원소가 먼저 나온다(pop)정해진 크기가 있다Stack overflow : 더 이상 들어가지 못하는 상황에서 넣으려 할때 발생Stack underflow : 빈 상태에서 더 빼

스택 -> 미로 찾기 같이 발자취를 기억하는 용도로 많이 사용"상태"의 의존관계가 생길 때 (재귀 호출에서 많이 사용)A라는 일을 마치기 위해서 B라는 일을 먼저 끝내야 할 때큐 -> A와 B가 서로 관련이 없지만 모두 하긴 해야할 때"상태"의 의존관계가 없을 때 사용

\-> 원소를 제거할 시, 가장 우선순위가 높은 원소를 제거 위 코드의 경우 over/underflow는 편의상 고려 x 큰 값이 우선순위가 큰 것으로 가정 pop 을 하는 경우 우선순위가 큰 것을 찾는데 시간복잡도 O(n) n이 100000이고 pop을 n만큼 하면

1. 문제를 정확히 이해한다 2. 문제를 해결하는 알고리즘을 설계한다 3. 알고리즘이 문제를 해결한다는 것을 증명한다(수학적으로) 4. 알고리즘이 제한시간 내에 동작한다는 것을 보인다(시간복잡도) 5. 알고리즘을 코드로 작성한다(한번에 디버깅 없이 한번에 하는 습관)

문제를 소문제로 분할 각각의 소문제를 해결 소문제의 해결 결과를 이용하여 전체 문제를 해결 재귀호출을 이용한 대표적인 정렬 -->> 처음에 mid = (start+end)/2로 나누는 것이 divide 앞 글에서의 ** 를 분할정복으로 풀어보자 배열을 반으로

\-> 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결분할정복법 : 위에서 밑으로 큰 문제를 쪼개면서 내려간다동적계획법 : 제일 작은 것 부터 하나하나 구해서 제일 큰 문제를 해결부분 문제를 말로 정의한다 = 무슨 값을 구할지를 정의(함수 정의)\-> T(i) 정

각 원소가 오른쪽 끝에 있다 가정했을 때 최대값들을 나열한 것이다ex> -4의 경우 -4 vs 2 - 4 vs 1 + 2 - 4 --> -1이 최대!n번째를 오른쪽 끝으로 했을 때 연속 부분 최대합은 n-1번째를 오른쪽으로 끝으로 하는 연속 부분 최대합을 이용하면 된

\-> 정점과 간선으로 이루어짐정점 = node = vertex간선 = edge차수 = 하나의 정점에 몇 개의 간선ex> 위 그림에서 노드2의 차수는 4사이클 = 자기 자신으로 돌아올 수 있는 경로\-> 현실세계의 많은 것들을 그래프로 나타낼 수 있다ex> 지하철 노선

깊이 우선 탐색(DFS) : 스택 사용너비 우선 탐색(BFS) : 큐 사용\-> 스택을 이용하여 그래프 순회스택 = 선행관계= 나를 먼저 방문하고 그 다음으로 인접한 노드를 차례로 방문(단, 방문했던 노드는 방문하지 않는다)모든 노드가 연결만 되어 있다면 DFS로 모든

최단경로 알고리즘 Strongly Connected Component(그래프 덩어리 몇개?) 최소 신장 트리(그래프에서 간선을 제거하여 트리형태로(간선들 합은 최소값을 유지하며)) -> A에서 B까지 가는 최단 경로는??? 다익스트라 알고리즘 : 하나의 정점에서 모