본문 바로가기

알고리즘, 자료구조/알고리즘29

[백준] 15663. N과 M(9) N과 M문제 중에 이 문제만 정답률이 47%로 낮다. 낮은 이유가 있었다. 중복되는 것에 대해서 트릭이 필요했다. 두 가지 방법을 소개한다. 수열 인덱스를 골라 나갈 것인데 예를 들어 4개중 2개를 골라보자. 4 2 9 7 9 1 2번 예제이다. 0 1 0 2 0 3 1 0 1 2 1 3 2 0 2 1 2 3 3 0 3 1 3 2 이 될것이다. 우선 v에 입력을 순서대로 저장하면 1 7 9 9 가 될 것인데, 저 순서대로 출력한다면, 1 7 1 9 1 9 7 1 7 9 7 9 9 1 9 7 9 9 9 1 9 7 9 9 이렇게 될 것이다. 중복되는 수열이 많다. 이것을 제거하는 방법은 해당 depth에서 새로운 인덱스를 고르기전에(for문전에) 이전 값을 기억하는 변수를 만드는 것이다.(before) 따라.. 2019. 10. 19.
[백트래킹] 백준 2580 스도쿠 백트래킹을 알고 있다면, 그대로 하면 풀린다! 원리는 간단하다, 모든 경우를 탐색하는 것인데 빈칸에 들어갈 수 있는 후보자를 찾은 뒤, 처음 후보자를 놓고, 다음 빈칸을 같은 방법으로 탐색한다. 그러다가 막히면(후보자가 없다거나) 다시 돌아오면 된다 (백트래킹!) 주의할 것은, 스페셜 져지문제인 만큼 답이되는 후보 제일 먼저 발견한 것을 찾으면, 바로 프로그램을 종료하면 된다. 헤더파일에 있는 exit(0)함수를 썼다. 후보자를 찾기 위해 가로세로를 탐색하고, 사각형을 탐색하는데 아이디어만 잘 내면 될 듯하다! #include #include #include #include using namespace std; int N = 9; int a[9][9]; int dx[] = {-1, 1, 0, 0}; in.. 2019. 9. 19.
[백준] 15651 N과 M (4) - 중복조합 15650 N과 M (2)를 풀었다면, 정말 거저 먹는 문제이다! 시작하는 부분만 한 단계 낮추어, 중복이 가능하게 하면된다. 이것 역시 stack버전과, 그냥 배열을 쓴 버전 두가지를 참고하시라. #include int N, M; int a[10]; void repeated_combination(int depth, int start){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] 15651 N과 M (3) - 중복순열 15650 N과 M (2)를 풀었다면 정말 쉽게 풀리는 문제이다. #include int N, M; char a[15]; void repeated_permutation(int depth){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] N과 M (2) - 조합 조합. depth를 증가 시키는 것과, start를 하나 더 늘리는 것이 관건이다. 한 재귀함수가 호출되면, depth가 고정되어 있는 채로, start와 관련된 i 인덱스가 바뀌면서 다음 조합의 수를 채운다. #include int N, M; int a[9]; void combination(int depth, int start){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] 15649 N과 M (1) - 순열 단계별로 풀어보기에서 N과 M 시리즈 4개 중 개인적으로 가장 어렵다고 생각한다. 하지만, dfs와 백트래킹을 알고 있다면, N과 M문제 자체가 그렇게 어려운 편은 아니다. DFS는 그래프에서 깊이 우선 탐색을 의미하지만, 완전 탐색에서 주로 쓰이는 알고리즘으로, 모든 것을 다해보는 브루트포스 알고리즘과도 연관이 있다. 백트래킹은 여기에 조건을 더해주어, 원하는 경로로 탐색할 수 있게 도와주는 장치이다. 구현 코드 2개를 소개하고자 한다. #include using namespace std; int n, m; int a[8]; void swap_(int &a, int &b){ int temp = a; a = b; b = temp; } void rotateR(int start, int end){ int t.. 2019. 9. 19.
[BFS] 2206 벽 부수고 이동하기 #include #include using namespace std; struct Pos { int x, y, b; }; queue q; char a[1001][1001]; int dist[1001][1001][2]; int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}; int main() { int n, m; scanf("%d %d", &n, &m); for (int i=0; i 2019. 9. 12.
[백준] 1694 숨바꼭질 BFS를 잘 활용하면 되는 문제. 그래프를 잘 생각 해보자. 각 숫자들을 그래프의 노드라고 했을 때, 1만큼 떨어진 이웃하는 숫자는 양방향 간선으로 다 이어져 있고, x노드에서 2x노드로 가는 간선들이 있다. BFS는 모든 정점과 간선을 살펴보는 알고리즘이므로 시간복잡도는 O(|V| + |E|)인데, V = 100,000, E < 300,000 이면 충분할 거라고 생각했다. 참고로 memset에 사이즈를 sizeof(d)/sizeof(int) 라고 했다가.... 수없이 실패를 했던 문제이다. 나머지는 최단거리를 구하는 BFS문제로 직관적으로 쉽게 풀 수 있다. #include #include #include using namespace std; int d[100001]; int main() { int n.. 2019. 9. 12.
[이진탐색] 1920 수 찾기, Binary search Binary search는 '정렬된 배열'에서 특정 원소를 찾을 때, O(logN)의 탐색시간을 보장합니다. 따라서, O(N)만큼 걸리는 Linear search 보다는 성능이 좋을 수 있습니다. 처음에는 재귀함수로 구현하였고, 이와 거의 비슷하게 반복문으로 구현할 수 있었습니다. #include #include int a[100001]; // array는 정렬되어 있어야 함. int binarySearch(int first, int last, int k){ int mid = (first + last) / 2; if (first > last) return -1; else { if (a[mid] == k) return mid; else { if (a[mid] < k){ binarySearch(mid + 1.. 2019. 8. 29.
[Deque] 5430 AC (백준) Deque의 성질을 잘 활용해야 하는 문제. 이것을 데크를 무시하고, 리버스를 처음에 그대로 구현했다가.. 시간초과가 났다. p의 길이의 합과 n의 합이 70만을 넘지 않다는 것이지... p x n 이 70만을 안 넘는 것은 당연히 아니었다. 리버스 있는 그대로 해서 하는 순간 reverse가 O(N)이라고 가정하면, 전체 수행시간이 O(PN)이 되어 10억, 즉 10초 정도로 시간초과가 난다. 그래서, 아이디어는 리버스했을 때 front인지 rear인지 설정을하고 각각 pop_front, pop_back을 해주면된다. 개념적으로는 참 쉬운데, 문자열 다루는데 익숙하지 않았던지 푸는데 너무 오래걸렸다. string 객체의 substr을 잘 이용해보았다. string s; s = "2019.08.28" i.. 2019. 8. 28.
728x90

티스토리툴바