1. 가중치가 없을 때 → BFS모든 간선의 비용이 같을 때 (예: 한 칸 이동 = 1)BFS는 가까운 노드부터 차례대로 탐색하기 때문에 처음 도착한 거리가 최단거리이다.한 칸당 이동하는 데 드는 비용이 같고,int[][] map 환경에서 A에서 B까지 가는 데에 걸리는 최단 거리를 구하는 문제가 나오면다음과 같이 풀면 된다.import java.util.*;class Solution { static int[] dx = {1, -1, 0, 0}; static int[] dy = {0, 0, 1, -1}; public int bfs(int[][] map) { int n = map.length; int m = map[0].length; bo..
Algorithms
반응형
문자열을 반복해서 다뤄야 할때, String 대신 StringBuilder를 사용하면 시간을 단축할 수 있다.String은 불변 객체이기 때문에, 반복적인 문자열 결합시 불필요한 객체 생성 → 시간 초과를 이어진다.코테에서 피해야 할 실수String s = "";s += "a" // 시간초과 위험 높음 메서드 정리1️⃣ append() : 문자열 추가StringBuilder sb = new StringBuilder();sb.append("hello");sb.append(" ");sb.append("world"); 2️⃣ toString() : 최종 문자열로 변환String result = sb.toString(); 3️⃣ 길이 확인int len = sb.length(); 4️⃣ charAt() / set..
알고리즘 문제를 풀다가 막힌 부분이 있어 정리하려고 한다!1. 정수를 리스트에 담기118372라는 정수를 배열에 한자리씩 담으려고 한다.이때 list()와 map()를 사용한다.중요한 것은 str() 문자열로 변경한 뒤에 map으로 감싸줘야한다!이유는 map함수가 반복 가능한(iterable) 객체를 두 번째 인자에 필요로 하는데, n은 정수이기 때문에 str문자열로 변경해줘야한다. list(map(int, str(n))n = 118372n_list = list(map(int, str(n)) # [1, 1, 8, 3, 7, 2] 2. 정수가 담긴 리스트를 하나의 정수로 표현하기정수가 담긴 리스트 [1, 1, 8, 3, 7, 2]를 118372로 표현하는 방법처음에는 하나씩 빼서 str()로 바꿔서 합치..
위상정렬 (Topopogical sort)위상 정렬은 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것이다.방향 그래프에서 간선 가 있다면, 정점 u는 정점 v를 선행하여 정렬한다.방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열해야한다.활용 예로는 선수 과목은 과목들의 선행 관계를 표현한다.🌟 구현정점에 들어오는 간선수를 저장하는 진입차수(in_degree)를 사용한다.동작방식모든 정점의 in_degree 설정순서에 맞도록 리스트 설정 예) graph[2] = [1,3] : 정점 2는 정점 1과 정점 3보다 선행함.in_degree가 0인 정점은 큐에 추가큐가 빌 때까지 반복3.1 큐의 앞 요소를 popleft()로 가져와 그에 맞는 리스트를 꺼냄3.2 리스트에서 나온 정점의 i..
유튜브로 "이것이 코딩이다" DFS&BFS 문제를 풀어보다 "미로 탈출" 문제에서 오류가 발생했다.👾 문제 📍 풀이입력3 31100100115 6101010111111000001111111111111인접한 노드에 자신의 노드 값을 +1 함 ⚒️ 코드from collections import dequen, m = map(int, input().split())graph = [] * n # 잘못된 부분 ㅠfor _ in range(n): graph.append(list(map(int, input().split())))result = 0dx = [1, -1, 0, 0]dy = [0, 0, 1, -1]def bfs(x, y): myqueue = deque() myqueue.append((x, ..
다익스트라 알고리즘에 대해 [이전글]에서 어떻게 풀어야하는지 정리해뒀다.요약하자면![이전글] 에서는 인접 노드의 distance > 현재 노드의 distance + 인접 노드까지의 distance 를 비교해야 했다.이를 위해서 우선순위 큐(PriorityQueue)와, 노드 방문 여부, disatnce를 고려해야 한다.하지만 이번 문제에선 heapq를 사용한다.파이썬 내장 heapq도 [이전글]에서 정리했다.👾 K번째 최단 경로 찾기 - 백준 1854번https://www.acmicpc.net/problem/1854예제 입력15 10 21 2 21 3 71 4 51 5 62 4 22 3 43 4 63 5 85 2 45 4 1예제 출력1-1107514 📍 풀이이전과는 다르게 k번째 거리를 구해야한다. ..
