알고리즘, 자료구조
-
너비 우선 탐색 알고리즘 (BFS Algorithm)알고리즘, 자료구조/정리 2020. 7. 18. 15:45
DFS(Depth-First Search) 알고리즘에 이어 BFS(Breadth-First Search)를 정리해본다 BFS(Breadth-First Search) 탐색 알고리즘 중 하나인 BFS는 트리의 root 노드(그래프일 경우 임의의 노드)부터 시작해 모든 이웃 노드를 탐색한 뒤 아래 depth로 내려가 탐색을 반복하는 방식이다. 즉 시작 노드에서 가장 가까운 노드들을 모두 탐색하고, 그다음으로 가까운 노드들을 모두 탐색하는 것. DFS 알고리즘과 달리 BFS 알고리즘은 재귀 함수로 구현할 수 없다. 현재 노드에서 가까운 노드들을 모두 탐색한 뒤 그다음으로 가까운 노드들을 탐색하기 위해선 queue(FIFO: First In First Out)을 이용해야 하고, 어떤 노드를 방문했는지에 대해 검사..
-
깊이 우선 탐색 알고리즘 (DFS Algorithm)알고리즘, 자료구조/정리 2020. 7. 13. 14:32
탐색 알고리즘 문제를 볼때마다 멍해지는 관계로 이번 기회에 확실히 짚고 넘어가야겠다. 이번 포스트에서는 DFS를 정리한다. DFS (Depth-first search) 미로 문제 해결 전략으로 연구된 DFS는 트리 및 그래프 구조를 탐색하는 알고리즘 기법이다. 트리의 경우엔 root node부터, 그래프의 경우엔 임의의 node부터 맨 밑까지 탐색하면 되고, 이전에 방문한 노드는 다시 방문하지 않는다. 그림으로 표현하면 아래와 같다. 일반적으로 DFS 알고리즘은 그래프 전체를 탐색하는데 사용한다. 시간 복잡도는 O(|V|+|E|)으로 그래프 사이즈만큼의 선형 시간이 걸린다. (V는 정점의 수, E는 간선의 수를 나타낸다) 즉, 정점이 늘어나는만큼 시간도 오래 걸리기 때문에, 탐색 과정이 시작 노드에서 한..
-
[Javascript] 프로그래머스 보석 쇼핑알고리즘, 자료구조/프로그래머스 2020. 7. 10. 23:27
문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 풀이 과정 결론부터 말하면 이 문제는 단순 이중 for문으로 해결할 수 없다. 만약 이중 for문으로 해결하려고 한다면 정확성은 다 통과되지만 효율성에서 시간 초과될 것이다. 맨 처음 내가 작성한 코드는 아래와 같다. function solution(gems) { let result = [], minLen = 100000; let unique = [...new Set(gems)]; let gemLen = ..
-
[Javascript] 프로그래머스 큰 수 만들기알고리즘, 자료구조/프로그래머스 2020. 7. 3. 11:44
문제 https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 어떤 숫자에서 k개 만큼의 숫자가 제거되었을 때 만들 수 있는 가장 큰 수를 구해야되는 문제이다. Greedy 알고리즘을 사용해 문제를 풀었고, 여기서 Greedy 알고리즘이란 매 순간 최선이라 판단되는 선택을 하면 가장 좋은 방법으로 문제를 해결할 수 있다라고 가정하는 아이디어에서 나온 것이다. 즉 미래는 생각하지 않고 당장 눈 앞에 닥친 문제만 생각하면 되는 것이다. 물론 이 방법으로 모든 문제가 풀리는 것은 아니지만 계산 시간이 적게 걸린다는 장점이 있기 때문에, Greedy 알고리즘으로 풀 수 있는 문제라면 이를 사용해 문제를..
-
[Javascript] 프로그래머스 프린터알고리즘, 자료구조/프로그래머스 2020. 6. 30. 16:27
문제 https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린�� programmers.co.kr 대기목록 맨 앞에 있는 문서(J)를 대기목록에서 꺼낸다 → 나머지 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록 맨 마지막에 넣는다 → 그렇지 않으면 J를 인쇄한다. 솔루션 함수의 파라미터에는 문서의 중요도가 순서대로 담긴 배열 priorities, 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 locati..
-
[Javascript] 프로그래머스 카펫알고리즘, 자료구조/프로그래머스 2020. 6. 29. 20:05
문제 https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 �� programmers.co.kr 완전 탐색으로 분류된 문제지만 나는 완전 탐색으로 접근하진 않았다. 이 문제에서 생각해야 될 부분은 yello로 주어진 파라미터가 모두 카펫 안에 들어가야 된다는 것이다. 풀이 과정 function solution(brown, yellow) { let answer = []; // row: 카펫의 가로길이, col: 카펫의 세로길이 // row >=..
-
[Javascript] 프로그래머스 H-index알고리즘, 자료구조/프로그래머스 2020. 6. 26. 15:02
문제 https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index이다. 그러니까 H-Index는 무조건 과학자가 발표한 논문 n편 이하의 숫자가 된다. 풀이방법 function solution(citations) { var answer ..
-
[Javascript] 프로그래머스 기능 개발알고리즘, 자료구조/프로그래머스 2020. 6. 26. 14:20
문제 https://programmers.co.kr/learn/courses/30/lessons/42586# 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 �� programmers.co.kr 작업 진도, 작업 속도가 주어지고 둘의 합이 100 이상 되어야 배포가 가능하다. 또한 뒷 작업이 먼저 완료되었다 하더라도 앞 작업이 배포되어야 뒷 작업도 배포될 수 있다. 즉, 뒷 작업이 앞에 작업보다 먼저 배포될 수 없다. 큐 개념을 이용해 문제를 풀었고, 배포된 작업들은 배열에서 삭제되기 때문에 시간 복잡도는 O(log n)이 되지 않을..