본문 바로가기

Algorithm66

[프로그래머스] 입국심사 c++ 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43238 KEY 시간을 기준으로 이분탐색한다는 방법 자체를 떠올리기가 어려운 문제다. 1분~가장 오래 걸리는 시간 까지 이분탐색으로 시간을 탐색하면서, 모든 사람이 심사를 받을 수 있는 시간 중 가장 짧은 시간대를 찾으면 된다. 시간을 심사대의 시간으로 나누어 더함으로써 완료할 수 있는 사람 수(cnt)를 센다. 가령 심사대는 7, 10분 두개가 있고, 지금 시간이 30분이라고 할 때, 완료할 수 있는 사람 수는 30/7 + 30/10 = 6이다. 자료형에 조심하자. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2.. 2023. 4. 6.
[백준] 1920 수찾기 c++ 문제 링크 https://www.acmicpc.net/problem/1920 KEY 이중for문을 돌려서 일일이 확인하는 작업은 100,000 * 100,000 O(N^2)으로 시간초과가 발생한다. 따라서 O(logN)의 시간복잡도를 갖는 이분탐색과 map, ordered_map을 활용하여 풀이할 수 있다. unordered_map: HashTable로 구현된 자료구조. 탐색 시 O(1)의 시간복잡도 map: 이진탐색트리로 구현된 자료구조. 탐색 시 O(logN)의 시간복잡도. map의 경우 자동으로 정렬되므로(Red Black Tree의 특징) 삽입/삭제가 빈번할 경우 성능이 저하되는 특징이 있다. 따라서 이 문제와 같은 경우 최대 100,000번 불필요한 정렬을 할 수 있으므로, unordered_m.. 2023. 3. 31.
[프로그래머스] 등굣길 c++ 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42898 KEY 101 * 101 의 arr배열을 선언 한 후, 물 웅덩이가 있는 부분에 -1을 넣는다. 시작부분인 arr[1][1]에 1을 넣는다. 1 0 0 0 0 -1 0 0 0 0 0 0 arr[i][j] = arr[i-1][j] + arr[i][j-1]의 점화식으로 arr[i][j]에 값을 넣어가며 최단경로의 가짓 수를 구할 수 있다. 1 1 1 1 1 -1 1 2 1 1 2 4 백트래킹으로 최단경로의 가짓수를 구하는 방식으로 풀면 테스트케이슨는 모두 통과했지만 전부 시간 초과가 발생한다. 격자의 크기가 100*100이나 되서 재귀로 푸는데에는 시간초과가 뜰 수 밖에 없다. Dfs.. 2023. 3. 30.
[백준] 9251 LCS c++ 문제 링크 https://www.acmicpc.net/problem/9251 KEY LCS문제는 다음과 같이 행열로 두 문자열을 나열한 다음, 이중 for문을 활용해서 풀이한다. 아래 표를 만들어 내는 것이 핵심이고, 규칙성은 다음과 같다. 두 문자가 같은 경우 : 대각선 이전의 값에 1을 더한다. 두 문자가 다를 경우 : 자신의 왼쪽과 위쪽 중 최댓값을 취한다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include #include using namespace std; string str1; string str2; int dp[1001][1001]; int main() { cin >> str1 >> str.. 2023. 3. 29.
[백준] 2565 전깃줄 c++ 문제 링크 https://www.acmicpc.net/problem/2565 KEY 문제에서 없애야 하는 전깃줄의 최소 갯수를 구하라는 말은, 전깃줄의 전체 갯수 - 엉키지 않도록 하는 전깃줄의 최대 갯수를 구하라는 말과 동일하다. 입력값의 first를 기준으로 오름차순 정렬을 하면 first를 고정시킬 수 있으므로 second만 고려할 수 있다. 문제의 예제를 살펴보면, 정렬 후 second는 8, 2, 9, 1, 4, 6, 7, 10로 나타난다. 여기서 8, 9, 1을 없앤다면 2,4,6,7,10이 될 것이고, 이는 엉키지 않도록 하는 전깃줄의 최대 갯수가 된다. 따라서, 순열이 주어졌을 때, 가장 긴 증가하는 부분수열의 길이를 구한 후, 전체 갯수 N에서 빼주면 없애야 하는 전깃줄의 최소 갯수가 나.. 2023. 3. 28.
[백준] 11054 가장 긴 바이토닉 부분 수열 c++ 문제 링크 https://www.acmicpc.net/problem/11054 KEY 가장 긴 증가하는 부분 수열 문제와 풀이 과정이 거의 같다. 참고 --> https://everydayyy.tistory.com/136 [백준] 11053 가장 긴 증가하는 부분수열 c++ 문제 링크 https://www.acmicpc.net/problem/11053 KEY 현재 자신과 이전에 나왔던 수들을 비교해가면서, 현재 자신 > 이전의 수를 만족할 경우에 길이+1을 해주고, 가장 긴 길이를 자신의 길이로 취한다. 예 everydayyy.tistory.com 위 글을 간단히 요약하자면, 가장 긴 증가하는 부분수열는 다음과 같이 구할 수 있다. 현재 자신과 이전에 나왔던 수들을 비교해가면서, 현재 자신 > 이전의 수.. 2023. 3. 28.

티스토리툴바