Toolofv 님의 블로그

백준 - 1018 체스판 다시 칠하기지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.www.acmicpc.net 문제지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있..

백준 - 12789 도키도키 간식드리미백준 - 12789 도키도키 간식드리미www.acmicpc.net문제인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만..

GPT가 만든 Monotonic Stack 문제 - 수열 A가 주어졌을 때, 각 원소 A[i]를 기준으로 자기보다 작지 않은 수들이 연속된 가장 넓은 구간을 찾으시오.구간은 왼쪽과 오른쪽으로 확장할 수 있으며, A[i]보다 작은 수가 나오면 거기서 멈춰야 합니다.수열 A가 주어졌을 때, 각 원소 A[i]를 기준으로 자기보다 작지 않은 수들이 연속된 가장 넓은 구간을 찾으시오.구간은 왼쪽과 오른쪽으로 확장할 수 있으며, A[i]보다 작은 수가 나오면 거기서 멈춰야 합니다.toolofv.tistory.com/287 문제 수열 A가 주어졌을 때, 각 원소 A [ i ]를 기준으로 자기보다 작지 않은 수들이 연속된 가장 넓은 구간을 찾으세요.구간은 왼쪽과 오른쪽으로 확장할 수 있으며, A [ i ]보다 작은..

퀵 정렬(Quick Sort)은 병합 정렬(Merge Sort)와 비슷하게 분할정복(Divide and Conqueror)의 방법으로 정렬되는 알고리즘이다. 퀵 정렬은 시간복잡도로는 복불복이다. 최선, 평균의 경우 $O(n\ log\ n)$이지만 최악의 피벗을 선택했을 경우 $O(n^{2})$이다. 공간복잡도는 추가적인 배열을 만들지 않는 In-Place 방식의 경우 추가배열이 만들어지지 않지만 재귀함수 호출로 인해 $O(log\ n)$이다. 추가적인 배열을 선언하는 Non-In-Place 방식은 $O(n)$이다. 퀵 정렬(Quick Sort)  1. pivot을 왼쪽으로 몰거나 오른쪽으로 몰아 하는 방식이 있다.(아래는 왼쪽 이동하는 방법이다.)2. pivot값을 지정한 후 l ,  r 을 pivot값..

정렬 알고리즘은 사실 실제로 구현해서 사용할 일은 없는 것 같다. 매일 잊어먹기 때문에 기록의 용도로 올린다. 병합 정렬(Merge Sort)의 시간복잡도는 최악의 경우부터 최선의 경우 모두 $O(n\ log\ n)$이고, 공간복잡도는 $O(n)$이다. 배열의 크기에 비례하는 공간이 필요하다.  병합 정렬(Merge Sort)  병합 정렬은 배열을 재귀함수로 계속 분할하고 끝에서부터 병합하면서 정렬이 되는 구조다. 타고타고 병합이 완료되면서 정렬된다. - 코드import syssys.setrecursionlimit(10**6)input = sys.stdin.readlined = [1, 6, 8, 2, 9, 3, 7, 5, 4]def merge_sort(d): if len(d) = len(l) or ..

힙(Heap) 정렬 알고리즘은 정렬의 용도로 주로 쓰인다고 볼 수는 없는 것 같다. 힙 자료구조는 원소가 들어갈 때 최댓값, 최소값을 꺼내쓰는데 효율적이기 때문에 다익스트라(dijkstra) 알고리즘같은 경우에도 사용된다. 시간복잡도는 $O(n\ log\ n)$이다. 완전이진트리(complete binary tree)다. 파이썬의 경우 heapq 모듈을 사용한다. 힙 자료구조화와 정렬은 좀 다르다.  Siftdown( )의 경우 범위를 받고 부모노드(parent)를 지정한다. 바로 밑의 자식 노드를 child로 지정한 후 오른쪽의 자식 노드와 비교해 큰 값을 최종 child로 정한다. 지정된 부모노드와 자식 노드를 비교하고 자식 노드 값이 크면 바꿔준다.(최대힙의 경우) 그 것을 반복하면 부모노드와 자식..

백준 - 2583 영역 구하기첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. www.acmicpc.net문제눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다.   와 ..

백준 - 2573 빙산첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. www.acmicpc.net문제지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.  빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되..

백준 - 10026 적록색약적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. www.acmicpc.net문제적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 ..