전체 글
-
[백준 2447] 별 찍기 - 10알고리즘/백준 2019. 3. 20. 17:52
분할정복 문제이지만, 생각보다 까다로웠던 문제...이해가 부족한만큼 더 공부해야겠다. 출처 : https://www.acmicpc.net/problem/2447 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (1, 3, 9, 27, ...) (N=3k, 0 ≤ k < 8) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 27 예제 출력 1 *************************** * ** ** ** ** ** ** ** ** * *************************** *** ****** ****** *** * * * ** * * ** * * * *** ****** ****** *** ******..
-
[백준 1992] 쿼드트리알고리즘/백준 2019. 3. 20. 06:38
분할정복 문제.. 왼쪽 위 -> 오른쪽 위 -> 오른쪽 아래 -> 왼쪽 아래 순으로 탐색을 나아가면 된다.다를시에는 size /= 2 및 괄호 출력 종이의 개수를 풀었다면, 무난하게 풀 수 있는 문제이다. 출처 : https://www.acmicpc.net/problem/1992 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으..
-
[백준 2263] 트리의 순회알고리즘/백준 2019. 3. 20. 05:09
인덱스 위치를 헷갈려서, 그리고 이유 모를 시간초과 문제로 몇 차례 실패했던 문제이다.종이에 쓰면서, 이해를 하려고 노력하니 이해가 되었지만....아직 100퍼센트 이해가 되지 않은 것 같아, 노력이 필요하다 문제 : https://www.acmicpc.net/problem/2263 문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력 첫째 줄에 프리오더를 출력한다. 예제 입력 1 3 1 2 3 1 ..
-
[백준 1780] 종이의 개수알고리즘/백준 2019. 3. 20. 01:35
NXN크기 행렬의 종이를 정해진 규칙에 따라서 잘라야 하기 때문에, 0 1 -1 1 0 1 => 행렬의 size/3 씩 분할 탐색을 한다.0 -1 0 0 -> 1 -> -1 -> 1 -> 0 -> 1 -> 0 -> -1 -> 0 순이다. (x축 부터) bool 변수 same을 두어, 이전과 현재 행렬의 요소가 같은지 검사해 나간다. 출처 : https://www.acmicpc.net/problem/1780 문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종..
-
[백준 11728] 배열 합치기알고리즘/백준 2019. 3. 17. 22:30
배열을 합치는 데, 병합정렬(Merge Sort)를 사용하였다.별로 어렵지 않은 문제였다. 문제: https://www.acmicpc.net/problem/11728 문제 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. 출력 첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다. 예제 입력 1 2 2 3 5 2 9 예제 출력 1 2 3 5 예제 입력 2 2 1 4 7 1 예제 출력 2 1 4 7 예제 입력..
-
[백준 1722] 순열의 순서알고리즘/백준[분발!] 2019. 3. 17. 21:00
문제 : https://www.acmicpc.net/problem/1722 문제를 처음에 보고 너무 쉽게 생각했는지, 직접 구현한 배열의 next_permutation을 사용했다.하지만, 시간초과... next_permutation으로 문제를 풀면 Big-O 표기로 O(N!)이 나오기 때문이였다. 항상 분발하는 자세로 겸손히 공부해야겠다. ㅠㅠ 실패한 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include#include using namespace std; bool next_permutat..
-
[Algorithm] C++ Bitmask란?C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 3. 17. 03:49
Bitmask란 비트위에 마스크를 씌우는 방식을 통해서어떤 위치에 집합의 원소가 존재하는지 아닌지, 추가하는 등의 행위를 말합니다. 주로 이를 마스크와 같다고 하여, 비트마스크라고 말합니다. 간단한 예시를 들자면, 네가지 원소를 가질 수 있는 집합이 있습니다. 우리는 이를 {1,2,3,4}로 나타낼 수 있습니다. 이 집합을 보다 효율적이고 간결하며 가독성있게 나타낼 수 있는 것이, 바로 비트표기이며 우리는 이를 1111(2)로 나타낼 수 있습니다. (오른쪽부터 원소 1입니다) 이 집합의 원소 중, 세번째 원소가 존재하는 지 확인하고자 한다면, 우리는 마스크를 씌울 수 있는데 이것이 비트마스크입니다. 1111(2) & 0100(2) => 0100(2) > 0 으로 세번째 원소가 존재하게 됨을 알 수 있습니..