방배동 고구마

문제 N*N 크기의 도화지에 1~9의 색을 칠한다. 이때 직사각형 모양으로 색칠한다. 매번 다른색을 칠하며 영역을 완전히 침범하지 않는 선에서 덧칠을 할 수 있다. 이때 덧칠되지 않은 색은 몇개인지 구하라. input (도화지 크기, 색정보) 4 1230 1737 1777 0220 output 2 접근방법 1. 색영역은 무조건 직사각형이다. 색 영역의 min, max 꼭지점 좌표를 구한다. 2. 색영역을 탐색하며 해당 색 영역에 침범된 다른 색을 Checker 배열에 count한다. 3. Checker배열에서 다른 영역을 침범하지 않은 색의 갯수를 구한다. #include int N; char paint[12][12]; void input(){ scanf("%d",&N); for(int i=0; i

문제 1. N개의 건물 높이가 주어진다. (최대 80000) 2. 건물옥상에서 좌에서 우측 방향으로만 바라볼 수 있다. 3. 높이가 같거나 높으면 옥상을 볼 수 없다. 4. 이때 옥상을 볼 수있는 최대의 합을 구하라 접근 N의 갯수가 최대 8만이기 때문에 i번째 건물'이' 볼 수 있는 옥상을 이중 루프로 비교 탐색을 수행할시 시간복잡도는 O(N제곱)이다. 때문에 시간이 초과될 수 있다. i번째 건물'을' 볼 수 있는 건물을 탐색해야한다. 시간 복잡도 O(N). 1. i번째 건물을 볼 수 있는 건물을 스택에 저장한다. 2. i+1번째 건물을 볼 수 있으면 pop하지 않는다. 3. i+1번째 건물을 볼 수 없다면 pop한다. 스택에 있는 전체 건물 후보에 대해 2,3을 판단한다. 4. 스택에 남아있는 건물 ..

난 컴공이라고 하기엔 애매한 학부를 졸업했다. 해서 알고리즘등과 같은 전산학 이론에 다소 취약하다. 그래도 꾸준하게 공부하고 정리해가다 보면 빠삭해지지 않을까. 어찌되었건 오늘은 N queen을 공부해보았다. 사실 이전에 풀은 기억이 있고 그때 풀었던 코드를 다시 봤는데 내가 풀었는데 이해가 안간다. 그래서 다시 차근차근 살펴보았다. N queen. 알고리즘의 Backtracking을 다룰때 매우 빈번하게 등장하는 아무 유명한 문제이다. 문제는 간단하다. 문제 "N*N의 Table에서 체스unit Queen N개가 서로 공격하지 않게 놓일 수 있는 경우의 수" 예를 들어 N=4일때, 4개의 Queen이 놓일 수 있는 경우는 아래와 같다. 주요 아이디어 1. 퀸의 특성상, 한 행에 하나의 퀸만 있을 수 있..