반응형 Algorithm73 [알고리즘] 그래프 탐색 알고리즘 by javascript - BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 코딩 테스트의 단골 문제인 그래프 탐색 알고리즘에 대해 알아보자. 그래프 탐색 알고리즘의 개념을 이해하기 위해서는 당연히 그래프 자료구조를 알고 있어야 한다. 이 글은 자료구조를 알고 있다는 가정하에 탐색 알고리즘인 BFS와 DFS만을 정리하고자 한다. (그래프에서는 인접행렬과 인접 리스트 방식이 존재하는데, 본 글은 인접 리스트를 사용한 BFS/DFS 알고리즘이다.) 1. BFS - 너비 우선 탐색 너비 우선 탐색 (Breadth-first search)은 정점들과 같은 레벨에 있는 즉, 인접한 노드들을 먼저 탐색하는 방식이다. 이미지를 통해 쉽게 접해보고 너비 우선 탐색의 특징에 대해 알아보자. 너비 우선 탐색은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법으로 두 개의.. 2022. 4. 6. [백준] 1260번 : DFS와 BFS (실버Ⅱ) by node.js ▷ 문제 :1260번 : DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ▷ 해결 날짜 : 2022.04.04 ▷ 소요 시간 : 2시간 30분 ▷ 풀이 과정 : 문제는 너무나도 기본 문제라 아 그냥 DFS와 BFS를 사용해서 풀어보라는구나 싶을 정도의 내용이었다. 이 문제에서 중요한 건 기본적인 DFS와 BFS의 개념이고 입력으로 주어지는 간선은 양방향이다. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다. 어떤 두 정점 사.. 2022. 4. 4. [백준] 17427번 : 약수의 합 2 (실버Ⅱ) by node.js ▷ 문제 :17427번 : 약수의 합 2 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net ▷ 해결 날짜 : 2022.04.01 ▷ 소요 시간 : 1시간 ▷ 풀이 과정 : 문제는 그렇게 어렵지 않다. 주어진 숫자만큼 반복해서 돌면서 각 숫자의 약수의 합을 전부 더해준 값을 출력해주면 되는 문제였다. 그래서 문제는 5분 만에 풀었는데... let fs = require('fs'); let input = fs.readFileSync('./text.txt')... 2022. 4. 1. [알고리즘] 약수 구하기 알고리즘 by javascript 약수 구하는 알고리즘에 대해 알아보자. 기본적으로 약수란 인수를 나누어 떨어지게 하는 수를 의미하는데, 약수를 구하는 여러 가지 방법에 대해 하나씩 알아보자. (아래 예제 코드는 약수들을 구하는 알고리즘이기 때문에 약수의 합을 구하거나 등의 상황에 맞춰 바꿔 사용하면 된다.) 1. 단순하게 모든 수를 나눠서 약수 구하기 const getDivisors = (num) => { const divisors = []; for(let i = 1 ; i { const divisors = []; for(let i = 1 ; i { const divisors = []; for(let i = 1 ; i a - b); return divisors; } 제곱근을 이용하는 방식은 좀 이해가 필요하다. num 을 100이라고 .. 2022. 4. 1. [프로그래머스] 순위 검색(LV.2) by javascript - 2021 KAKAO BLIND RECRUITMENT ▷ 문제 : 2021 KAKAO BLIND RECRUITMENT - 순위 검색 LV. 2 { const condition = e.split(' ').filter(e => e != '-' && e != 'and'); const score = Number(condition.splice(-1)); return info.filter(v1 => condition.every(v2 => v1.includes(v2)) && v1.match(/\d/g).join('') >= score).length; }); } 아니나 다를까 "효율성 테스트" 문제였다. 당연히 효율성 부분에서 0점이 나와서 통과를 하지 못했는데, 몇 시간을 개선하다가 이렇게 풀면 도저히 안될 거 같아 몇몇 글을 통해 도움을 받았다. 이 테스트의 핵심은 .. 2022. 3. 26. [알고리즘] 이진 검색/탐색(Binary Search) 알고리즘 by javascript (ft. lower / upper bound) 이진 검색/탐색 알고리즘 (binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 절차를 지닌다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 이러한 검색 원리로 원하는 값이 나올 때까지 반복하는 알고리즘이다. 이진 탐색 알고리즘 원리는 아래 그림을 살펴보면 좀 더 이해가 쉬울것이다. 검색 원리상 위에서 설명했지만 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목푯값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 그렇다 보니 아무래도 선형 탐색.. 2022. 3. 26. [HackerRank] Staircase(Easy) by javascript ▷ 문제 : Staircase (Easy) Staircase | HackerRank Print a right-aligned staircase with n steps. www.hackerrank.com ▷ 해결 날짜 : 2022.03.18 ▷ 소요 시간 : 3분 ▷ 풀이 과정 : 그냥 단순하게 입력받은 수 만큼 "#"으로 이루어진 트리를 만드는건데, 우측 정렬로 만드는 것이다. # ## ### #### ##### ###### 문법 몇개만 알면 Easy난이도 답게 매우 간단하다. ▷ 구현 function staircase(n) { for(let i = 1; i 2022. 3. 18. [HackerRank] Diagonal Difference(Easy) by javascript 해커랭크 스타트! ▷ 문제 : Diagonal Difference (Easy) Diagonal Difference | HackerRank Calculate the absolute difference of sums across the two diagonals of a square matrix. www.hackerrank.com ▷ 해결 날짜 : 2022.03.18 ▷ 소요 시간 : 5분 ▷ 풀이 과정 : Easy 난이도의 몸풀기용 문제라 그런지 많이 쉽다. 그냥 이중 배열을 전달받아서 좌상우하, 우상좌하 대각선 끼리 더한다음 두 값을 빼주는 문제이다. 결과는 절대값으로 반환하면 해결된다. ▷ 구현 function diagonalDifference(arr) { // Write your code here re.. 2022. 3. 18. [프로그래머스] 수식 최대화(LV.2) by javascript - 2020 카카오 인턴십 ▷ 문제 : 2020 카카오 인턴십 - 수식 최대화 LV.2 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr ▷ 해결 날짜 : 2022.03.15 ▷ 소요 시간 : 1시간 20분 ▷ 풀이 과정 : 문제를 읽어보면 이 문제는 순열 문제라는것을 금방 파악할 수 있다. 문제는 수식을 전달 받았을 때 연산자 우선순위에 따라 가장 큰 값이 나오는 경우를 구하면 되는 문제이다. 다행히 수식과 연산자의 위치는 변하지 않고 우선순위만 바뀌는것이기 때문에, 우선순위에 대한 순열을 전부 구하고 계산을 진행해주는 식으로 접근하.. 2022. 3. 16. 이전 1 ··· 4 5 6 7 8 9 다음 반응형
