알고리즘
1.[알고리즘]정렬 알고리즘
기본적인 정렬 알고리즘에 대해 공부하고 코드를 작성해본다. 특정 리스트를 오름차순 정렬하는 상황을 가정하고 공부해본다.ex) 5,3,4,1,2 => 1,2,3,4,5간단하게 표현하면 제일 작은 수부터 차례로 찾아가며 정렬하는 방법이다.리스트 요소를 하나씩 서로 비교
2.[알고리즘]탐색 알고리즘
모든 경우의 수를 탐색하는 방법이다. 굉장히 직관적이고 놓치는 값 없이 탐색을 진행할 수 있다는 장점이 있지만, 경우의 수가 많아질 수록 탐색시간이 늘어나 비효율적인 방식이 된다.사람들이 즐기는 업앤다운 게임을 생각하면 이해하기 쉽다. 업앤다운 게임은 출제자가 숫자 하
3.[알고리즘]DFS, BFS
그래프는 리스트같은 구조와 달리 순차적이거나 선형적이지 않은 구조다. 정점(node)와 간선(edge)으로 구성되어있다. 쉽게 정점은 하나의 구역, 간선은 구역과 구역을 이어주는 길이라고 생각하면 된다.그래프 탐색에 사용되는 두 가지 자료가 있다.인접행렬(Adjacen
4.[알고리즘]재귀
재귀함수는 자기 자신을 다시 호출하는 함수를 의미한다. 재귀함수는 여러번 재귀를 할 수도 있는데, 이때 재귀는 재귀가 되지 않을 때까지 계속한다. 예를 들어 어떤 재귀함수가 있고 재귀함수 내용이 다음과 같다고 가정해본다. 파라미터로 숫자를 받고, 그 숫자가 0보다 크면
5.[알고리즘]다익스트라,플로이드와샬
다익스트라는 최단경로 알고리즘이다. 이때 최단경로란 특정 노드에서 다른 노드까지의 최단 경로를 의미한다.비용 배열(걸리는 시간or거리 같은 비용)과 방문 배열(방문했는지 안했는지)을 이용한다. 디폴트값으로 비용 배열에는 무한대값을 모두 넣고, 방문 배열에는 모두 방문하
6.[알고리즘]동적계획법
동적계획법은 복잡한 문제를 반복적인 작은 문제 단위로 나누어 푸는 방식을 뜻한다. 가장 흔한 방식이 메모이제이션을 이용하는 방법인데, 이는 간단하게 생각하면 중복된 연산을 피하기 위해 값들을 저장해나가며 값이 필요할 때 연산을 다시 하지 않고 메모이제이션으로 저장된 값
7.[알고리즘]탐욕법(그리디 알고리즘)
선택을 할 때마다 그 당시에 할 수 있는 가장 최선의 선택을 하는 알고리즘이다. 가장 쉬운 예는 돈을 지불하는 방식이다. 만약 어떤 물건을 샀고 그 가격이 1560원이라고 가정한다. 그럼 우리는 가장 적은 지폐와 가장 적은 동전을 사용해(동전갯수와 지폐갯수를 합했을 때
8.[알고리즘]이진탐색
사람들이 즐기는 업앤다운 게임을 생각하면 이해하기 쉽다. 업앤다운 게임은 출제자가 숫자 하나를 선정하면 나머지 사람들은 숫자를 유추하고 출제자는 유추한 숫자가 선정된 숫자보다 작은지 큰지를 알려주며 점점 범위를 좁혀나가 숫자를 알아맞추는 게임이다. 이진탐색도 마찬가지로