알고리즘 문제풀이
-
[프로그래머스/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 ..
-
[프로그래머스/Level 2] 소수 찾기 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 3. 17:03
programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 1. 문자열의 각 요소를 정수로 바꾸어 벡터에 넣어준다. 2. 정렬을 한 후, next_permutation을 이용하여 벡터의 순열을 구한다. (num = num * 10 + v[i] 식을 통해 한자리부터 n자리 까지의 수를 구할 수 있다.) 3. 순열을 통해 만들어지는 수를 set에 저장한다. (중복을 없애기 위해 set을 사용) 4. set의 iterator..
-
[프로그래머스/Level 2] 카카오프렌즈 컬러링북 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 3. 15:33
programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 전형적인 BFS 문제로 어렵지 않은 문제다. 다만 영역을 구할 때 값이 매번 바뀌므로, 이를 tmp에 저장하고 큐의 탐색이 진행되어야 한다. #include #include using namespace std; int row, col; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int BFS(int r, int c, vecto..