본문 바로가기

자료구조+알고리즘

[백준-Gold4] 11404 플로이드 - javascript https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net [풀이] 노드 --------간선-------> 노드 (도시) 버스 (도시) 예제) 도시 5개 버스 14개 시작점 끝점 비용 1 2 2 ... * 플로이드 알고리즘 설명 참고 : https://eonhwa-theme.tistory.com/178 [코딩테스트 알고리즘] 플로이드-워셜 - javascript ﹅ 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 모든 노드에서 다른.. 더보기
[알고리즘] 플로이드-워셜 - javascript ﹅ 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 모든 노드에서 다른 모든 노드까지 가는 최소비용 start → mid → end 표[2차원 배열]를 만들어 중간 경유지에 따라 값을 계속 갱신시킨다. 시간복잡도 : O(V^3) 다익스트라 : 한 노드 → 다른 모든 노드, O(ElgV) 플로이드 워셜 알고리즘은 다익스트라 알고리즘과는 달리 "모든 노드 쌍" 에 대해 최단거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이다. 💡 그래프 알고리즘에 대해 읽어볼 좋은 글 https://yozm.wishket.com/magazine/detail/2411/ ﹆ 작동 원리 1 → 4 로 바로 가는 방법은 존재하지 않지만, 중간 노드 mid 를 3으로 둔다면, 1 → .. 더보기
[프로그래머스 level03] 순위 - javascript https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 문제의 예제를 보면 [4,3]은 4가 이긴거고 [3, 2]는 3이 이긴거다. 4 -> 3 -> 2 이므로 4는 2를 역시 이기게 된 게 된다. 해당 풀이를 모든 노드에서 모든 노드까지 최소비용을 구하는 "플로이드" 알고리즘을 써서 풀어보는게 나을꺼 같다. (이전의 글 참고: https://eonhwa-theme.tistory.com/178) ﹅ 문제 해결 방식 이차원 배열에 각 선수들의 .. 더보기
[프로그래머스-level2] 조이스틱 - javascript https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] AAA -> JAZ 로 만들기 위해서는 "▲ 커서" 9번 조작 : A→"J" "◀ 커서" 1번 조작 : 맨 뒤의 문자로 커서 이동 "▼ 커서" 1번 조작 : A→"Z" 총 11번 이동으로 만들 수 있다. 💡 고려 사항 1️⃣ 상하 이동 ▲ or ▼ 알파벳의 아스키 코드를 이용해서 13번째 값인 N 을 기준으로 짧은 이동 구한다 for(let i = 0; i < name.length; i+.. 더보기
DP : Dynamic Programming (동적 계획법) #️⃣ DP : Dynamic Programming 이전의 값을 재활용하는 알고리즘 이전의 값을 활용해서 시간복잡도를 줄일 수 있다. 예시) - 1~10 숫자 중 각각 이전값들을 합한 값 구하기 문제 dp 에서는 점화식 을 구하는게 핵심이다 ! 이전값을 어떻게 활용하는지를 구하는 알고리즘 이기 때문에 예를들어 점화식 : An = An-₁ + An-₂ 더보기
[프로그래머스-level2] 게임 맵 최단거리 - javascript https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 최단거리를 구하는 거니 BFS 알고리즘을 사용해야 한다. 알고리즘 이해만 있다면 수월하게 풀 수 있는 난이도 문제. function solution(maps) { let answer = 1; let visited = maps //탐색을 마친 노드들 let needVisit = []; //탐색해야할 노드들 const n = maps.length; //세로 const m = maps[0].le.. 더보기
[javascript] BFS 📶 그래프 탐색 어떤것들이 연속해서 이어질 때, 모두 확인하는 방법 이다. Graph : Vertex (정점) + Edge (이어지는 것) - 시작점에 연결된 Vertex 찾기 - 찾은 Vertex 를 Queue 에 저장 - Queue 의 가장 먼저 것 뽑아서 반복 ⏱️ 시간복잡도 알고리즘이 얼마나 오래 걸리는지 / 문제를 해결하는데 걸리는 시간과 입력의 함수 관계 나타낸다. BFS : O(V+E) BFS 의 기본원리 - 방문여부 확인 (재방문 금지) - Queue: BFS 실행 최단거리는 BFS(너비우선탐색) 로 푸는게 좋다. 탐색 스택, 방문 배열 생성 탐색을 시작하는 정점을 탐색스택에 쌓는다 탐색스택이 없어질때까지 아래 반복 - 스택 최상단에 있는 것을 없애고, 이를 탐색 - 탐색 시에 방문했는지 .. 더보기
[프로그래머스-level2] 기능개발 (javascript) https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] - 각 기능은 진도가 100% 일 때 배포 가능 - 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발되더라도 앞에 있는 기능이 배포될 때 함께 배포 ---> Queue 활용 Math.ceil() Math.ceil() - JavaScript | MDN The Math.ceil() static method always rounds up and returns the smallest integer.. 더보기
[프로그래머스_lv2] 타겟 넘버 (javascript) https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [유형] - 깊이/너비 우선 탐색 (DFS/BFS) [풀이] 💡 노드그래프 시각화할 수 있는 사이트: https://csacademy.com/app/graph_editor/ dfs 풀이 const numbers = [4, 1, 2, 1]; //[1, 1, 1, 1, 1]; const target = 4; //3; function solution(numbers, .. 더보기
[백준18870-silver2] 좌표 압축 (javascript) https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net [풀이] 📌 좌표압축 ? 만약 x축의 좌표가 [0 ,1 ,2 ,3 ,100 ,150]과 같이 주어졌을 때, 0~3은 각 1씩 차이라 크게 문제 되지 않지만 100과 150을 탐색하기 위해서는 100까지, 150까지 탐색해야하는 문제점이 있다. 다시말해 4~99, 101~149는 쓰지 않는데 탐색하고 있는 시간낭비를 하고 있는 것이다. 숫자의 갭차.. 더보기
반응형

티스토리툴바