백준 |1167번. 트리의 지름 - BFS 응용 문제

⬛ 백준 1167번. 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 30.
• textsms

백준 | 7576번. 토마토 - BFS 응용

⬛ 백준 7576번. 토마토 | BFS - 출발점이 여러 개인 BFS를 어떤 식으로 처리할지 고민해야 한다. 하나의 큐에 출발점 담아두고 while()문으로 순회하면서 BFS 레벨 탐색을 한다. 이 문제에서 레벨 == 최소일자가 된다. https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 ..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 30.
• textsms

백준 | 18126번. 너구리 구구 - DFS, BFS 풀이

⬛ 백준 18126번. 너구리 구구 - DFS, BFS 풀이 https://www.acmicpc.net/problem/18126 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net [주의] long 타입으로 변수를 선언해야 정답이 맞다. 길 하나의 길이가 10억이고, 방은 최대 5,000개까지 존재하므로 특정 방까지의 이동 거리는 최대 5^12까지이므로 long 타입을 사용해야 한다. 문제 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 ..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 29.
• textsms

백준 | 1865번. 웜홀 - 벨만포드

⬛ 백준 1865번. 웜홀 - 벨만포드 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 25.
• textsms

백준 | 1948번. 임계경로 - 위상정렬 & 다익스트라

⬛ 백준 1948번. 임계경로 - 위상정렬 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 문제 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 25.
• textsms

백준 | 2623번. 음악프로그램 - 위상정렬

⬛ 백준 2623번. 음악프로그램 - 위상정렬 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다. 그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 ..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 24.
• textsms

백준 | 14567번. 선수과목 (Prerequisite) - 위상정렬 + 레벨 탐색

⬛ 백준 14567번. 선수과목 (Prerequisite) - 위상정렬 + 레벨 탐색 https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 문제 올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 ..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 24.
• textsms

백준 | 1766번. 문제집 - 위상정렬 & 우선순위 큐

⬛ 백준 1766번. 문제집 - 위상정렬 & 우선순위 큐 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 ..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 23.
• textsms

백준 | 1516번. 게임 개발 - 위상정렬 & DP

⬛ 백준 1516번. 게임 개발 - 위상정렬 & DP https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다. 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론,..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 23.
• textsms

백준 | 2056번. 작업 - 위상 정렬 & DP

⬛ 백준 2056번. 작업 - 위상 정렬 & DP https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 23.
• textsms

백준 | 1005번. ACM Craft - 위상 정렬 & DP

⬛ 백준 1005번. ACM Craft - 위상 정렬 & DP https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 ..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 23.
• textsms

백준 | 1261번. 알고스팟 - BFS, 다익스트라

⬛ 백준 1261번. 알고스팟 - BFS, 다익스트라 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NM 크기이며, 총 11크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 22.
• textsms

백준 | 2665번. 미로 만들기 - 다익스트라

⬛ 백준 2665번. 미로 만들기 | 다익스트라 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다. 시작방에서 출발하여 ..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 22.
• textsms

백준 | 2468번. 안전 영역 | DFS, BFS

⬛ 백준 2468번. 안전 영역 | DFS, BFS continue 조건에 nx ≥ N, ny≥ N 했을 때 틀렸고, nx > N-1 ny > N-1 했더니 맞았다. https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 18.
• textsms

백준 | 1303번. 전쟁- 전투 | DFS 풀이

⬛ 백준 1303번. 전쟁- 전투 | DFS, BFS문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 이 문제는 가로 크기 N, 세로 크기 M으로 준다. M먼저 입력받고, N을 나중에 입력받아서 map[N][M] 해줘야 한다. 문제 전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 16.
• textsms

백준 | 10026번. 적록색약 - BFS & DFS 풀이

⬛ 백준 10026번. 적록색약 - BFS & DFS 풀이 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또,..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 14.
• textsms

JAVA | Deque - Double-ended-queue (덱/데크) 사용법

⬛ Deque | Double-ended-queue (덱/데크) 데크 : 큐 양쪽 끝에서 삽입/삭제 모두 수행 가능하도록 확장한 자료구조 ⚫ Deque 사용법 1) Deque 생성 Deque dq = new LinkedList(); 2) Deque 값 추가 Deque dq = new LinkedList(); //1) 앞쪽에 데이터 삽입 dq.addFirst(); dq.offerFirst(); dq.push(); //2) 뒤쪽에 데이터 삽입 dq.addLast(); dq.offerLast(); dq.add(); 3) Deque 값 제거 //1) 앞쪽 값 제거 dq.removeFirst(); dq.remove(); dq.poll(); dq.pollFirst(); //2) 뒷쪽 값 제거 dq.removeLas..

• format_list_bulleted 코딩 테스트 [준비]/JAVA | 활용할 문법 정리
• · 2023. 8. 14.
• textsms

백준 15649번. N과 M (1) - 백트래킹 문제

⬛ 백준 15649번. N과 M (1) | 백트래킹 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 11.
• textsms

백준 | 21938번. 영상처리 - DFS & BFS 풀이

⬛ 백준 21938번. 영상처리 - DFS & BFS 풀이 https://www.acmicpc.net/problem/21938 21938번: 영상처리 화면의 세로 $N$, 가로 $M$ 값이 공백으로 구분되어 주어진다. 두 번째 줄부터 $N + 1$줄까지 $i$번째 가로를 구성하고 있는 픽셀의 $R_{i,j}$, $G_{i,j}$, $B_{i,j}$의 값이 공백으로 구분되어 총 $M$개 주어진 www.acmicpc.net 💚나의 풀이 입력만 주의하면 되는 문제이다. N행 M열의 map에 똑같이 이중 for문을 돌면서 하나의 map[i][j]에 3개의 값을 모두 담아 그 평균치를 담으면 된다. 이후 경계값 T보다 크거나 같으면 255 로, 작다면 0으로 세팅을 한 번 더 해주고, DFS 나 BFS로 탐색을 ..

• format_list_bulleted 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
• · 2023. 8. 11.
• textsms