알고리즘
-
[백준 1476] 날짜 계산알고리즘/백준 2019. 3. 29. 02:07
쉬운 문제이다. 간단하게 날짜 범위를 생각하여, 계산하고 풀면 충분히 정답인 문제 출처 : https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1 www.acmicpc.net #include using namespace..
-
[백준 1517] 버블 소트알고리즘/백준 2019. 3. 21. 18:14
중간에 논리오류가 발생했지만, 수정 뒤에 정상적으로 출력이 가능하다.어디가 잘못된 건지, 곰곰히 생각해봐도 아직 모르겠지만, 중간에 바꾼건 사실 ans += (long long)(mid - i + 1);이 부분이 전부이긴하다. 출처 : https://www.acmicpc.net/problem/1517 문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2..
-
[백준 1074] Z알고리즘/백준 2019. 3. 21. 02:14
분할정복 문제이다. "Z" 방향으로 탐색을 하면서, 주어진 좌표가 몇 번째에 탐색이 되는지 출력하는 문제이다. 0 1 2 3 이라고 하면, 0 -> 1 -> 2 -> 3 순으로 탐색이 되며, 분할 탐색을 해가면서 각 좌표마다 입력 값과 비교하여, 결과를 출력한다. 출처 : https://www.acmicpc.net/problem/1074 문제 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다..
-
[백준 2448] 별 찍기 - 11알고리즘/백준 2019. 3. 20. 20:27
생각보다 난 별 찍기를 못하는 것 같다.꽤 오랜시간 동안, 해맨 문제. 출처 : https://www.acmicpc.net/problem/2448 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (k ≤ 10) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 24 예제 출력 1 * * * ***** * * * * * * ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***..
-
[백준 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)이 아닌 경우에는 종..