👨🏻‍💻 PS/바킹독

[JAVA] 백준 1507번 【G2.궁금한 민호】

문제 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 풀이 1️⃣ 플로이드 알고리즘을 이용한 풀이 💡 참고한 Idea 먼저 입력으로 주어지는 비용 그래프가 플로이드 알고리즘을 이미 한번 거친 비용 그래프라고 생각해야한다. 그리고나서, 이 그래프를 다시 분해를 해야하는데 어떻게 분해할 수 있을까? 플로이드 알고리즘의 경우 costs[u][v] = Math.min(costs[u][v], costs[u][m] + costs[m][v]);​ 위와 같이 u에서 v로 가는 비용보다, u에서 m으로 간..

[JAVA] 백준 13168번 【G3.내일로 여행】

문제 13168번: 내일로 여행 첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소 www.acmicpc.net 풀이 1️⃣ 플로이드 알고리즘과 해시를 이용한 풀이 💡 떠오른 Idea 먼저, 플로이드 알고리즘을 사용해서 도시와 도시간 어떤 경로를 거치던 최소 비용을 구해야겠다고 생각이 들었다. 다만, 이 문제의 경우 도시가 숫자가 아닌 문자열의 형태로 주어지기 때문에 도시를 고유한 숫자로 변환하여 플로이드 알고리즘을 사용해야겠다는 생각이 들었다. 1. 먼저, 주어지는 도시의 중복이 있을 수 있다고 했으므로 중복을 제거한다. 중복을 제거..

[JAVA] 백준 2637번 【G2.장난감 조립】

문제 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 풀이 1️⃣ 위상정렬을 이용한 풀이 💡 떠오른 Idea 일단 부품의 조립 순서가 있으므로 위상 정렬을 사용해야한다는 것은 파악했다. 근데, 원하는 출력은 최종 장난감을 구성하는 기본 부품의 수를 출력해야했다. 기본 부품은 조합되어 만들어진 부품이 아닌 경우 기본 부품이라고 한다. 따라서, 특정 부품을 조립할때마다 해당 조립 부품을 구성하는 기본 부품의 정보를 저장하고 계속 넘겨주어야겠다고 생각했다. 일단, indegree 값이 0..

[JAVA] 백준 21276번 【G2.계보 복원가 호석】

문제 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 풀이 1️⃣ 위상 정렬과 우선순위 큐를 활용한 풀이 💡 떠오른 Idea 이 문제에서 가장 중요한 포인트는 직계 자손임을 어떻게 파악하는가였다. haeun doha doha minji haeun minji 위와 같이 관계가 주어졌을 때 하은은 도하와 민지의 자손이고 도하는 민지의 자손임을 알 수 있는데 들어오는 간선의 수를 보면 민지 : 0 도하 : 1 하은 : 2 임을 알 수 있다. 위상 정렬에 따라 정렬하면 민지에서 시작해서 민지와 연결된 간선..

[JAVA] 백준 1967번 【G4.트리의 지름】

문제 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 1️⃣ dfs를 이용한 풀이 💡 떠오른 Idea 처음에는 문제에서 친절하게 부모 노드를 명시해서 알려줘서 다른 방향으로 많이 생각했던 것 같다. 근데, 이 문제는 부모 노드를 특정해서 문제를 풀기보다는 모든 노드가 루트 노드가 될 수 있음을 가정해서 푸는 것이 편리하다. 예시에서 나온 그림은 위와 같은데 사실 위 그림은 9 를 최상단 노드라고 생각하고 그리면 위와 같이 그려질 수 있다. 그리고 9 → 5 → 3 → 6 → 12 노드..

[JAVA] 백준 2250번 【G2.트리의 높이와 너비】

문제 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 풀이 1️⃣ 중위순회를 이용한 풀이 💡 떠오른 Idea 중위 순회는 위와 같이 트리의 노드를 순회하는 방식이다. 중위 순회를 사용하면 트리에 존재하는 각 노드의 열 값을 알 수 있다. 각 노드의 깊이를 체크해나가면서 중위 순회를 하고, 각 깊이에 해당하는 열 값의 최솟값과 최댓값을 기록해두면 된다. public class Main { static Node[] tree; static Map info = new HashMap(); static..

[JAVA] 백준 20955번 【G4.민서의 응급 수술】

문제 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 풀이 1️⃣ 트리의 특징과 bfs 를 이용한 풀이 💡 떠오른 Idea 이 문제는, 무작위로 주어지는 노드간의 관계를 트리관계로 풀어가야 하는 문제이다. 먼저, 생각할 수 있는 경우는 다음과 같다. 1. 정상적인 트리 형태를 이루고 있는 집합인 경우 2. 특정 노드 집합이 사이클을 이루고 있는 경우 3. 1번 혹은 2번 같은 집합이 연결되어있지 않고 떨어져 있는경우 그래서 모든 뉴런을 하나의 트리 형태로 연결하기 위한 횟수를 어떻게 구해야할까 고민했는데 먼저..

[JAVA] 백준 22856번 【G4.트리 순회】

문제 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 풀이 1️⃣ 트리 클래스를 정의한 풀이 💡 떠오른 Idea 처음에는 이 문제에서 정의한 유사 중위 순회를 똑같이 구현해야하나 고민했었지만, 그러지 않고 쉽게 해결할 수 있었다. 이 유사 중위 순회의 특징은 트리에서 제일 오른쪽 간선은 한번만 지나가게 된다는 특징이 있다. 따라서, 가장 오른쪽 자식만 지나가게끔 하는 순회를 정의하여 노드의 개수를 구했고 간선의 개수는 노드의 개수 -1 임을 이용하여 편도 간선의 개수를 구할 수 있었다. 그리고 (전체 노드의 ..

[JAVA] 백준 5214번 【G2.환승】

문제 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 1️⃣ bfs와 인접리스트를 이용한 풀이 💡 참고한 Idea 역의 수 N이 최대 100000 이고 하이퍼 튜브와 하이퍼 튜브가 연결하는 역의 개수 K 와 M이 최대 1000 이라서 일반적인 그래프를 푸는 방식으로 노드를 연결하면 시간 복잡도가 말도안되게 커져서 고민을 많이 했다. 계속 메모리 초과를 어떻게 해결해야할지 고민하다가 다른 사람의 아이디어를 참고하였다. 하이퍼 튜브를 일종의 역으로서 생각을 하고 노드로서 추가하는 ..

[JAVA] 백준 1043번 【G4.거짓말】

문제 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 1️⃣ 플로이드 알고리즘을 이용한 풀이 💡 떠오른 Idea 이 문제는 파티별로 바로 체크를 할 수 없는 문제이고, 모든 파티의 정보를 처리한 다음에 개수를 구할 수 있다. 그 이유는 예제 처럼 4 5 1 1 1 1 1 2 1 3 1 4 2 4 1 위와 같이 주어졌을 때, 4번째 파티인 1 4 에서는 4번이 진실을 모를것 같지만 5번째 파티에서 진실을 아는 1번이 4번에게 알려 줄 수 있기 때문이다. 따라서, 순차적으로 판단할 수 없다. 내가 생각한 전략은 지민이..

[JAVA] 백준 2617번 【G4.구슬 찾기】

문제 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 풀이 1️⃣ bfs와 Marble 클래스 정의를 통한 풀이 💡 떠오른 Idea 문제를 해결하기 위한 방법은 문제에 거의 주어지다 싶이 나와있었다. 구슬이 총 5개일때는 특정 구슬보다 가벼운게 3개 이상인 경우 중간이 될 수 없고 무거운게 3개 이상인 경우는 중간이 될 수 없다. 처음에는 N이 짝수로도 주어지나 싶어서, 짝수인 경우에는 약간 기준이 달랐지만 홀수로만 주어진다고 했으므로 특정 구슬이, 상대적으로 가벼운 구슬이 (N+1)/2 개..

[JAVA] 백준 1707번 【G4.이분 그래프】

문제 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 1️⃣ 이분 그래프의 정의와 bfs 를 이용한 풀이 예전에 풀어봤던 문제여서, 원리를 쉽게 파악할 수 있었다. 이전에도, 한참을 고민했었다가 서칭해서 풀었었는데, 이분 그래프라는 단어가 나오면 이 정의를 생각해야한다. 이분 그래프인지 아닌지 확인할 수 있는 특징 중 하나인, 노드 그래프를 2개의 색깔로 칠했을 때, 인접하는 노드끼리 색이 겹치지 않게 색칠할 수 있을 때, 이분 그래프가 될 수 있다고 한다. 위와 같은 그림처럼 말이다. 아직 방문하지 않..

[JAVA] 백준 2660번 【G5.회장뽑기】

문제 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 1️⃣ 플로이드 알고리즘 사용 💡 떠오른 Idea 처음에 문제가 '어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.' 라고 나와있어서 이해하기가 힘들었었다. 근데, 이 문제를 직관적으로 이해해보니 '특정 회원이 있을 때 가장 사이가 ..

[JAVA] 백준 1781번 【G2.컵라면】

문제 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 풀이 1️⃣ 우선 순위 큐와 그리디를 이용한 풀이 💡 떠오른 Idea 컵라면을 데드라인이 짧고 컵라면을 많이 주는 문제부터 결정해서 큐에 집어넣는다. 즉, 큐의 크기 = 풀기로 결정한 문제 수 = 내가 문제를 푸는데 사용한 시간이 된다. 그리고, 이후에 나오는 문제들이 내 큐의 크기보다 크거나 같으면서 내 큐에 들어있는 컵라면보다 많이 준다면 내 큐에 들어있던 가장 컵라면을 적게 주는 문제를 제거하고, 추가해준다. 예제로 원리를 설명해보면, 먼저, 데드라인이 짧은 ..

[JAVA] 백준 1655번 【G2.가운데를 말해요】

문제 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 1️⃣ 우선 순위 큐 두개를 활용한 풀이 💡 떠오른 Idea 우선 순위 큐는 이진 힙 방식으로 구성되어 있기 때문에, 사용하면 정렬을 유지한 삽입 과정을 O(logN) 에 수행할 수 있다. 그리고, 우선 순위 큐에 따라 정렬된 데이터를 꺼낼 때 역시, O(logN) 로 수행할 수 있다. 따라서 우선 순위 큐를 사용하는게 시간 복잡도를 만족시킬 수 있다고 판단하였다. 가운데 수를 항상 말해야 하므로, 내림차순으로 정렬된 우선순위 큐 (l..