반응형 Programming/Algorithm29 백준 1504 자바 특정한 최단경로 알고리즘 백준 1504 문제는 다익스트라 알고리즘을 이용해서 최단 경로를 찾는 문제다. 하지만 기본적인 다익스트라와 차이점은 양방향 그래프라는 점과 반드시 지나야 하는 정점이 주어진다는 것이다. 문제의 입력 예제에서는 정점 2와 정점 3을 반드시 지나는 조건을 충족하는 다익스트라 알고리즘을 요구하고 있다. 만약 다익스트라 알고리즘이 처음이라면 반드시 아래 글을 먼저 참고해서 이해하고 오길 바란다. 백준 1753 자바 최단거리 다익스트라 알고리즘 시간복잡도 JAVA 백준 1753 최단거리 문제는 다익스트라 알고리즘을 사용해서 풀어보는 문제다. 우선순위 큐를 사용해야 하고, 인접한 그래프의 방향성이 존재하는 그래프의 정보가 입력값으로 주어진다. 최단거 incomeplus.tistory.com 문제 시각화 입력 예제를.. 2022. 4. 5. 백준 1753 자바 최단거리 다익스트라 알고리즘 시간복잡도 JAVA 백준 1753 최단거리 문제는 다익스트라 알고리즘을 사용해서 풀어보는 문제다. 우선순위 큐를 사용해야 하고, 인접한 그래프의 방향성이 존재하는 그래프의 정보가 입력값으로 주어진다. 최단거리를 구하는 방법으로 우선순위 큐를 사용해서 문제를 풀어본다. 다익스트라 알고리즘이란? 양수의 그래프 한 정점에서 주변 정점까지 도달하는 최단거리를 구하는 알고리즘이다. 초기 모델은 우선순위 큐를 사용하지 않아 O(V^2)였다. 이 후 최소 우선 큐가 도입되면서 피보나치 힙으로 수행되는 시간복잡도는 O(|E| + |V|log|V|)가 된다. 다익스트라 알고리즘은 음이 아닌 가중치를 가지는 무작위유향 그래프에서 단일 소스 최단 경로 알고리즘 중에서 가장 빠른 알고리즘으로 알려져 있다. 다익스트라 알고리즘 모든 정점을 미방문.. 2022. 3. 24. 백준 1707 자바 이분 그래프 판별 알고리즘 백준 1707 이분 그래프 판별 알고리즘 백준 1707 이분 그래프 판별 문제를 풀기 위해서는 먼저 '이분 그래프'에 대해서 이해해야 한다. 그래프 자료구조는 비선형 자료구조에 속한다. 즉 자료들이 순차적으로 배열되있지 않고, 정점과 간선으로 이루어진 '비선형' 형태의 자료구조를 의미한다. 그래프는 단방향 그래프와 무방향 그래프로 구분된다. 이분 그래프란, 모든 정점을 빨강과 파랑으로 색칠하면서 모든 변이 빨강과 파랑 정점을 포함하도록 칠할 수 있어야 한다. 즉, 한 개의 정점에서 출발해서 이웃 정점들을 방문하면서 현재 정점의 색과 반대의 색을 칠해가면서 모든 정점을 순회할 수 있으면, 이분 그래프라고 판별할 수 있게 된다. DFS / BFS 알고리즘 더 알아보기 백준 7562 나이트의 이동 자바 알고리.. 2022. 3. 23. 백준 7562 나이트의 이동 자바 알고리즘 java 풀이 백준 7562 나이트의 이동 알고리즘 해당 문제는 최단거리를 묻는 문제다. 출발 지점의 좌표에서 시작해서 도착 지점까지의 최단거리를 구하기 위해서는 DFS보다는 BFS 알고리즘을 사용해서 문제의 해법을 찾아야 한다. 즉 1칸씩 이동할 때 마다 counter를 증가시키면서 도착지점까지의 최단거리를 구하는 문제다. BFS 알고리즘에서는 Queue 자료구조를 사용한다. while문을 돌면서 queue 내의 더 이상의 데이터가 없을 때 까지 무한 반복이 진행되며, 만약 새로운 지점을 찾게 되면 queue에 지점의 좌표값을 입력하면서 BFS 알고리즘 탐색을 이어 나간다. 혹시나 BFS, DFS 알고리즘이 처음이라면 아래 글들을 다 읽고 문제를 푸는 것을 추천한다. BFS, DFS 알고리즘 백준 1697 숨바꼭질 .. 2022. 3. 22. 백준 1697 숨바꼭질 문제 자바 JAVA BFS 알고리즘 풀이 백준 1697 숨바꼭질 문제는 BFS 알고리즘을 사용해서 풀어보는 문제다. 술래의 위치에서 동생이 숨어있는 위치까지 이동하기 위한 횟수를 계산하게 된다. 술래는 좌,우,*2 순간이동을 할 수 있다고 가정한다. 동생의 위치까지 도착하기 위한 최단시간은 얼마인지를 구하기 위해서는 이동한 모든 노드에 대해서 COUNT를 해야 한다. BFS 알고리즘 이해하기 백준 7569 토마토 3D 알고리즘 문제 자바 JAVA 풀이 해설 리뷰 백준 7569 토마토 문제는 기존 토마토 문제와 동일하지만 3D로 만들어진 토마토 틀에서 토마토가 익는 날짜를 구하는 문제다. BFS 알고리즘을 사용하지만 좌표값이 2D에서 3D로 늘어났을 뿐이다. BFS incomeplus.tistory.com 백준 7576 토마토 알고리즘 문제 자바.. 2022. 3. 12. 백준 7569 토마토 3D 알고리즘 문제 자바 JAVA 풀이 해설 리뷰 백준 7569 토마토 문제는 기존 토마토 문제와 동일하지만 3D로 만들어진 토마토 틀에서 토마토가 익는 날짜를 구하는 문제다. BFS 알고리즘을 사용하지만 좌표값이 2D에서 3D로 늘어났을 뿐이다. BFS 알고리즘을 까먹었거나 익숙하지 않다면 아래 글을 꼭 참고 하고 오길 바란다. BFS 알고리즘 백준 7576 토마토 알고리즘 문제 자바 JAVA CODE 백준 7576 토마토 문제는 토마토가 들어있는 1의 칸에서 시작해서 전체 토마토가 익어가는 기간을 구하는 문제다. 복잡해보이지만 결국 BFS 알고리즘으로 해결할 수 있는 문제다. 첫번째 노드에서 incomeplus.tistory.com 백준 1012 유기농 배추 알고리즘 자바 JAVA 백준 1012 유기농 배추 알고리즘 자바 JAVA 문제 백준 1012.. 2022. 3. 11. 이전 1 2 3 4 5 다음 반응형
