알고리즘/알고리즘문풀

BOJ - 샘터 18513번 (JAVA)

❓ 문제 - 백준 샘터 18513번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/18513) 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 📝 문제해결법 1. 이 문제는 BFS로 해결했다. 샘터 위치를 큐에 넣고 BFS를 돌려서 가장 가까운 곳의 집을 다 위치시키면 그 때의 거리를 출력하면 된다. visited을 체크하기 위해서 HashSet을 이용했으며 배열로 했을 때 메모리 부분이나 더 오버헤드가 크다. 큐를 돌면서 방문하지 않은 곳에 ..

BOJ - 대기업 승범이네 17831번 (JAVA, Python)

❓ 문제 - 백준 대기업 승범이네 17831번 - JAVA, Python 풀이법 출처 (https://www.acmicpc.net/problem/17831) 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net 📝 문제해결법 1. 이 문제는 DFS + DP == Tree DP로 해결했다. 2차원 리스트를 통해 i인덱스를 멘토로하는 멘티의 값을 리스트에 넣어준다. dp[i][0]은 i번째 사람이 멘티거나 아무것도 아닐 때의 시너지의 합의 최대값이며, dp[i][1]은 i번째 사람이 멘토일..

BOJ - 우수 마을 1949번 (JAVA, Python)

❓ 문제 - 백준 우수 마을 1949번 - JAVA, Python 풀이법 출처 (https://www.acmicpc.net/problem/1949) 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 📝 문제해결법 1. 이 문제는 DFS + DP, Tree DP로 해결했다. [문제의 조건] 1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다. 2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을 모두 '우수 마을'로 선정할 수 없다. 즉 '우수 마을' 끼리..

2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기(JAVA)

❓ 문제 - 2021 KAKAO BLIND RECRUITMENT 카드 짝 맞추기 - JAVA 풀이법 출처 (https://programmers.co.kr/learn/courses/30/lessons/72415?language=java) 📝 문제해결법 1. DFS로 순열로 카드 번호 뽑는 순서를 정한 후 BFS로 이 순서에 맞춰 최단 거리로 이동 처리하면서 이동 거리의 최솟값을 갱신한다. 2. DFS로 순열 구하기 nodes라는 Node의 2차원 배열로 각 인덱스는 카드의 숫자이고 nodes[i][0], nodes[i][1] 은 i번째 숫자의 Node를 나타내며 Node를 통해 카드의 위치 x, y를 구할 수 있다. permu라는 Node 배열로 각 카드의 번호를 뽑는 순서에 맞게 노드의 위치들을 정한다...