728x90 백준8 [백준] 1927 : 최소힙 Problem 최소 힙 성공분류 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 (추가 시간 없음) 128 MB 17636 7409 5770 46.412% 문제 널리 잘 알려진 자료구조 중 최소 힙이라는 것이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제.. 2020. 9. 13. [백준] 2529 : 부등호 How to solve 이 문제는 0~9 의 수 중 각 부등호에 넣을 수 있는 수를 구하는 것이다. 부등호가 성립하도록 넣어지는 수는 중복되지 않는다. Tip1. 순열은 구할 때는, next_permutation() prev_permutation() 함수를 활용해서 구한다. Tip2. 부등호가 성립하는지 확인하는 함수를 만든다. 풀이 순서 본 문제는 다음과 같은 순서로 풀이한다. 1. 순열의 최대 값을 maxVal에 저장한다. 2. maxVal의 순열 값의 부등호 성립여부를 연산하여, 성립하면 return 한다. prev_permutation()으로 이전 순열 값을 찾으며, 1-2 과정을 반복한다. 3. 순열의 최소 값을 minVal에 저장한다. 4. 순열의 최소 값 부터 시작하여 next_p.. 2020. 9. 4. [백준] 1992 쿼드트리 (분할정복) How to solve 분할정복은 문제를 작은 사례로 나누고 작은 문제들을 해결하여 답을 얻는다. 이 문제도 맵을 나눌 수 없을 때까지 나누어서 각각을 풀면서 문제의 답을 얻는 분할정복 문제이다. 1. 현재 사각형 구간안에 있는 숫자들이 0 or 1로 이루어져있는지 확인한다. 2. 한가지의 수로 이루어져 있다면, 수를 출력한다. 3. 그렇지 않다면, 맵 크기 N -> N/2 로 계속 2로 나누어가며 각 사각형의 2, 1, 3, 4분면에서 동일 행위를 반복한다.(재귀) 4. 기저 사례를 확인한다. (N=1) Problem 쿼드트리 성공분류 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 128 MB 13690 7932 6241 57.776% 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리.. 2020. 8. 28. [백준] 1890 점프 (DP) How to solve 1. input을 배열 map_init 에 저장 2. 해당 정점까지의 경우의 수 를 더해줌 3. dp[0][0] = 1; 처음 시작점 4. dp[0][0]부터 모든 map 정점의 경로를 더해줌 5. 점프한 점의 dp 는 = 이전점 dp + 점프한 점 dp 4. 결과는 dp[N-1][N-1]을 출력 Problem 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 24691 7220 5322 28.098% 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 .. 2020. 8. 27. 이전 1 2 다음 728x90
