https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 스택, 문자열 설명 문제의 지문에 문자열의 길이는 1~1,000,000 로 명시되어 있습니다. 가장 쉽게 풀 수 있는 방법은 replaceAll 메소드를 사용하는 것 이겠지만, 문자열의 길이를 보니 시간초과, 메모리 초과 등이 날 것이 당연하네요. 따라서, 저는 Stack 자료구조를 사용하여 해당 문제를 풀이하였습니다. 스택에 하나씩 문자열을 ..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 탐색, 그래프 이론, 다이나믹 프로그래밍 설명 DFS를 사용하여, 직전 파이프의 형태 (가로, 세로, 대각선)을 참고하여 풀이할 수 있는 문제입니다. 처음엔 DFS 없이 DP만을 사용하여 풀이하려고 했으나, 생각보다 잘 되지 않아서, 마침내 그래프 탐색 문제인걸 깨닫고 푼 문제였습니다. 소스코드 전체 소스코드 import java.io...

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 데이크스트라, 플로이드-워셜 설명 각 정점에서 m 만큼의 비용 안에 갈 수 있는 정점들의 아이템 값의 최대값을 구하는 문제입니다. 한 정점과 연결된 다른 정점을 순차적으로 탐색하는 방식으로 DFS, 다익스트라 알고리즘을 사용해 풀이할 수도 있지만, 본 포스팅에서는 플로이드 - 워셜 알고리즘을 사용하여 풀이하겠습니다. 소스코드 인풋값 세팅 val MAX_VALU..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색 설명 이전에 많이 해보았던 상하좌우 4방향으로 이동하는 BFS 문제에, 체스의 나이트 방향으로 움직일 수 있는 조건이 더해진 문제입니다. 단, 나이트 이동의 경우 k번이라는 제약조건이 있으므로, 말 이동을 k번 이하로 사용하면서 최단 경로로 목표지점에 도달하는게 핵심입니다. 소스코드 Data Class - P..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 난이도 : 골드4 태그 : 자료구조, 그래프 이론, 그래프 탐색, 분리 집합 설명 파티에 진실을 아는 사람이 포함되어 있으면, 그 파티에 참여한 사람들은 모두 진실을 알고 있다고 간주하고, 진실을 알고 있는 사람들이 하나도 포함되어 있지 않는 파티를 카운트하는 문제입니다. 문제 태그에도 명시되어 있듯이 그래프 탐색(DFS/BFS)를 통해서도 풀 수 있지만, 분리 집합 (Union - Find 알고리즘 이용)..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 난이도 : 골드3 태그 : 그래프 이론, 위상정렬 설명 누가 누구보다 더 앞선 우선순위를 갖고 있다는 사실만으로 정렬을 하는 위상정렬 문제입니다. 예를 들어 A, B, C, D, E. 5명의 사람을 키 순서대로 정렬하려 할때, 170cm, 180cm, 190cm, 160cm, 150cm 등으로 각 사람의 키가 주어지면 손쉽게 정렬 할 수 있겠지만, A는 B보다 작다. D, E는..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 백트래킹 설명 유명한 보드게임인 스도쿠를 기반으로 한 코테 문제입니다. 빈칸에 들어갈 수 있는 경우의 수를 하나씩 찾아 대입해보고, 최종적으로 결과값을 도출해내는 백트래킹 문제입니다. DFS를 사용하여 풀이하였습니다. 소스코드 입력값 세팅 import java.io.BufferedReader import java.io.InputStreamReader imp..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 백트래킹, 깊이 우선 탐색 설명 DFS를 사용한 백트래킹을 사용하여 풀 수 있는 문제 입니다. 아이디어 자체는 빨리 떠올랐는데, 시간초과 때문에 꽤 애먹었던 문제였습니다. 처음엔 방문한 좌표와 사용한 알파벳을 각각 체크하였는데, 생각해보니 사용한 알파벳만 체크해도 되더군요. 사용한 알파벳 역시 ArrayList로 했더니 시간초과가 나..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프이론, 플로이드 - 워셜 설명 문제의 제목처럼 플로이드 - 워셜 알고리즘을 이용해 해결할 수 있는 문제입니다. 플로이드 - 워셜 알고리즘의 기본격인 문제이니, 해당 알고리즘을 알고 계신다면 어렵지 않게 풀 수 있습니다. 저는 잘 몰라서 플로이드 - 워셜 알고리즘이 뭔지 찾아보고서야 풀었네요...ㅎㅎ 소스코드 값 입력과 테이블 준비 val br = BufferedR..

파이어베이스를 추가하려고, 구글 가이드라인을 따라 Android의 build.gradle에 넣으려 했는데, 위와 같은 오류가 뜨더군요. 찾아보니, 안드로이드 스튜디오 Aritcle Fox 이상의 버전부터는 setting.gradle에 추가를 해야 한다 합니다. 안드로이드 스튜디오는 버전이 바뀔때마다 뭔가 조금씩 바뀌는데, 개발자 입장에서는 잘되던 놈이 안되니 매번 당황스러움을 느끼네요 허허...