분류 전체보기
-
[프로그래머스/Level 2] 가장 큰 정사각형 찾기 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 5. 17:40
programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr DP를 이용하여 푸는 문제, 정사각형 오른쪽 아래 점이 1이고, 그 점을 기준으로, 왼쪽, 위쪽, 왼쪽 가운데 점의 값이 1 이상이면 길이가 2이상인 정사각형 조건 성립 1. 처음 위치는 (1,1)에서 시작 2. 탐색 하는 점 위치를 기준으로 왼쪽, 위쪽, 왼쪽 대각선의 값 중 최소값에서 +1 (누적하며 계속해서 오른쪽 아래의 점을 갱신) 3. 최대값 = 가장 큰 정사각형의 넓이의 한 변 #include #include using namespace std; int s..
-
[프로그래머스/Level 2] 카펫 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 5. 16:29
programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 처음에 접근했을 때는 가로 세로의 길이가 갈색, 노란색 격자의 합의 약수 관계라는 규칙을 발견했고, 세로가 가로의 길이보다 같거나 작으므로 세로에 격자의 합의 제곱근 길이를 넣은 후, 합에서 세로를 나눠 가로를 구하였다. 그러나 위의 방법같은 경우 노란색 격자가 6개인 경우 문제점이 발생한다. 노란색 격자가 6개일 때, 다음과 같이 카펫이 위치할 수 있기 때문이다. BBB..
-
[프로그래머스/Level 2] 타겟 넘버 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 5. 16:23
programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 전형적인 DFS 문제였습니다. #include #include using namespace std; int answer; void DFS(int L, int sum, vector numbers, int target) { if(L == numbers.size()) { if(sum == target) answer++; retu..
-
[프로그래머스/Level 2] 구명보트 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 5. 02:15
programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 그리디가 세상에서 제일 어렵다. 1. 오름차순 정렬 2. idx가 0번(최소값)을 가리킨다. 3. 최소값과 최대값을 배에 넣어본다. 4. 최소값 + 최대값 = dq.front()) { dq.pop_back(); dq.pop_front(); } else { dq.pop_back(); } answer++; } return answer; }
-
[프로그래머스/Level 2] H-Index (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 4. 22:56
programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 인덱스의 크기가 해당 인덱스의 citations 값보다 크거나 같을 때 해당 인덱스가 H-Index가 된다. 예를들어 [3, 0, 6, 1, 5] 인 경우 내림차순으로 정렬하면 6, 5, 3, 1, 0이 되고, 인덱스 번호를 붙혀보면 0 6 1 5 2 3 3 1 -> 최초로 조건을 만족하므로 인덱스 번호 3이 H-Index 4 0 다른 예시로 ..
-
[프로그래머스/Level 2] 더 맵게 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 4. 21:12
programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 스코빌 지수가 낮은 순서대로 2개씩 리턴을 해야하는데, priority_queue를 이용한 최소 힙을 통해 쉽게 구현할 수 있다. 1. 최소 힙 우선순위 큐에 scoville 벡터의 요소들을 넣어주어 자동으로 오름차순 정렬한다. 2. 우선순위 큐의 맨 앞이 가리키는 값이 K보다 작으면서 동시에 우선순위 큐의 사이즈가 1이 아닐때까지 반복문을 진행한다. (우선순위 ..
-
[프로그래머스/Level 2] 큰 수 만들기 (C++)알고리즘 문제풀이 2020. 11. 3. 23:30
programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 처음에 DFS로 접근했는데, 입력값의 최대 범위가 1000000이라서 시간 초과가 나는 것 같다. 결국 해결하지 못해서 구글 검색을 통해 풀이를 찾아봤는데, 그리디 문제는 도대체 어떻게 생각하면 이런 풀이를 스스로 해낼 수 있는지 아직 감이 안온다. (많이 풀면 되려나 ㅠ) number가 4177252841 이고 k가 4일 때, 1. 첫번째 탐색 : i = 0, 탐색 범위 : j = 0 ~ 4(0+4), maxNum = 7, maxIdx = 2, start = 3(2+1), answer = 7 2. 두번째 탐색 : i = 1, 탐색 범위 : j = 3 ..