갑갑이의 개발세상

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128MB 34902 17536 12585 49.322% 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 ..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256MB 49704 12781 7530 23.198% 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을..

그래프에 정보를 저장했으면, 정보를 사용하기 위해서는 그래프에 어떤 정보가 어떻게 저장되어 있는지 파악해야 할 것이다. 그래프를 탐색하면 그래프를 탐색하는 과정에서 간선이 어떠한 방식으로 연결되어있는지, 탐색 순서는 어떻게 되었는지 등을 통해서 그래프의 전체적인 구조를 파악할 수 있다. 즉, 그래프 탐색의 목적은 임의의 정점에서 시작하여 연결되어있는 모든 정점을 한 번씩 방문하면서 그래프의 구조를 파악하는 것에 있다. 그렇다면 그래프는 어떠한 방법으로 탐색할 수 있을까? 그래프를 탐색하는 방법은 대표적으로 DFS와 BFS의 두 가지가 있다. 1. 깊이 우선 탐색(Depth-First Search, DFS) DFS는 임의의 정점에서 시작하여 방문할 수 있는 정점 중 하나를 방문하고, 방문한 정점에서 방문할..

그래프(Graph)란? 그래프란 사물이나 개념 간의 연결 관계를 표현해주는 자료구조의 일종이다. 예를 들면 SNS에서 친구와 친구 사이의 관계라던지 도로의 교통망, 웹사이트 간의 링크 등과 같이 어떤 요소와 요소간의 관계를 나타낼 때 주로 사용할 수 있다. 그래프는 어디에 활용할 수 있을까? 철도, 도로 등 교통망 분석: 어떤 교통망을 이용해야 최소 비용/최단 거리/최소 시간 내에 이동할 수 있는가? SNS 분석: 친구 관계 분석 및 친밀도 분석 인터넷 망 분석: 어떤 라우터로 가야 최대한 빨리, 최소 비용, 최소 전송 용량으로 전송할 수 있는가? 한 붓 그리기: 그래프 탐색을 통해 단순 사이클을 생각해보면 한 붓 그리기 문제를 해결할 수 있다. 이 외에도 현실세계의 다양한 모델에 그래프 이론을 활용하면..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 512MB 14174 4274 2859 29.147% 문제 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 입력 ..

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128MB 5013 2219 1796 43.816% 문제 한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다. 각 집중..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256MB 56974 18078 11061 29.235% 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지..

HashMap은 Map의 인터페이스를 구현한 대표적인 Map 컬렉션의 일종으로, 당연히 Map을 상속받았기 때문에 키(Key)와 값(Value)로 구성된다는 Map의 구조를 그대로 따르고있다. HashMap 선언 아래 예시와 같은 경우 key값의 형식으로 String을, value값의 형식으로는 Integer값을 사용함을 의미한다. // HashMap hm1 = new HashMap(); HashMap hm2 = new HashMap(hm1);// hm1과 동일한 값을 가진 HashMap 생성 HashMap hm3 = new HashMap(10);// 초기 용량(capacity) 지정 HashMap hm4 = new HashMap(){{ put("apple", 1); }};..

https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256MB 6097 2345 1619 37.660% 문제 생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다. 입력 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 ..

https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256MB 10512 3115 2271 28.387% 문제 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 ..