코딩복습장

이번 글에서는 Heap sort를 구현해볼 것이다.  heap은 max heap을 사용할 것이다.  우리는 배열에 데이터를 넣고 heap으로 사용할 것이다.  이전 글에서 우리는 배열로 complete binary tree를 만들때 부모노드를 구하는 방식을 배웠다. 여기서 자식노드를 구하고 싶을 경우왼쪽 자식노드: 부모노드 index x 2오른쪽 자식노드: 부모노드 index x 2 + 1이 공식은 배열의 0번째 index가 비워져 있을 때의 공식이다.  배열을 모두 채웠을 경우는 공식이 아래와 같아진다. (한칸씩 배열이 왼쪽으로 밀림) 부모 = 배열의 길이 // 2 - 1왼쪽 자식 = 부모 * 2 + 1오른쪽 자식 = 왼쪽 자식 +1우리는 이 공식을 이용하여 힙 정렬을 구현할 것이다.  우리는 가장 오..

문제 링크: https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 제한시간 메모리 제한 제출 정답 맞힌사람 정답비율 2 초 512 MB 59554 27499 16507 42.719% 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 ..

문제링크: https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 512 MB 44422 20021 14375 44.317% 문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r..

오늘은 kobis의 2015~2023년 영화 데이터를 분석해보려고 한다. column의 개수는 총 19개이고 데이터의 개수는 14301개이다. Data preprocessing missing value에 대한 graph를 뽑아보았다. (데이터의 분포 확인) 다음과 같이 나오는 것을 확인할 수 있는데 여기서 알 수 있는 점은 영화의 제작사와 수입사 column에 null데이터가 굉장히 많다는 것 이었다. 따라서 제작사와 수입사 column을 제거시켜주었고 영화 유형과 영화 형태 column의 경우 동일한 데이터가 굉장히 많아 제거시켜주었다. 영화 등급 column preprocessing 영화 등급의 개수 그래프를 출력해보았다. 여기서 청소년관람불가, 15세이상관람가, 12세이상관람가, 전체관람가를 제외한..