알고리즘 2

코딩테스트 공부를 막 준비, 시작하시는 분 들에게..

*매우 주관적인 견해임을 밝힙니다. 정답은 없으니까... 안녕하세요. F-lab에서 오프라인으로 코딩테스트 스터디를 진행하면서 다른 분들보다 조금이라도 문제를 많이 푼 경험이 있어, 삽질을 한 경험을 공유드려 이제 막 코테, 언어, 자료구조 공부를 시작하시는 분들에게 조금이나마 저와 같은 실수를 하지 않기를 바라는 마음에 글을 작성하게 되었습니다. 백준과 프로그래머스 문제를 합쳐 700문제 가까이 풀었습니다. 정말 많이 푼 것 같지만 저는 작년에 카카오 공채, 소마 2 차코테, 이베이 등등 수많은 코테에 떨어진 경험이 있습니다. Q) 왜 떨어졌을까요? A) 문제만 많이 풀면 될 줄 알았고, 알고리즘의 원리나 자료구조에 대해 정확히 파악을 하지 못하고 무작정 생각과 동시에 코드를 작성하려고 했습니다. 그러..

끄적끄적 2023.02.10

다익스트라 알고리즘(Dijkstra Algorithm) - JAVA

다익스트라 알고리즘 이란? 그래프에서 여러 개의 노드가 있을 때, 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘입니다. 다익스트라 최단 경로 알고리즘은 '음의 간선' 즉, 가중치가 0보다 작은 값이 아닌 경우에 때 정상 동작합니다. 현실 세계에서의 길(간선) 음의 간선으로 표현되지 않아 다익스트라 알고리즘은 실제로 인공위성 GPS 소프트웨어 등에서 가장 많이 사용됩니다. 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류됩니다. 왜냐하면 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복합니다. 동작과정 출발 노드를 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중에서 최단 거리(가중치)가 가장 짧은 노드 선택 해당 노드를 거쳐 ..

알고리즘 정리 2022.03.23