재원블로그 재원블로그

이 문제는 수학 문제에 가깝게 풀었다. 일단 최대 n의 크기가 20인데, 20!은 2,432,902,008,176,640,000 라는 엄청난 수가 나오고, 당연히 단순 순회로는 이 문제를 풀 수 없다. 그러나 한가지 중요한 점은 20!이 long long 자료형에 담긴다는 사실이다. 즉, 팩토리얼을 이용한 어떤 수식을 사용할 수는 있다. 일단 n = 4 일때의 모든 순열을 구하고, 규칙을 찾아봤다. 1 2 3 4 - 0 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 - 6 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 - 12 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 - 18 4 1..

이 문제는 bfs를 이용해서 풀었다. 일단 입력 2차원 배열이 최대 100 * 100 이므로 bfs를 돌리기에 충분한 시간이었다. 기본적인 구현이므로 빠짐없이 구현만 하면 정답이 바로 나오는 쉬운 문제였다. #include #include #include #include #include using namespace std; int dy[] = {-1, 0, 1, 0}; int dx[] = {0, -1, 0, 1}; bool visited[100][100]; int N; int M; bool inRange(int y, int x) { if (0

이 문제는 투 포인터를 이용해서 풀었다. 일단 이 문제의 입력 배열의 최대 크기가 100만이므로 O(n) 시간 이하의 알고리즘을 사용해야 한다. 그래서 투 포인터를 떠올렸고, 왼쪽에서 두 포인터가 모두 시작하는 방향으로 구현하였다. 정답으로 리턴해야하는 값이 부분 배열의 처음과 끝 인덱스인데, 끝 인덱스가 포함된 범위이므로 right++을 할 때 더 조심해야 한다. 그래서 right++을 하는 로직마다 size를 넘었는지 체크하는 부분을 집어넣었다. 또한 왼쪽에서 둘 다 시작하는 투 포인터는 반드시 두 포인터가 만났을 때는 right가 증가해야 두 포인터가 교차하여 발생하지 않게 된다. #include #include #include using namespace std; vector solution(ve..

이 문제는 진법 변환 문제이다. 나는 처음에 이 문제를 백트래킹을 이용해서 풀었으나, 효율성 검사에서 시간 초과가 나왔다. 아무리 최적화를 해도 시간 초과가 나온다. 그래서 검색을 해보니 단순 진법 문제였다. 이 문제에서 핵심은 3으로 나눈 나머지가 0일 때 4를 추가해주고, n을 1 빼줘야 값이 제대로 나온다는 것이다. 그 점만 파악하면 쉽게 풀 수 있었을 것 같다. #include #include #include using namespace std; string solution(int n) { string answer = ""; while (n > 0) { int rem = n % 3; n /= 3; if (rem == 0) { answer = '4' + answer; n--; } else if (r..

이 문제는 스택을 사용하는 문제이다. order의 최대 길이가 100만이므로 O(n) 시간 이하 알고리즘을 사용해야 한다. 문제를 잘 읽어보면 보조 컨베이어 벨트가 스택 구조라는 것을 알 수 있다. 처음에 알고리즘을 구상할 때는 box와 order를 한 루프 안에 전부 해결하려고 했으나, 이렇게 하면 로직이 매우 복잡해진다. 일단 box에 대해 모든 연산을 다 수행한 뒤, 스택에 남은 것을 처리하는게 훨씬 간편하게 구현할 수 있었다. 한가지 주의할 점은 box 반복문에서 st.top()이 현재 order와 같은 경우 box를 고려하지 않았는데 for문에 의해 더해지므로 box--을 해놔야 box는 그대로고 스택에서만 뺄 수 있다는 것이다. 이 부분만 생각할 수 있다면 구현은 어렵지 않은 문제였다. #in..

이 문제는 맵을 이용해서 풀었다. topping의 최대 길이는 100만이므로, O(n) 시간 이하의 알고리즘을 써야만 시간 안에 풀 수 있다. 절반을 자르는 로직은 왼쪽은 topping의 처음부터 half를 포함하는 범위까지로, 오른쪽은 half + 1부터 마지막까지로 정했다. topping을 순회하면서 절반을 자르고, 여기서 추가 반복문을 사용하지 않기 위해 map으로 해당 숫자의 count를 저장하고, left에서는 해당 값이 0일때 추가되면 leftCnt++을, right에서는 해당 값이 0이 되면 rightCnt--을 수행하여 정답을 도출했다. #include #include #include using namespace std; int solution(vector topping) { int ans..

이 문제는 다이나믹 프로그래밍을 이용해 풀었다. 사실 이 문제는 bfs로 풀어도 전혀 상관이 없어보이는게 2와 3을 곱해서 수가 빠른 속도로 커지기도 하고, x부터 시작해서 세 연산 모두 무조건 커지기 때문에 충분히 가능할 것 같다. 하지만 나는 이 문제를 처음 보자마자 dp가 떠올라서 그걸로 풀었다. 다이나믹 프로그래밍으로 풀 때 유의 사항은 처음으로 dp 배열에 값을 집어넣는다고 해서 그 값이 최적이 아닐 수 있다는 사실이다. 처음에 나는 dp 배열이 -1이면 dp[i] + 1을 저장하고 다음 수로 넘어갔는데, 이렇게 하면 테스트 케이스에서 일부 오답이 나온다. 그래서 dp가 -1이 아니더라도 dp[i] + 1과 저장되어 있는 값을 비교하여 최소를 저장하는 로직을 집어넣었더니 바로 정답이 나왔다. #..

이 문제는 스택을 이용해서 푸는 문제이다. 처음에는 덱을 이용해서 풀었는데 테스트 22번에서 시간 초과가 났다. 아무리 해도 정답이 나오지 않아 검색을 했고, 스택을 이용해서 훨씬 간단하게 풀 수 있었다. 일단 입력 배열의 최대 길이가 1,000,000 이므로 무조건 O(n) 이하의 알고리즘을 구상해야만 한다. 덱을 이용했을 때의 수도 코드는 다음과 같다. (시간 초과) answer[n] = -1 for (i : n - 1 -> 1) 만약 numbers[i + 1] > present dp.push_front(numbers[i + 1]); answer[i] = numbers[i + 1] 그렇지 않다면 dp 덱 순회하여 present보다 큰 값 있는지 확인 만약 없으면 answer[i] = -1 있으면 an..