본문 바로가기

프로그래밍/알고리즘, 프로그래밍 언어35

[알고리즘] 인접 리스트(adjacency list) 자료구조- JavaScript 인접리스트 자료구조 - 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현 - 메모리를 효율적으로 사용하고 싶을 때 사용 - 구조 : 시작점을 key로, '도착점들의 배열'을 값으로 가지는 객체 형태 // 인접리스트 예시 by JavaScript { a: [c, d], // a에서는 c와 d로 향하는 간선 있음 b: [a, c, d], // b에서는 a, c, d로 향하는 간선 있음 c : [a], // c에서는 a로 향하는 간선 있음 d : [b, c] // d에서는 b와 c로 향하는 간선 있음 } 코드 작성 포인트 1. 인접 리스트를 객체에 담기 위한 변수 선언 2. 정점을 추가하는 메소드를 구현하되, 이미 있는 정점이면 그대로 놔두기 3. 두 정점 사이 간선을 추가하는 메소드 구현 : 키의 값인 배.. 2021. 8. 23.
[알고리즘] 조합(Combination)으로 배열의 요소 뽑기 (JavaScript) 조합으로 만들 수 있는 모든 배열을 리턴 조건 - 전달인자 : 문자열을 요소로 갖는 배열 - 출력 값 : 전달인자의 요소를 조합으로 뽑아서 배열을 만들고, 그것들을 모두 엘리먼트로 갖는 2차원 배열을 리턴 코드 작성 포인트 - 내장함수(pickOrNot)을 만들고 재귀를 사용해서, 빈 배열 result에 엘리먼트를 담기 - 배열의 인덱스를 모두 순회하면서 엘리먼트를 bucket에 담기 (담을 수도 있고 담지 않을 수도 있음) - 함수의 전달인자는 인덱스(idx)와 조합 엘리먼트를 담을 배열(bucket)이며, 인덱스는 0부터 1씩 올리기 - 재귀 탈출조건 : 인덱스(idx)가 배열의 범위를 벗어났을 때 탈출하기 코드 작성하기 const elements = ["가", "나", "다", "라"]; let r.. 2021. 8. 19.
[알고리즘] 순열(permutation)로 뽑은 모든 배열 구하기 (JavaScript) 문제설명 조건 - 재료가 담긴 stuffArr배열에서 0이 3개 이상인 엘리먼트는 제외 - 재료를 넣는 순서가 다르다면 다른 레시피로 취급 (조합이 아닌 순열임을 나타냄) - 사용할 재료가 없거나 choiceNum보다 작다면 빈 배열 리턴 전달인자 - stuffArr : number 타입을 요소로 갖는 배열이며, 요소는 중복될 수 없음 (예시 : [1, 10, 1100, 1111]) - choiceNum : number 타입으로 1 이상 stuffArr.length 이하 출력 값 - stuffArr에서 choiceNum개의 요소를 선택하여 만들 수 있는 모든 배열을 리턴하기 - stuffArr에서 choiceNum개의 요소를 선택하여 배열을 만들고, 그것을 엘리먼트로 삼는 2차원 배열을 리턴 - 조합 및.. 2021. 8. 18.
[알고리즘] 구현 - 보드게임 문제 (JavaScript) 문제설명 조건 - N * N의 크기를 가진 2차원 행렬 위에서 게임 진행 - 말은 상/하/좌/우로 이동 (U, D, L, R은 각각 상, 하, 좌, 우를 의미) - 말은 좌표 왼쪽 상단(0, 0)부터 시작하며, 움직일 때마다 그 칸 안의 요소인 숫자를 획득 - 방문한 곳을 또 방문해도 숫자를 획득 - 보드 밖을 나간 말은 OUT 처리하기 전달인자 - board : number 타입의 2차원 배열 (2 2021. 8. 18.
[알고리즘] 이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리 (Binary Search Tree) 자료구조 설명 - 자식 노드가 최대 두 개인 노드들로 구성된 트리로 각 노드에 값이 있음 - 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 구성 - 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 구성 - 좌우 하위 트리는 각각이 다시 이진 탐색 트리 (sub tree) 코드 작성 포인트 1. 노드에 값 입력 및 자식 노드 선언 - (루트)노드를 선언 후 입력 값을 할당하기 - '왼쪽 자식 노드'와 '오른쪽 자식 노드'를 선언 후 null을 할당하기 2. 자식 노드에 값을 추가하기 - 입력 값을 노드 값과 비교해서 작으면 왼쪽 자식 노드로, 크면 오른쪽 자식 노드로 이동 - 자식 노드에 값이 없으면 new .. 2021. 8. 11.
[알고리즘] 인접행렬(adjacency matrix) 구현 (JavaScript) 인접행렬(adjacency matrix) 자료구조 설명 - 인접 행렬(Adjacency Matrix) : 서로 다른 정점들이 인접한 상태인지를 2차원 배열로 나타냄 - 두 정점 사이의 관계 유무 확인에 용이하며, 가장 빠른 경로(shortest path)를 찾을 때 주로 사용 - 두 정점이 연결되어 있다면 1 (true), 두 정점이 연결되어 있지 않다면 0 (false) 코드 작성 포인트 1. 인접 행렬을 받을 변수 선언 및 할당 - const matrix = []; 2. 버텍스 추가하기 - matrix의 기존 엘리먼트들에 각각 0을 푸시해서 배열의 길이 늘려주기 - 새 엘리먼트는 new 키워드와 fill 메소드로 배열을 생성하여 matrix에 push 하기 3. 버텍스 사이 간선 추가/삭제 - 인덱스.. 2021. 8. 10.
[알고리즘] Tree 자료구조 구현 (JavaScript) Tree 자료구조 설명 - 무방향 그래프의 한 구조로 하나의 뿌리로부터 사방으로 뻗은 형태의 자료구조 - 계층적으로 표현되고 아래로만 뻗어나가 사이클이 없음 - 용어 노드(Node) : 트리 구조를 이루는 모든 개별 데이터 루트(Root) : 트리 구조의 시작점이 되는 노드 부모 노드(Parent Node) : 두 노드가 상하관계로 연결되었 있을 때 상대적으로 루트에서 가까운 노드 자식 노드(Child Node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드 리프(Leaf) : 트리 구조의 끝지점이고 자식 노드가 없는 노드 깊이(Depth) : 트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현 코드 작성 포인트 1. 현재 노드의 값을 받을 변수 선언.. 2021. 7. 29.
[알고리즘] Queue로 포장을 마치고 나가는 인원 수 구하기 문제 설명 조건 - 사람들이 박스 포장을 하기 위해 한 줄로 서 있음 - 짐이 많은 사람은 포장하는 박수의 개수가 많아 포장 시간이 길어짐 - 장소가 협소하여 먼저 온 사람이 박스 포장을 마치고 나가야지 뒷 사람도 나갈 수 있음 - 뒷사람이 포장을 모두 끝내도 앞 사람이 끝내지 못하면 나갈 수 없음 전달인자 - boxes : 앞 사람부터 차례로 포장해야 하는 박스 수가 담긴 배열 출력 값 - Number 타입을 리턴해야 하며 통틀어 최대 몇 명이 한꺼번에 나가는지 출력하기 코드 작성 포인트 방법1 - 전달인자 boxes가 queue가 되므로 따로 queue를 받을 변수를 선언할 필요는 없음 - queue에서 마지막으로 비워진 값을 담기 위한 last 변수 선언 - queue에서 곧 비워질 값을 받기 위한.. 2021. 7. 27.
반응형

티스토리툴바