Algorithm/개념 검색 결과

해당 글 11건

Heap

Heap 힙은 완전 이진트리를 활용하는 자료구조로 최대값과 최소값을 빠르게 구하기 위해 고안되었다 최대값이 root 노드가 되는 maxheap의 그림 보통 이진 트리로 표현되지만 아래의 그림처럼 배열로도 표현할 수 있으며 이 글에선 배열로 구현한 heap만 다룬다 삽입 heap의 끝 자리에 노드를 추가하고 자신의 부모와 비교해서 부모보다 크거나/작을 때 까지 부모와 위치를 바꾼다 삭제 heap의 루트 노드를 삭제한 뒤 heap의 제일 마지막 노드를 root로 옮긴 뒤 왼쪽과 오른쪽 자식들을 비교해서 크거나/작을 때 까지 자식과 위치를 바꾼다 코드 class Heap{ constructor(compare) { this.arr = []; this.compare = compare; } get size(){ r..
Algorithm/개념 2021. 6. 7. 12:40

비트 마스크

비트가 0과 1로 이루어져있다는 것을 이용해서 두 가지의 상태로 마스킹하여 일종의 자료구조 처럼 사용하는 방법이다 어떻게 사용하는지는 예시를 보면 알기가 쉽다 숫자 집합 {1,2,3,4}가 있다고 가정하고 이 집합에서 숫자를 뽑을 수 있는 경우의 수를 표현하려고 한다 배열의 경우 다음과 같이 참/거짓을 1/0으로 표현해서 배열로 표현할 수 있다 const arr = [1,1,1,1]; {1,2,3,4} const arr = [1,1,1,0]; {1,2,3 } const arr = [1,1,0,1]; {1,2, 4} const arr = [1,0,1,1]; {1, 3,4} ...비트의 경우 위에서 1과 0으로 표현했듯이 비트로도 똑같이 표현할 수 있다 1111 {1,2,3,4} 1110 {1,2,3} 11..
Algorithm/개념 2021. 5. 16. 12:55

Graph

그래프 무방향 그래프 G에 대해서 G = (V,E) 로 표기할 수 있다 여기서 V는 vertex, node로 불리는 정점 E는 edge, link로 불리는 정점을 잇는 간선을 나타낸다 위와 같은 그래프는 V = {1,2,3,4,5,6,7,8} E = {(1,2), (1,3), (2,3), ..., (7,8)} n = 8, 정점 개수 m = 11, 간선 개수 으로 나타낼 수 있으며 위와 같이 (1,2) (2,1)이 동일하다고 보는 것이 무뱡항 그래프이다 위와 같은 그래프는 (u,v) 와 (v,u)가 같지 않은, 방향 그래프라고 하고 가중치 그래프는 무방향, 방향 그래프 모두 될 수 있으며 간선에 가중치를 부여한 것을 가중치 그래프라고 한다 그래프의 표현 이러한 그래프들은 프로그래밍에서 어떻게 나타낼 수 있..
Algorithm/개념 2021. 4. 25. 14:00

2차원 배열 회전시키기

배열 회전 배열 arr [1,2,3] [4,5,6] [7,8,9] 를 에서 90도를 회전시키면 [7,4,1] [8,5,2] [9,6,3] 가 된다 배열을 나누어서 잘 살펴보면 arr[0]에 있던 원소들이 arr[0][0], arr[0][1], arr[0][2]로 각각 들어간 것을 볼 수 있다 이런 규칙에 따라서 function rotate (arr) { const temp = Array(arr.length).fill().map(()=>Array(arr.length).fill().map(()=>null)); for(let y=0; ynull)); for(let y=0; y{ return arr[arr.length-1-x][y] // return arr[arr.length-1-y][arr.length-1-x..
Algorithm/개념 2021. 4. 17. 14:27

Sort - 기본

정렬 알고리즘에는 여러가지가 있지만 구현하기 매우 간단한 3가지만 먼저 살펴보자 선택 정렬 선택 정렬이란 말 그대로 정렬해야 할 배열에서 가장 큰 수를 선택한 뒤 배열의 마지막 위치로 보내버리는 정렬이다 간단하게 작동 과정을 살펴보면 크기가 n인 배열에서 0부터 n-1까지 가장 큰 수를 탐색한다 가장 큰 수를 n-1의 위치에 있는 수와 바꾼다 n = n-1한 뒤 n이 0이 될 때까지 1번부터 다시 반복한다 시간 복잡도는 O(n^2) 버블 정렬 버블 정렬은 옆의 수와 비교한 뒤 비교한 수보다 크면 둘의 위치를 바꾸고 다시 옆의 수와 비교해서 자리를 바꾸며 찾아가는 정렬이다 [3,2,1,4,5]의 배열을 버블 정렬을 이용해서 정렬해보자 제일 첫 수인 3을 바로 옆에있는 2와 비교한다 3이 더 크니까 두개의 ..
Algorithm/개념 2020. 12. 18. 01:28

에라토스테네스의 체

에라토스테네스의 체 어느 수가 소수인지 판별하거나, 소수 한두개를 구할 때 보다는 범위 내에서 소수를 구하거나 대량으로 소수가 필요한 경우에 사용하면 좋은 알고리즘이다 방법 우선 원하는 범위 만큼의 배열을 만든 후 n부터 자기 자신을 제외한 모든 배수를 지운다 (1은 처음부터 제외, n = 2) 배열에 숫자가 남아 있다면 n += 1시켜준 뒤에 다시 1을 반복한다 이게 끝이다 구현 1 const sieve = Array(size).fill(true); for(let i=2; i
Algorithm/개념 2020. 12. 13. 21:01

Recursion - 순열

순열 순열은 멱집합의 반대?되는 개념이라고 생각하면쉽다 우리가 멱집합을 구할 때는 순서가 달라도 원소가 같으면 동일한 것으로 취급했지만 순열을 구할때는 순서가 다르면 다른 개체?로 취급한다 예를 들어 집합 {a,b,c}의 순열을 구하라 고 한다면 {a,b,c} {a,c,b} {b,a,c} {b,c,a} {c,a,b} {c,b,a} 총 6개의 집합을 구할 수 있다 문제 집합이 주어졌을 때 그 집합의 모든 순열을 구하는 재귀함수를 만들어라 접근 방식 위에 {a,b,c}의 순열을 나열하면서 느낀 것이 있는가? a + {b,c}의 순열을 b + {a,c}의 순열을 c + {a,b}의 순열을 구한 것과 같다 즉 앞의 원소를 제외한 나머지 원소의 순열을 구한 뒤에 합쳐주면 모든 순열을 구할 수 있다 코드 funct..
Algorithm/개념 2020. 12. 11. 13:22

Recursion - 멱집합

멱집합 주어진 집합의 모든 부분집합들을 원소로 가지는 집합이다 개수를 구하는 공식은 집합 원소의 개수가 n이라고 가정하면 2^n이다 {a,b} 라면 2^2= 4 {a}, {b}, {a,b}, {∅} 접근 방법 {a,b}의 모든 부분 집합을 구하는 방법은 a를 제외한 모든 원소의 부분 집합을 구한 뒤에 (1) (1)의 집합에 a를 추가해줘서 (2) (1),(2)를 다 나열하는 것이다 (1) = {b}, {∅} (2) = {a,b}, {a} 둘을 합치면 {a}, {b}, {a,b}, {∅}로 모든 원소를 나열할 수 있게 된다 여기서 재귀적인 부분을 찾아 재귀적으로 해결할 수 있다 내가 푼 코드 모든 부분 집합을 출력하는게 목적 접때 실패한 기억을 떠올려서 이번엔 base case를 먼저 작성하기로 했다 재귀..
Algorithm/개념 2020. 12. 9. 14:02

Recursion - N Queens Problem

n queens problem 체스판에 퀸의 동선이 겹치지 않게 놓는 문제 백 트래킹 백 트래킹은 퇴각 검색이라고 해석되며 트리에서 내가 원하는 해를 검색하는 알고리즘인데 검색할 때 내가 원하지 않는 노드를 만나게 되면 그 노드와 자식들은 검색할 필요가 없으므로 그 노드의 부모로 퇴각한 후 다른 자식을 검사하러 간다 접근 방법 2차원 배열을 선언하고 시작하려 했지만 필요가 없었다 어짜피 한줄에 하나의 말만 놓이게 되기 때문에 인덱스가 행을 안의 값이 열을 나타내는 것 예를 들어 board[2] = 3 은 3번째 줄에 3번째 열에 퀸이 있는 것 board = [1,3,3,3]은 보드판으로 나타내면 아래와 같다 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 내가 푼 코드 나는 풀다가 포기하고 결국..
Algorithm/개념 2020. 12. 8. 18:37

Recursion - 미로 찾기

미로 찾기 미로 찾기에는 여러가지 유형들이 있겠지만 목적지가 설정된 미로에서 주어진 좌표를 시작점으로 목적지까지 도달할 수 있는지 없는지 boolean값을 반환하는 함수를 만들려고한다 접근 방법 역시 알고리즘의 알자도 모르는 나 답게 어떻게 재귀적으로 접근하는지 모르겠어서 한번 봤다 내가 있는 현재 위치가 목적지인지 검사하고 그렇지 않으면 인접한 길로 간다 인접한 길로 넘어간 뒤에 다시 내 위치가 목적지인지 검사하고 그렇지 않으면 인접한 길로 간다.. 즉 처음에 넘겨준 좌표에서 좌표값만 수정해서 재귀 호출을 하면 되는 것이었는데 앞으로는 그냥 모르겠다고 할 것이 아니라 단계적으로 글을 써서 접근해 봐야할 듯 싶다 구현 const map = [[0,0,0,0], [0,0,0,0], [0,-2,0,0], [..
Algorithm/개념 2020. 12. 6. 14:40