본문 바로가기

Algorithm11

[Algorithm] DP - Coin change 안녕하세요 :) 개발자 sean입니다. 휴가 다녀오고 오랜만에 포스팅을 하는 것 같습니다. 2주간 코드는 거들떠 보지도 않고 놀다 오니 코드 감각이 떨어진 듯하여 오늘은 감을 끌어올릴 겸 dp 문제를 풀어보았습니다. 아니나 다를까 코딩 실력이 default로 돌아갔더군요... The Coin Change Problem이란 문제를 풀어보았는데 결국에는 못풀어서 다른 사람의 풀이를 참고해 풀었습니다. 이럴 땐 정말 자괴감이 들곤 합니다만 뭐 어쩌겠습니까 배울 것이 많이 남아 있다는 건 성장할 수 있는 여지가 많이 남아있다는 것이고, 또 어플만드는데는 전혀 문제가 되지 않는걸요 껄껄.. ㅠㅠ 그래도 포기하지 않고 끝까지 풀이에 성공한것을 위안 삼아 멘탈 잡고 한번 풀이를 해보도록 하겠습니다. 제가 풀이한 정답.. 2023. 2. 9.
[Algorithm] queens-attack-2 풀이 안녕하세요 개발자 Sean입니다. 오늘은 queens attack이라는 문제를 풀어보았습니다. 해답 코드는 아래와 같습니다. function queensAttack(n, k, r_q, c_q, obstacles) { // Write your code here let left = 1; let right = n; let high = n; let bottom = 1; const equation = (x) => x + (r_q - c_q); const revEquation = (x) => -x + (r_q + c_q); const getX = (y) => y - (r_q - c_q); const getrevX = (y) => - y + (r_q + c_q); let hightLeft = revEquation(1.. 2022. 12. 3.
[Algorithm] non-divisible-subset 문제 풀이 안녕하세요, 개발자 Sean입니다. 재미 삼아 코딩 문제나 풀어볼까... 하고 HackerRank의 문제를 풀어보았는데요, 해결하는데 꼬박 하루가 걸려버렸네요 ㅠㅠ 시간 복잡도 때문에 런타임 에러가 발생해 꽤나 애를 먹다가 결국 다른 분들의 풀이를 한번 살펴봤는데 풀이를 봐도 이해가 안 되는 부분이 있어 고생을 꽤나 했습니다. 일단 저의 풀이는 아래와 같습니다. function nonDivisibleSubset(k, s) { // Write your code here const counter = new Array(k).fill(0); s.forEach((el, i) => { counter[el%k]++; }) let result = 0; if (counter[0] > 0) result++; if (k%2.. 2022. 11. 28.
[Subset] reduce와 map을 이용해 subset 구하기 const getAllSubsets = (arr) => { return arr.reduce((subsets, value) => { return subsets.concat(subsets.map((subset) => [...subset, value])) }, [[]]) }; 2022. 11. 27.
[Algorithm] 다익스트라 알고리즘 인접리스트로 풀기 인접 리스트로 풀기 다익스트라 문제의 경우 인접 리스트로 푸는 경우가 많다고 한다. 왜냐하면 힙을 이용해 시간 복잡도를 줄일 수 있기 때문이다. 여기서 힙이란 스택과 대비되는 자료구조 중의 하나로 개발자가 직접 할당해서 사용하는 메모리 부분이다. 그렇다면 아래 문제를 한번 인접리스트로 풀이해 보겠다. 문제 무방향 그래프의 한 정점(vertex)에서 다른 정점까지의 최단 거리를 리턴해야 합니다. 입력 인자 1: num number 타입의 자연수 그래프에 존재하는 정점의 개수 정점은 1부터 num까지 존재 인자 2: edges 배열(간선에 대한 정보)을 요소로 갖는 배열 edges [i]는 number 타입을 요소로 갖는 배열 edges [i]. length는 3 edges [i]의 요소는 차례대로 정점, .. 2022. 3. 25.
[Algorithm] 플로이드 와샬 알고리즘 이번에는 최단거리 알고리즘의 마지막! 플로이드 와샬에 대해 알아보자. 플로이드 와샬은 다른 최단거리 알고리즘 중에서 제일 느리다. 왜냐하면 딕스트라나 벨만 포드는 모두 출발점이라는 개념이 있는데 플로이드 와샬은 그런 거 모르겠고 모든 노드의 최단거리를 다 구해 버리기 때문이다. 자바스크립트 구현 코드 const INF = Infinity; const floydWarshall = function(dist){ const len = dist.length; for (let i = 0; i dist[j][i] + dist[i][k]) dist[.. 2022. 3. 25.
[Algorithm] 벨만포드 알고리즘 오늘은 딕스트라 알고리즘에 이은 벨만 포드! 음수의 값이 있을 때 최단거리를 구하는 데 사용할 수 있다. 실제 상황에서 음수 거리라는 게 있을 수는 없지만... 저번 코딩 테스트 문제로 나와 당황했던 기억이 있으니 오늘 한번 풀어보려고 한다. 방식은 아래와 같다. 1. 노드 수만큼 최단거리를 표시하는 배열을 생성한다. 이 때 시작점을 제외하고는 INF 값을 넣는다. 시작점은 0을 넣어준다. 2. 노드 수 만큼 루프 하면서 모든 간선을 루핑 하는데 이때 최단거리에서 INF가 아닌 시작점이면서 도착점까지의 거리에 가중치를 더했을 때 현재의 거리보다 작아진다면 최단거리 배열을 수정한다. 3. 마지막으로 위 과정을 한번 더 적용했을 때 만약 최단거리가 또 수정된다면 이는 무한 루프에 빠진 것으로 정답이 없는 게.. 2022. 3. 25.
[Algorithm] 다익스트라 알고리즘 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. 다른 최단거리 알고리즘으로는 벨만 포드와 플로이드 와샬 알고리즘이 있는데 이는 다른 포스팅에서 다루기로 하겠다. 다익스트라 알고리즘의 핵심은 1. 노드간의 거리를 나타내는 매트릭스와 방문 기록 배열을 만든다. 2. 매트릭스에 노드간 거리를 넣는다. 3. 출발 노드에서 가장 작은 비용으로 갈 수 있는 노드를 구한다. 4. 최소거리 노드로 이동하며 방문 기록을 True로 변경한다. 5. 최소거리 노드까지 이동하는 거리를 더한 참조 배열을 만들고 출발 노드와의 거리와 비교해 더 작은 값을 대입한다. 6. 과정을 반복한다. 아래 예제를 풀어보자. https://www.acmicpc.net/problem.. 2022. 3. 24.
[Algorithm] Powerset 알고리즘 뽀개기 어제 Powerset 알고리즘 공부를 하다 결국 침대에 누워 서럽게 울다 지쳐 잠이 들었다... 나만 이해가 안되는 건가..? 하지만 정신을 차렸으니 다시 한 번 꼼꼼이 파헤처 보도록 하자. 일단은 Poserset에 대한 기본적인 이해부터 해보도록 해보겠다. Powerset = 멱집합 The power set is a set which includes all the subsets including the empty set and the original set itself. 멱집합이란 빈집합부터 원래 요소를 모두 포함한 집합까지의 모든 하위 집합을 말한다. 즉 {1, 2, 3}의 멱집합은 다음과 같다: {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} Power.. 2021. 12. 14.
[Algorithm] D.P Top-Down vs Bottom-up Dynamic Programming에서 최적의 값을 찾기 위해 두 가지의 방법을 사용한다. 바로 Top-Down 방식과 Bottom-Up 방식! 오늘은 이 둘의 차이점에 대해 Deep 하게 파헤쳐 보자. 레츠 기릿! Difference Between Top-Down and Bottom-up Approach 알고리즘은 탑다운과 바텀업 접근법으로 나뉘어 디자인된다. Top-down 접근법에서는 복잡한 모듈이 작은 모듈로 나누어진다. 반면에 Bottom-up 접근법에서는 기초적인 모듈을 점점 합쳐나가는 방식을 이용한다. 알고리즘의 최우선 목표는 데이터 구조 속 데이터를 작동시키는 것이다. 다른 말로 설명하자면, 알고리즘은 데이터 구조속의 데이터 연산을 실행하기 위해 사용된다. 복잡한 알고리즘은 모듈이라고 부르.. 2021. 12. 13.
[Algorithm] Greedy Algorithm 오늘부터 본격적으로 알고리즘 공부를 시작하려 한다. 쫄지마 나 자신...! 우선 그 첫 번째 시작을 Greedy Algorithm에 관한 포스팅으로 시작하려 한다. Greedy Algorithm 이란 무엇인가? 탐욕적 알고리즘(Greedy Algorithm)은 각각의 작은 단계에서 최선의 선택을 내림으로서 전체적으로 최적의 솔루션을 찾아내는 알고리즘 전략을 말한다. 즉 탐욕적 알고리즘은 순간순간마다 결과는 신경 쓰지 않고 최선의 솔루션을 선택하게 된다는 뜻이다. 최선의 아웃풋을 즉각적으로 골라내지만, 전체적인 그림은 고려하지 않기 때문에 '탐욕적'이라고 부른다. 탐욕적 알고리즘은 각가의 단계에서 최적의 해답을 선택하고 끝이 나타날 때까지 다음 단계로 넘어가는 방식으로 동작한다. 각각의 단계에서 선택하는 .. 2021. 12. 13.

티스토리툴바