알고리즘
-
그래프 자료구조 구현알고리즘 2021. 9. 25. 15:32
위와 같이 vertex(정점)과 edge(정점간의 연결하는 선)으로 구성되어 있는 자료구조를 그래프라고 부릅니다. 그래프 자료구조는 방향성 유무, 무게 유무, 그래프 모양 등에 따라 달라지기 때문에 여러 종류가 있습니다. 또한 다양한 모습의 그래프 자료구조 덕분에 최단거리를 통해 목적을 도달하기 위한 알고리즘, 최소한의 가중치로 목적에 이동하는 알고리즘 등 필요한 목적에 따라 구현한 알고리즘들도 많습니다. 이번 글을 통해 그래프의 기본용어, 자바스크립트를 통한 그래프 구현을 정리해보았습니다. 그래프 기본용어 vertex (정점) : 위 그림의 a, b, c 등의 노드를 부름 edge (간선): 노드 a와 노드 b를 연결하는 선을 부름 degree of vertex (차수): 노드의 간선 개수. 노드 a의..
-
방문길이알고리즘 2021. 9. 23. 10:57
내 풀이법 문제해석 게임 캐릭터의 이동거리를 구하라! 제한사항 위 그림의 좌표면을 넘어설 수가 없음! (최대 5 최소 -5) 처음 걸어본 거리만 이동거리로 해당됨! 내가 생각한 풀이법 각 이동(up, down, left, right)마다 값을 변경하는 함수를 작성한다 [제한사항1] 이동한 루트가 중복 안됨 set객체를 사용해야겠다고 생각함 [0, 0] 좌표에서 [0, 1] 좌표로 이동을 "0001"로 string으로 값을 주고 이를 set 객체에 넣음 [0, 0] 좌표에서 [0, 1] 좌표로 이동 ("0001")과 [0, 1] 좌표에서 [0, 0] 좌표로 이동함 ("0100")은 루트 상 똑같기에 두 값 모두 set 객체에 넣어야함. (그러므로 마지막에 set.size()를 2로 나누어야함) [제한사항2..
-
땅따먹기알고리즘 2021. 9. 14. 23:27
내 풀이법 문제해석 한 행마다 4개의 열이 주어지며 그 중 숫자 하나를 골라야 한다 단 각 행마다 선택하는 열은 일치해서는 안된다. 예를들어 첫번째 행에 첫번째 열을 골랐다면, 두번째 행에 첫번째 열을 골라서는 안된다. 선택한 숫자를 모두 더할 때의 최대값을 리턴하시오 내가 생각한 풀이법 [1, 2, 3, 4], [1, 2, 3, 8]이 있다면 첫번째 행과 두번째 행의 가장 큰 값의 열이 일치하여 둘 중 하나를 선택해야한다. 이럴 경우 두번째로 큰 값과 제일 큰 값과의 차를 통해 구분할 수 있다. 한계점 위 방법알 적용하기 위해서는 모든 행들을 스캔하여 근접하는 행들 중 가장 큰 값들의 열이 중복되는 경우를 따로 저장해야한다. 만약에 3개의 행의 가장 큰 값의 열이 모두 일치해야한다면 계산 방법이 너무 ..
-
다리를 지나는 트럭알고리즘 2021. 9. 13. 19:55
내 풀이법 문제해석 트럭들이 다리를 지나가는데 걸리는 시간을 구하라 트럭들은 1초마다 다리의 길이의 1씩 지나간다 다리에는 무게제한이 있다 (weight) 내가 생각한 풀이법 특별한 이벤트 발생할 때와 지속적으로 발생하는 이벤트를 나눠서 코드를 작성함 특별한 이벤트의 경우 새로운 트럭이 다리에 진입할 때 다리위의 트럭이 다리의 끝에 도달할 때 지속적 이벤트의 경우 한 턴마다 시간이 1씩 증가함 트럭이 1초마다 다리를 1씩 지나감 나의 코드 const solution = (bridgeLength, weight, truckWeigths) => { let time = 0; let passingWeight = 0; let passingTrucksWeigth = []; let passingTrucks = []; ..
-
스킬트리알고리즘 2021. 9. 11. 14:26
내 풀이법 문제해석 skill 인자는 스킬을 찍는 순서를 나타냄 skill_trees 인자의 각 배열값들이 스킬 찍는 순서에 맞게 찍었는지 확인 skill_trees 배열 중 몇개가 순서에 맞게 찍었는지 확인 내가 생각한 풀이법 스킬트리 각 배열의 값에 skill 값 이외를 우선 지운다 스킬트리 각 배열 값들의 인덱스 값과 스킬의 인덱스 값들을 비교하며 조건에 부합한지 확인한다 스킬은 중복되지 않고 고유하기 때문에 가능 나의 코드 const solution = (skill, skill_trees) => { let answer = 0; let trans = []; for (let i = 0; i < skill_trees.length; i++) { // 1. 스킬트리 각 배열값을 string에서 array로..
-
영어 끝말잇기알고리즘 2021. 9. 9. 21:57
내 풀이법 문제해석 n 명이서 끝말잇기를 한다 낱말을 못 잇거나 기존에 사용한 낱말을 쓰면 탈락자가 발생한다 [누가(n명 중에 몇번째 사람이), 몇번째 라운드]에서 탈락을 했는지 리턴 만약에 탈락자가 없을 시 [0, 0] 리턴 내가 생각한 풀이법 반복문을 돌며 탈락자 발생 (1. 마지막 글자를 못 잇거나 혹은 2. 단어 중복 사용) 시 반복문 중단 반복문에 사용한 i 값을 통해 [누가, 언제] 탈락했는지 값을 구함 나의코드 const solution = (n, words) => { let usedWords = []; let i; for (i = 1; i < words.length; i++) { let previousWord = words[i - 1]; let presentWord = words[i]; u..
-
구명보트알고리즘 2021. 9. 8. 22:00
내 풀이법 문제해석 구명보트에는 2명이하 탈 수 있으며, 2명의 몸무게가 limit을 넘어서는 안된다 2명이 탈 수 없다면 1명을 태워야한다 최소한의 구명보트 사용 개수를 구하라 내가 생각한 풀이법 몸무게가 가장 무거운 사람별로 나열한다 선택한 사람과 더하면 limit 이하지만 최대에 가까운 사람과 같이 탈 수 있도록 한다 구명보트에 탄 인원은 배열에서 지운다 나의 코드 function solution(people, limit) { let answer = 0; people.sort((a, b) => b - a); while (people.length > 0) { let partnerCandidate = []; for (let j = 1; j < people.length; j++) { if (people[..
-
기능개발알고리즘 2021. 9. 1. 20:57
내 풀이법 문제해석 progresses 배열 내에는 개발의 진도를 엘리먼트로 갖고 있는 일의 양을 확인할 수 있다. speeds의 배열 내 각 index의 엘리먼트에 따라 하루 개발 진도량이 추가된다! 일의 진도가 100에 도달하면 개발은 끝나 배포된다! 즉 배열내에서 삭제됨! 가장 앞의 일이 먼저 끝나야 그 후의 일도 같이 배포 가능하다. ex) [95, 100, 100, 100] 의 상태여도 95가 100에 도달해야 나머지도 전부 배포가능하다 리턴 값은 한번 배포할 때 몇개의 개발 수가 배포되는지 배열로 나타내면 된다. 내가 생각한 풀이법 map 함수를 사용하여 하루에 progressess 배열의 개발진도량을 항상 체크한다 progresses의 첫번째 배열이 100이상이면 개발진도량 전부 확인하여 완..