https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 난이도 : 골드5 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 너비 우선 탐색(BFS, Breadth First Search)을 사용하여 풀이하는 문제입니다. 각 경우의 수를 그래프 형태로 생각하며, 가장 먼저 도달하는 해가 최적의 해인 BFS의 특징을 사용하여 풀이할 수 있습니다. BFS의 '가장 먼저 도달하는 경로가 최적의 경로이다'라는 특징을 잘 모르실 경우, 아래 포스팅을 한번 보고 오시..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 분리 집합 설명 0 a b 일때는 a와 b를 합집합하고, 1 a b 일때는 a와 b가 같은 집합에 속하는지 확인하는 문제입니다. 즉, 원소들간에 그룹을 만들고, 그룹을 하나씩 합쳐가며, 1 연산일때 두 원소가 같은 그룹 내에 존재하는지 확인하면 됩니다. 해당 문제는 분리 집합과 Union - Find 알고리즘을 사용..

https://www.acmicpc.net/problem/25205 25205번: 경로당펑크 2077 시은이는 종합설계 프로젝트로 오픈월드 액션 고스톱 게임 경로당펑크 2077을 개발하고 있다. 대사를 추가하던 중, 사용자 이름에 따라 '을' 또는 '를' 중 하나를 출력해야 함을 깨달았다. 예를 들 www.acmicpc.net 난이도 : 브론즈 2 태그 : 구현, 문자열 설명 한글의 경우, 이름의 마지막 글자의 종성이 있다면, 즉 받침이 있다면 '를', 없다면 '을' 을 사용합니다. 닉네임이 영타로 들어올 때, 마지막 글자만 체크해서 자음이면 1, 모음이면 0을 출력하면 됩니다. 소스코드 #include #include int main() { int n; char name[30]; scanf("%d", ..

https://www.acmicpc.net/problem/17358 17358번: 복불복으로 지구 멸망 (2,1,4,3), (3,4,1,2), (4,3,2,1) 총 3가지 경우가 가능하다. www.acmicpc.net 난이도 : 실버5 태그 : 수학, 조합론 설명 컵 하나와 다른 컵 하나를 서로 바꿉니다. 컵의 갯수는 항상 짝수이며, 모든 컵은 단 한 번만 바뀌어야 할 때, 가능한 조합의 경우의 수를 구하는 문제입니다. 예시와 함께 보겠습니다. 6개의 컵이 있다 가정을 해보겠습니다. 6개의 컵중 하나를 선택합니다. 위치를 옮길 다른 컵 하나를 선택합니다. 5개의 컵 중 하나를 선택할 수 있으므로, 현재까지 경우의 수는 5입니다. 다른 컵을 하나 선택합니다. 저는 2번컵을 집었습니다. 남은 3개의 컵중 위..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색, 시뮬레이션 설명 외부 공기와 접촉하는 칸이 두 곳 이상이면 치즈가 녹습니다. 이때, 모든 치즈가 녹으려면 얼마만큼의 시간이 필요한지 구하는 문제입니다. DFS, BFS 중 어느것을 사용해도 무방하나, 저는 DFS를 사용하여 풀이하였기에, 본 포스팅에선 DFS를 사용한 접근법과 풀이를 서..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 난이도 : 골드 4 태그 : 가장 긴 바이토닉 부분 수열 설명 가장 긴 증가한는 부분수열(LIS, Longest Increasing Subsequence), 가장 긴 감소하는 부분수열(LDS, Longest Decreasing Subsequence)과 비슷하게 가장 긴 증가했다가 줄어드는 부분 수열을 찾는 문제입니다. 첫 접근은 다이나믹 프로그래밍 배열 두개를 사용하여, 하나는 쭉 증가하다가, 다른 하나는 어느 순간..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 트리, 재귀 설명 입력으로 pre order(전위 순회)가 주어지고, 이를 트리 형태로 변환하여 post order(후위 순회)하여 방문한 노드 순서대로 출력하는 문제입니다. 소스코드 전체 소스코드 import java.io.BufferedReader import java.io.InputStreamReader val sb = S..

모바일 앱이나 웹을 서비스 할 때, 서비스에 따라 지도에 통계치를 표기할때와 같이 지도의 색을 칠해야 할 때가 있습니다. 처음 시, 도 등 특정 지방자치단체에 색을 칠해야 함을 알았을 때, 어떻게 해야하나... 많은 고민이 있었고 3대 지도 API인 네이버, 카카오, 구글 지도 API에 삽질도 좀 하다가, 스택 오버플로우도 꽤나 많이 기웃거렸던 기억이 납니다. Javascript 관련 예제는 꽤 많은데 안드로이드 관련 예제는 별로 없어서 꽤 애먹었습니다 ㅎㅎ.... 결과적으로 지도에 색을 칠하는 것 자체는 지도 API는 별 필요가 없고 지도 svg 파일 하나와 VectorChildFinder 라이브러리면 됩니다. 지도 SVG 파일 준비 먼저 바탕이 될 지도 svg 파일 하나를 준비합니다. 구글링을 해봤더..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 벨만-포드 설명 1번 도시에서 출발해 나머지 도시로 가는 최단경로를 구하는 문제입니다. 다만, 음의 간선이 존재하므로 다익스트라는 사용하기 어렵습니다. 음의 간선이 있다는 것을 보고, 어떻게 풀어야하나... 하며 최단경로 알고리즘을 찾아보다가, 음의 간선일때의 쓰는 최단경로 알고리즘인 벨만-포드..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 난이도 : 골드 5 태그 : 다이나믹 프로그래밍, 슬라이딩 윈도우 설명 이전 값들을 이용하여, 최대값 및 최소값을 구하는 다이나믹 프로그래밍 문제입니다. 소스코드 전체 소스코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.StringTokenizer import kotlin.math.max import kotlin..