https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 바로 앞서 풀었던 문제와 동일한 유형 앞선 문제에서 태그를 까봤더니 플로이드-와샬이더라... arr[a][b] 를 a가 b 앞에 오는 사건인지 체크하는 용도로 사용한다. 플로이드 와셜을 통해서 모든 a,b 쌍들에 대해서 사건 간의 전후관계를 설정해 주고, 정답을 출력할 때 arr[a][b] 가 true라면 앞서는 것이고, arr[b][a] 가 true라면 뒤에 오는 사건인 것이고, 둘 다 ..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net DFS로 해결했다. 각 학생마다 DFS를 한번씩 돌면서 순회를 하는데, 이때 자기 자신을 포함해서 갈 수 있는 노드의 갯수를 세준다. 이 수에서 1을 뺀 것이 자기 자신보다 키가 큰 학생의 수이고, DFS 순회 과정에서 A에서 B로 갈수 있을경우 chk[B][A]에 기록해둔 뒤, 마지막에 chk[K] 배열 속의 모든 수들을 더해주고 1을 빼면 어떠한 위치에서 B로 올 수 있는 경우의 개수, 즉 자기..

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) 로 두 사람을 골라낸 다음 그 두 사람이 같..

https://www.acmicpc.net/problem/16165 16165번: 걸그룹 마스터 준석이 정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 www.acmicpc.net std::map 을 활용해서 해결한 문제. 입력 범위가 작아서 매번 비교대조하면서 해결해도 괜찮겠다만, 편리하고 깔끔하게 풀기 위해서는 std::map을 사용하면 좋다. std::map 으로 문자열과 숫자 인덱스를 서로 매칭시켜 줄 수도 있고, teamName[Name[i]] = i; 어떠한 팀 $M_i$ 에 어떠한 사람이 포함되어있는지도 맵을 사용하면 깔끔하게 판별할 수 있다. if(memb..

https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 이분 탐색 문제. N이 터무니 없이 큰 숫자라서 시뮬레이션 문제로 보면 시간초과를 피할 수 없다. 이분탐색을 통해서 "사람 N명이 탑승하는데 필요한 최소의 시간" 을 구한다. 이 시간을 T라고 하면, 정확히 T 시간에 사람이 N명 탑승하게 될 것이므로, T-1 시간에는 탑승을 하지 못한 사람들이 생기게 된다. 이 사람들 중에서 마지막 아이가 나오게 되므로, T..