시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 16367 3904 2522 25.125% 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,..

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 9503 5463 4173 58.667% 문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1≤N≤3^7, N은 3^..

https://www.acmicpc.net/problem/5620 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 1700 558 294 40.664% 문제 평면상에 n개의 점 (P1, .... , Pn) 이 놓여져있다고 했을 때, 거리가 최소인 두 개의 점을 구하고 그 거리를 알고 싶다. 입력 입력은 첫 번째 줄에 정수로 된 점의 개수 n이 주어진다. 두 번째 줄부터 n+1번째 줄까지 2개의 정수 x,y가 공백을 사이에 두고 주어진다. i+1번째 줄은 Pi 의 x,y 좌표를 의미하고 n개의 점에 대해서 주어지게 된다. 점의 개수는 2 ≦ n ≦ 500000 , 좌표의 범위는 -10000 ≦ x,y ≦10000로 주어진다. 또한, 모든 점의 좌표는 같은 것이 없이 다른 것으로 ..

인공신경망 설계 시 고려사항 Network topology 네트워크의 모양 (feed forward, feed backward) Activation function 출력의 형태 Objectives 분류? 회귀? Loss function, Error로 나타낼 수 있음 Optimizers weight update Generalization Overfitting 방지 2. activation function 출력의 형태 결정 1. one-hot vector 여러 값 중 하나의 값만 출력 ex_ 숫자 식별 2. softmax function 해당 출력이 나올 확률로 표현 3. objective function 기타 목적함수 Mean absolute error / mae Mean absolute percentag..

깊어진 인공신경망의 문제점 Generalization : training에 사용되지 않은 data에 대한 성능 Data set Training set training에 사용하는 data set Validation set 주어진 data set 중 빼놓았다가 성능을 검증할 때 사용하는 data set Test set 주어지지 않았던 접한 적 없는 data set 학습이 training set으로 진행되기 때문에, 학습을 반복할 수록 training set에 대한 정확도는 높아지고 오류율은 낮아진다. 하지만 validation set에 대한 오류율은 낮아지다가 높아지는 현상을 띄는데, 이는 학습이 너무 training set에만 적합하게 되었기 때문이다. 이를 training set에 overfitting(..

https://www.acmicpc.net/problem/1992 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 10660 6114 4794 57.420% 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 ..

7.2 문제 : 쿼드 트리 뒤집기 (문제 ID:QUADTREE, 난이도: 하) 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2^N*2^N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다. 모든 픽셀이 같은 색이 ..

7. 분할 정복 7.1 도입 분할 정복( Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라고 설명할 수 있음 주어진 문제를 둘 이상의 부분 문제로 나눈 후, 재귀 호출을 이용해 각각의 답을 계산하고, 부분 문제의 답을 이용해 전체의 답을 계산하는 방식 알고리즘 구성 divide 문제를 더 작은 문제로 분할 merge 각 문제의 답을 전체 문제의 답으로 병합 base case 더이상 답을 분할하지 않고 풀 수 있는 매우 작은 문제 적용가능한 문제의 특성 문제를 부분 문제로 나누는 자연스러운 방법이 존재해야함 부분 문제의 답을 조합해 전체 문제의 답을 계산하는 효율적인 방법이 있어야함 장점 대부분의 경우에서 작업을 빠르게 처리해줌 예제 : 수열의 빠른 합과 행렬의 빠른..