춤추는 개발자

문제 출처 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r= www.acmicpc.net 접근 방식 및 풀이 - DFS를 이용하여 시작점과 만나면는 사이클 그래프의 노드 개수를 전체 학생수에서 뺀다. - 참고 h..

문제 출처 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 접근 방식 및 풀이 - BFS 이용 - 아래 블로그 참고함. https://qlyh8.tistory.com/157 백준 2178번: 미로 탐색 문제 출처: https://www.acmicpc.net/problem/2178 참고 BFS(Breadth-First Search): http://qlyh8.tistory.com/30?category=731166 BFS 문제: http://qlyh8.tistory.com/31?c..

문제 출처 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방식 및 풀이 - DFS 이용 - 부모노드에 해당하는 노드값을 출력하기 위해 배열을 추가로 선언한다. 소스 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { static int n ; static Arr..

문제 출처 https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 접근 방식 및 풀이 - 규칙대로 숫자를 구하다가 중복되는 숫자가 나오면 map에 넣어둔 data값 출력 참고 : https://haloworld.tistory.com/122 [문제풀이] 백준 2331 반복수열 import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class 반복수열_2331 { public static void main(String args[]){ Scanner sc = new Scanner..

문제 출처 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net 접근 방식 및 풀이 - 키워드는 간척사업을 통해 다리를 만들수 있는 최소거리, BFS 활용이다. - 너무 어려워서 아래 블..

문제 출처 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 접근 방식 및 풀이 - 1~k 배열의 가장 큰 값의 중간값으로 가장 큰 랜선의 길이를 찾아간다. - 코드는 아래 블로그에서 참고했다. https://ukyonge.tistory.com/25 #백준_1654 랜선 자르기 -..

문제 출처 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 문제 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다. 순열을 배열을 이용해 \(\begin{pmatrix} 1 www.acmicpc.net 접근 방식 및 풀이 - DFS를 이용하여 DFS를 하나씩 완성할때마다 Count를 올려준다. 소스 코드 import jav..

문제 출처 https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있다. www.acmicpc.net 접근 방식 및 풀이 - 아직도 어려운 개념 - 분할 정복, line sweep 알고리즘 사용하면 금방 풀수 있다고한다..(난 아직..;ㅜ) - 참고 https://wellohorld.tistory.com/38 [백준 - 2261번] 가장 가까운 두 점 - Java //Wello Horld// 이번에는 BOJ의 2261번 문제 "가장 가까운 두 점" ..

문제 출처 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net 접근 방식 및 풀이 - BFS, DFS 모두 사용하여 해결할 수 있다. - 아래 블로그 내용을 참고하여 구현하였다. (개인적으로..

문제 출처 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 접근 방식 및 풀이 아직도 감이 안온다.. 이해한 부분까지는 코드에 주석으로 달았다. 참고 사이트 : https://ballpython.tistory.c..