//white: 0, black: 1 #define SIZE 128 #define F first #define S second #define X dir_x #define Y dir_y #include using namespace std; int col; int cnt[2]; //index 0: white, 1:blue int map[SIZE][SIZE]; // change - true, not change - false bool check(int x1, int y1, int x2, int y2) { col = map[x1][y1]; for (int i = x1; i < x2; i++) { for (int j = y1; j < y2; j++) { if (col != map[i][j]) return true..

1. 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 풀이 단순히 모든 칸을 한칸씩 다 탐색했더니 시간초과가 나왔다. N의 최대값을 살펴보니 15이다. 최대 size는 2의 15승이므로 32,768이 된다. 즉, 최대넓이는 32,768 x 32,768 = 1,073,741.824로 10억이 넘어간다. 결국 10억이 넘는 칸을 모두 탐색할 경우 대충 10초가 나온다.(1억번 탐색하면 약 1초가 나오므로) 따라서 구역을 확인 후..

1. 재귀 함수란? 한자로 풀어서 해석하면 다시 "재(再)" 돌아올 "귀(歸)", 말 그대로 다시 돌아오다 라는 뜻이다. 프로그래밍의 관점에서 재귀란 "함수 자신을 다시 호출하다"라는 의미이다. 2. 재귀함수의 쓰임 재귀함수는 기본적으로 현재의 condition을 유지한 상태로 전의 작업과 비슷한 행동을 할 때 매우 유용한 알고리즘이다. 이러한 재귀함수의 특성때문에 stack, 분할정복 등의 많은 문제에서 활용되곤 한다. 다음은 재귀함수로 간단하게 구현할 수 있는 문제이다. https://wondrous-developer.tistory.com/1 [백준 17609] 회문 (C++) 처음 고민했던 사고과정과 이후 정답풀이를 같이 정리해 놓았다. 1. 문제 https://www.acmicpc.net/prob..

hanoi함수 void hanoi(int n, int from, int to) { if (n == 0) return; hanoi(n - 1, from, 6 - from - to); cout

1. monotone stackmonotone stack은 stack의 한 종류로 "단조로운 스택"이란 뜻이다. 우리말로 해석하자면 단순하게 증가하거나 감소하기만 하는 stack이다. 즉, 오름차순 또는 내림차순의 형태만 가지는 stack을 말한다.2. 활용데이터를 다루거나 알고리즘 문제를 푸는 과정에서 stack을 사용할 때 오름차순 또는 내림차순으로 stack을 유지해야하는 경우가 생긴다.

분할 정복 알고리즘을 이용해 L - 트로미노 도형으로 정사각형을 채우는 문제를 풀 수 있다. https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8#/media/%ED%8C%8C%EC%9D%BC:Geometrical_dissection_of_an_L-triomino_(rep-4).gif 트로미노 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 모든 자유 트로미노 트로미노 (tromino) 또는 3-오미노 (3-omino)는 n=3인 폴리오미노로, 크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형이다. 자유 트로미노 (fr ko.wikipedia.org 위 사이트에 들어가면 L - 트로미노 도형으로 정사각형을 채우는 ..

공부하다 보면 항상 부족한 점이 많다고 느낀다. 그럴수록 더더욱 기본적인 태도가 중요함을 느낀다. 코딩은 평소 습관이 중요하다. 알고리즘대회나 코테를 치는 경우 평소 코딩습관이 그대로 반영되어 큰 영향을 미치곤 한다. 따라서 대회나 시험당일에 빠르고 효율적으로 문제를 풀기 위해 평소 길러야할 기초 코드 작성요령을 정리하려고 한다. 종만북이라는 유명한 책이 있다. 대회를 통해 배우는 알고리즘 문제해결전략이라는 책이다. 필자는 이 책을 참고하여 알고리즘을 연습중이다. 따라서 공부하며 느낀점을 따로 정리하려고 한다. 1. 반복은 되도록이면 피하는게 좋다. 코딩을 할 때 가장 우선시되어야할 기본적인 태도이기도이다. 조건문이나 반복되는 변수를 사용할 때 이를 활용하면 시간을 절약할 수 있다. 2. 변수명은 최대한..

1. 문제 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 레이저로 쇠막대기를 자른다. 쇠막대기와 레이저가 주어졌을 때 잘려서 나누어진 막대조각의 수를 구하는 문제이다. 이때 주어진조건은 다음과 같다. ()는 무조건 레이저를 나타낸다. 한 막대의 밑에는 위의 막대보다 긴 막대만 올 수 있다. 쌓인 막대의 양끝부분은 겹치지 않는다. 2. 풀이 현재의 condition을 유지한 상태로 같은 작업을 반복한다는 점에서 stack의 자료구조가 떠올랐다.