https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 그래프에서 사이클을 찾아내는 문제. DFS로 접근했다. dfs를 진행할때, 바로 전에 지나고 있던 점의 위치를 px, py에 담아놓아서, 탐색한 다음 뒤를 돌아서 다시 탐색하는것을 막아준다. 보통은 방문 여부를 저장하는 vis 배열을 통해서 재탐색을 막아주는데, 방문여부를 통해서 재탐색을 막을 수 없는 이유로 문제에서 요구하고 있는 것이 "방문한 적이 있던 같은 점의 색을 가진 위치" 로..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 브루트포스 문제이다. 어떠한 위치 i에서 고일수 있는 물의 양은, 그 양쪽으로 i보다 높이가 높은 두개의 블록 l,r 이 있을때, min(l,r) - i 만큼 고일 수 있다. 모든 i에 대해서 순회하는데 O(N), 높이가 최대로 높은 두 블록 l,r 을 찾는데 O(N)으로 전체 시간복잡도는 O(N^2) 이다. 위치 i에서 l,r을 찾고자 할때, l이나 r이 존재하지 않는 경우가 ..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 이분탐색 문제이다. 세 수를 선정할 때에, O(N^3) 브루트포싱으로 접근하면 시간초과를 받게 되므로 세 숫자 중 하나는 이분탐색을 통해서 골라내야 한다. O(N^2) 로 두개의 쌍을 더해서 그 합 SUM 을 만들어 주고, SUM의 음수와 가장 가까운 수를 이분탐색으로 구해준 다음 셋의 합이 0에 가까워지도록 갱신해나가면 된다. 이때, lower_bound로 구한 인덱스가 k..

https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 우선순위 큐 사용 문제. 하나의 우선순위 큐에 임시파일을 포함한 모든 파일들을 저장해놓고, 실시간으로 가장 비용이 작은 두개의 파일을 합쳐서 하나의 임시파일로 만들어주면 된다. 이 과정을 파일이 하나만 남을때까지 반복해주면 되고, 전체 시간복잡도는 O(KlogK) 이다. 입력되는 수의 갯수가 1e6으로 꽤나 많으니 fastio를 써야 할 듯 하고, 수의 범위가 int값을 넘어가니까 long l..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 투 포인터 알고리즘을 사용하는 골드4 문제. 문자열의 길이 S가 1e6으로 커서 투 포인터 알고리즘을 사용해야 한다. 구간 [s,e] 안에 있는 알파벳의 종류가 N을 넘지 않도록 관리해주면 된다. 알파벳의 종류를 세주기 위해서, 일반적이라면 map 등을 만들어서 관리하게 될 텐데, char 가 0~255 사이의 숫자 아스키코드에 대응한다는것을 통해 그냥 256개의 배열을 만드는 방법으로 map 를 대체할 ..

https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 비트마스킹을 사용해서 풀었다. 재귀로 풀어도 상관없다. 비트마스킹을 통해서 팀 A와 B를 구분해주었다. i번째 비트가 1으로 켜져있다면 i번째 사람은 A팀에 들어간 것이고 i번째 비트가 0으로 꺼져있다면 i번째 사람이 B팀에 들어간 것이다. 사람 20명으로 만들어 낼 수 있는 모든 경우에 대해서, O(N^2) 로 두 사람을 골라낸 다음 그 두 사람이 같..