Algorithm/Baekjoon (25) 썸네일형 리스트형 [Baekjoon] 백준 21924번: 도시 건설 (JAVA) 문제 21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net [ 문제 풀이 ] 모든 건물을 최소한의 비용으로 연결하는 문제이므로 크루스칼 알고리즘으로 풀면 됩니다. 크루스칼 알고리즘에 대한 자세한 설명은 아래 포스트를 참고해주세요 :) [JAVA] 서로소 집합(Disjoint Sets)과 연산 최근 알고리즘 문제를 풀면서 최소 신장 트리 개념에 대해 공부하다가 알게 된 크루스칼 알고리즘.. [Baekjoon] 백준 14567번: 선수과목 (JAVA) 문제 14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net [ 풀이 과정 ] 대표적인 위상 정렬 문제입니다. 위상정렬 문제는 아래의 내용을 기본으로 해서 풉니다. 1. 방향 그래프를 만든다. (연결 리스트 생성) 2. 각 노드의 진입차수를 배열로 저장한다. 3. 진입차수가 0인 노드를 그래프에서 하나씩 지워가며 queue에 저장한다. 학기는 depth로 생각할 수 있으므로, 큐의 현재 사이즈만큼 돈 후에 하나씩 증가시켜주면 됩니다. 문제에 나와있는 예제 입력 2를 보면 아래와 같습니다. 진입차수가 0인 노드 1, 4, 6을 먼저 q.. [Baekjoon] 백준 11085번: 군사 이동 (JAVA) 문제 11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net [ 풀이 과정 ] 입력으로 받는 c와 v를 연결하는데, 가장 넓은 너비를 가지는 간선으로만 연결하는 문제입니다. 시작과 끝이 각각 c와 v이므로 이 점을 유의하며 크루스칼 알고리즘으로 해결할 수 있습니다. 간선을 나타내는 Edge 클래스를 만들고, Comparable을 이용하여 간선의 너비가 넓은 순(내림차순)으로 정렬할 수 있도록 compareTo()를 오버라이딩 합니다. PriorityQueu.. [Baekjoon] 백준 11123번: 양 한마리... 양 두마리... (JAVA) 문제 11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net [ 풀이 과정 ] 양들의 무리만 카운트하면 되므로 map[][]에 양과 풀을 저장한 후 for()문으로 순회하면서 '#' 가 있는 위치에서 카운트를 하나 증가시키고, bfs()를 돌려주면 상하좌우로 붙어있는 '#' 끼리 최대한 방문하게 됩니다. (행, 열의 최대 크기가 각각 100이므로 시간복잡도는 충분합니다.) !! for()문으로 순회할 때 방문체크까지 해주어야 정점을 중복해서 방문하지 않게 됩니다. [ 코드 ] import.. [Baekjoon] 백준 14248번: 점프 점프 (JAVA) 문제 14248 14248번: 점프 점프 첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출 www.acmicpc.net [ 풀이 과정 ] 입력값을 살펴보면, 돌의 개수를 입력받은 후 각 돌의 위치에서 좌우로 점프할 수 있는 거리, 즉 칸의 개수를 입력받습니다. 따라서 jump[]에 각 위치에서 점프할 수 있는 거리를 입력 받아 저장해주고, BFS를 사용하여 현재 칸에서 점프하여 갈 수 있는 모든 위치를 큐에 넣고 방문표시를 해준 후, 전역변수 cnt를 하나씩 증가해줍니다. [ 코드 ] import java.io.*; import java.. [Baekjoon] 백준 5972번: 택배 배송 (JAVA) 문제 5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net [ 풀이 과정 ] 간선에 비용이 있고, 최소 비용을 구하는 문제이므로 다익스트라로 풀 수 있습니다. Node 클래스를 만들어 정점의 값과 비용을 저장하고, ArrayList 배열을 만들어 Node 인스턴스를 저장하여 시작 정점에서 도착 정점까지의 간선 비용을 저장합니다. 최소 비용을 구하기 위해 우선순위 큐를 사용하여 비용이 작은 값부터 방문할 수 있도록 하고, dist[]에 각 정점까지의 최소 비용을 저장해줍니다. [ 코드 ] import java.io... [Baekjoon] 백준 17070번: 파이프 옮기기 1 (JAVA) 문제 17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [ 풀이 과정 ] (1, 1) 에서 (N, N) 까지 가는 경우의 수를 구하는 것이기 때문에 그래프 탐색 방법인 BFS, DFS가 떠올랐습니다. 흔히 그래프 탐색 문제는 현재 좌표에서 상하좌우 또는 대각선까지 갈 수 있는 좌표를 모두 탐색하는 것이 대부분이지만, 이 문제에서는 현재 좌표에서 갈 수 있는 방향이 오른쪽, 아래쪽, 대각선(오른쪽 아래) 이렇게 총 3가지이고, N의 범위도 3 ~ 16으로 작습니다. BFS로 풀게.. [Baekjoon] 백준 알고리즘(Python) 1620 - 나는야 포켓몬 마스터 이다솜 문제 1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 이 문제를 풀기 위해 알아야 할 개념은 다음과 같습니다. > dictionary 자료형 > sys.stdin.readline() 1. 문제 풀이 1) 잘못된 문제 풀이 (시간 초과) 이 문제는 딕셔너리의 키와 값을 이용해서 푸는 것이 더 효율적입니다. 아래와 같이 리스트로 접근하게 되면 시간 초과가 발생합니다. n, m = map(int, input().split()) list1 = [] res = [] for _ in.. 이전 1 2 3 4 다음 목록 더보기
