재원블로그 재원블로그

이 문제는 그리디 알고리즘으로 풀었다. 완전 탐색으로 가능해 보이지만, 직접 코드를 작성해보니 시간 초과가 났다. 각 단어에서 알파벳을 검사하고, 해당 위치에 대해 가중치를 10^n 단위로 매겼다. 이를 각 알파벳에 더해주고, 해당 가중치로 내림차순 정렬하여 순서대로 9부터 숫자를 매겼다. 이 방법으로 정답을 맞출 수 있었다. #include #include #include #include #include #include using namespace std; #define MAX 10 #define ALPHA 26 int N; string words[MAX]; map cost; map mappedNum; int calcPower(int power) { if (power == 0) { return 1; }..

이 문제는 그리디 알고리즘, 우선순위 큐를 사용하여 풀었다. A + B가 최소가 되게 하는 두 카드를 매번 고르면서, 카드들이 1개만 남을 때까지 반복하면 된다. 이 때 최소가 되게 하는 두 카드를 O(log N) 시간에 뽑을 수 있는 자료구조는 우선순위 큐이므로, 이를 이용하여 풀었다. #include #include using namespace std; #define MAX 100000 int N; int cards[MAX]; int solve() { priority_queue minPQ; for (int i = 0; i 1) { int a = minPQ.top(); m..

이 문제는 LIS 문제 알고리즘을 이용해서 푸는 문제이다. 입력 값 최대가 10만이므로, O(n^2) 알고리즘 사용이 불가능하다. 따라서 O(N log N) 이하의 알고리즘을 찾아야 한다. 전깃줄이 꼬이지 않게 하는 최소의 제거 전깃줄 수를 구하는 문제는 다르게 말하면 전깃줄이 꼬이지 않는 최대의 전깃줄 수를 구하는 것과 같다. 즉, 이는 입력 배열에서 LIS를 찾고 이를 N과 빼주면 된다는 말과 같다. LIS를 구하는 알고리즘 중 O(N log N) 시간을 요구하는 방법은 이분 탐색을 이용하는 방법이다. 해당 알고리즘을 통해 LIS를 구하고, 이를 N과 빼주면 정답이 나온다. #include #include #include using namespace std; #define MAX 100000 int ..

이 문제는 이분 탐색을 이용해서 푸는 문제이다. 사대의 수 M은 [1, 100,000] 이고, 동물의 수 N도 [1, 100,000]이다. 즉, 각 사대나 각 동물에 대해서 모든 동물 혹은 모든 사대를 루프로 검색하는 것은 시간 초과가 난다. 따라서 O(N log N) 이하의 알고리즘을 생각해야 한다. 각 사대에 대해 동물을 이분 탐색으로 찾는 것보다는 각 동물에 대해 사대를 이분 탐색으로 찾는 게 더 쉬워보였다. 따라서 사대 배열을 오름차순으로 정렬하고, 각 동물에 대해 루프를 돌며 이분 탐색을 수행한다. 이분 탐색 로직의 경우에는 우선 mid를 찾고, 해당 인덱스의 사대에 대해서 거리가 사정거리 이하면 true를 리턴한다. 만약 아닐 경우, 사대가 동물보다 오른쪽에 있는 경우에는 왼쪽 사대들을 검색해..

이 문제는 이분 탐색을 이용해서 푸는 문제이다. 이 문제는 일단 입력이 최대 40,000 이므로 O(N log N) 이하의 알고리즘으로 풀 수 있다. 이 문제의 핵심은 이 문제가 LIS (Longest Increase Subsequence) 문제임을 파악하는 것이다. 나는 이걸 파악하지 못해 검색을 통해 알게 되었다. 입력 예시를 보면 6 4 2 6 3 1 5 와 같은데, 꼬이지 않는 최대의 선 개수이므로 2, 3, 5를 고르면 된다. 이 형태가 최장 증가 수열이므로 LIS를 구하면 된다. LIS는 두 가지 방법이 있는데, 하나는 DP를 이용해서 푸는 방법이고 다른 하나는 이분 탐색을 이용해서 푸는 방법이다. DP를 이용할 때에는 dp[i] = i번째 값을 포함한 최장 증가 수열의 길이로 놓고 이중 루프..

이 문제는 구현, 시뮬레이션 문제이다. 문제 길이는 짧아보이지만 생각보다 어려운 문제였다. 이 문제에서 핵심은 물고기들, 상어, 물고기 냄새를 따로 저장하여 구현하는 것이다. 처음에 물고기들과 상어를 같이 넣어놓고 erase를 통해 빼면서 구현했는데, 테스트 케이스에서조차 2초 안에 답이 나오지 않는다. 이는 erase가 내부적으로 O(N) 시간이 걸리기 때문이었다. erase 함수는 되도록 그냥 사용하지 않아야겠다는 생각이 문제를 풀 수록 든다. 또한 빠뜨리기 쉬운 부분은 물고기의 방향을 찾을 때, 입력에서 주어지는 LEFT부터 시계 방향과 다르게 반시계 방향으로 탐색해야 한다. 이 부분을 까먹어 처음에 전혀 다른 방향으로 답이 나왔었다. 위 두 가지 이외에도 구현이 쉽지는 않지만, 삼성 기출 문제를 ..

이 문제는 스택을 이용해서 풀었다. 예전에 풀었다가 결국 못 풀었었는데, 이번에는 정답을 맞췄다. 스택을 pair에 대해 사용하였고, first는 문자, second는 다음 매칭되어야 할 인덱스를 저장했다. 구현은 비교적 쉽게 했는데, 계속 시간 초과가 났었다. 알고보니 이는 마지막에서 result = st.top().first + result 를 사용해서 reverse 함수 없이 바로 출력했었는데 이 방법이 O(N) 시간을 소요하게 된다고 한다. 매번 result에 O(N) 시간이 걸리므로 최악 O(N^2) 이 걸리게 되어 시간 초과가 발생하는 것이다. 그래서 result += st.top().first 를 사용하고 reverse 를 사용하면 총 O(N) 시간밖에 안 걸려 정답이 나오게 된다. #inc..

이 문제는 구현, 시뮬레이션 문제이다. 요구사항이 굉장히 까다로운데, 핵심적인 부분은 2차원 배열의 중앙부터 반시계 방향으로 배열을 읽는 방법을 구현하는 것과 구슬 폭발을 구현하는 것이다. 첫 번째는 나의 경우 nextPos 함수와 make 함수를 통해 구현하였다. nextPos는 현재 위치 기준으로 direction에 따라 다음 위치를 리턴하는 함수이고, make는 nextPos를 이용하여 전체 2차원 배열을 반시계 방향으로 순회하는 함수이다. 반시계 순회의 규칙성을 보면 중간에서 시작하여 1, 1, 2, 2, 3, 3, 4, 4, .... 의 양만큼 앞으로 가고, 방향은 왼, 아, 오, 위 순으로 동작한다. 이를 그대로 구현하면 쉽게 반시계 방향으로 읽을 수 있다. 두 번째는 구슬 폭발 구현인데, 이..