msmn

분류: 백트래킹, 순열 문제: www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2가지 방식으로 풀었다. 1번은 백트래킹, 2번은 순열 C++의 next_permutation을 활용한 풀이 1. 백트래킹 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include ..

분류: 재귀, 분할정복 문제: www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define INF 1e9 using nam..

분류: 정렬, 맵 문제: www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 최빈값 처리를 위해 맵에 숫자/빈도수를 저장해주고 pair 벡터로 옮겨서 빈도수로 정렬해주었다. 이 때, 같은 빈도수가 있다면 두 번째로 작은 수를 출력하도록 했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include ..

분류: 그래프 탐색 문제: www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 방문할 수 있는 정점이 여러 개인 경우 정점 번호를 작은 것부터 방문하므로 구현의 편의를 위해 인접행렬을 활용했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #inc..

분류: 문자열, 트라이(Trie), 정렬, 해시맵 문제: www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 3가지 방법으로 풀어본 문제이다. 정렬을 사용한 방식이 가장 효율성이 높았다. 1. 정렬 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #..

분류: DP, LIS, BS 문제: www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net DP를 활용한 LIS(Longeset Increasing Subsquence)로 해결했다. O(nlogn)을 구현하기 위해 이분 탐색으로 풀었고 이때 C++의 lower_bound를 활용하였다. LIS를 추적하기 위해 LIS 배열을 선언하여 dp벡터의 인덱스(LIS의 길이)를 저장했고 LIS배열을 오른쪽부터 읽으며 최장 부분 수열을 추적해나가는 ..