728x90 반응형 자료구조10 [백준] 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. [백준] 9576 책나눠주기 (Greedy Algorithm) How to solve 1. 입력 받기 2. student를 b에 대해서 sort b->a 기준으로 오름차순 sort 3. M명의 학생에 대해서 책 a~b까지 보고 한개씩 나눠줌 4. 책에 대해서 check vector를 만들어 나누어준 책 표시 5. 나누어준 책 count Problem 책 나눠주기 성공분류 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 256 MB 5394 1495 1020 26.977% 문제 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다. 조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이.. 2020. 8. 27. [백준] 1202 보석도둑 (Greedy Algorithm) How to solve *priority queue 를 사용! 1. jewerly를 보석 무게 기준 기준 오름차순 정렬합니다. 2. 가방을 작은것 부터 채우기 위해 오름차순 정렬합니다. 3. K개의 가방을 차례로 채웁니다. 4. 가방의 무게보다 작은 주얼리는 모두 priority queue(pq)에 넣어줍니다. 5. 넣은 주얼리 중 가장 비싼 주얼리(pq에 내림차순으로 정렬되어있으므로 pq.top())를 선택합니다.(res에 더해줌) 6. 넣은 주얼리를 pop하고, 다음 가방을 채웁니다. Problem 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 256 MB 9203 2203 1562 23.753% 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있.. 2020. 8. 25. 이전 1 2 3 다음 728x90 반응형
