재원블로그 재원블로그

이 문제는 프로그래머스 Level 2 문제이다. 이 문제는 구현이 어려운 편에 속하고, 백트래킹을 이용해 연산자 우선순위를 정하고, long long 자료형을 사용해야 한다는 사실을 캐치하면 풀 수 있다. 수식이 정해져 있고, 연산자 우선순위가 같은 경우가 없기 때문에 다이나믹 프로그래밍을 생각해내기 어려웠다. 연산자가 최대 3개이므로 우선순위 경우의 수는 최대 6이다. 따라서 O(N) 시간의 알고리즘으로도 1초 안에 풀 수 있다. 연산하는 것까지 구현을 잘 했지만, long long 자료형을 사용해야 한다는 점을 파악하지 못해 처음에 오답이 나왔다. 그러나 문제를 다시 읽고 바로 수정한 뒤 정답을 받을 수 있었다. #include #include #include #include using namespa..

이 문제는 프로그래머스 Level 2 문제이다. 문제에서 주어진 대로 그대로 구현하면 되는 문제이다. 한 가지 주의할 점은 균형 잡힌 두 개의 문자열로 나누는 부분인데, 처음으로 acc이 0이 되는 i 를 찾아 그 부분을 중점으로 둘로 나누면 된다. #include #include #include using namespace std; bool isCorrect(string str) { stack st; int strSize = str.size(); for (int i = 0; i < strSize; i++) { char c = str[i]; if (st.empty()) { if (c == '(') { st.push(c); } else { return false; } } else { if (c == '('..

이 문제는 누적합을 이용해서 푸는 문제이다. 일단 board의 최대 크기는 1,000 * 1,000 이고, skill의 최대 길이는 250,000 이다. 최악의 경우에는 skill의 모든 값이 0,0 ~ 999,999까지를 변경하는 경우이고, 이 때 250,000 * 1,000 * 1,000 이기 때문에 당연히 시간 초과가 난다. 여기서 많은 경우를 생각해봤지만, 마땅한 알고리즘이 떠오르지 않아 해설을 봤고, 새로운 개념을 알 수 있었다. 바로 누적합을 이용하는 것인데, [n1, n2] 까지의 범위 안에서 일정 숫자를 더해주고자 할 때, 반복문을 돌려 갱신하면 O(n) 시간이 걸린다. 하지만 [n1, n2 + 1] 까지 0이 저장되어있는 배열에서 n1의 위치에 더할 숫자 x를, n2 + 1 위치에 -x를..

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 이 문제는 다이나믹 프로그래밍을 이용한 행렬 계산 수 줄이기에서 사용하는 테크닉과 매우 유사하게 풀 수 있다. 일단 입력 배열에서 짝수번 인덱스는 숫자를, 홀수번 인덱스는 연산자를 나타내는 것을 확인할 수 있고, 전역 배열을 두개를 놓아 따로 배치했다. 여기서 중요한 것은 예를 들어 0번째 숫자, 1번째 숫자에 대한 연산자는 0번 인덱스이고, 2번째 숫자, 3번째 숫자에 대한 연산자는 2번 인덱스라는 것이다. 가장 중요한 점화식을 나는 다음과 같이 간략하게 생각했다. f(s, e) : max { f(s, k) + f(k + 1, e) (0

이 문제는 이행적 폐포 (Transitive Closure) 를 이용해서 풀었다. 일단 이 문제에서 사람의 최대 수가 100명이므로 O(n^4) 알고리즘까지도 충분하다. 그리고 중요한 점은 경기 결과에 모순이 없다는 것인데, 이는 유향 그래프로 나타나지는 경기 결과에서 사이클이 없다는 소리와 같고, 이는 경기 결과에 대한 그래프가 DAG 임을 나타낸다는 것이다. 처음에는 DAG 하면 위상 정렬이 떠올라 위상 정렬로 풀려고 했지만, 마땅한 방법이 떠오르지 않았다. 그러다가 incoming edge와 outcoming edge의 수를 더한 값이 n - 1이면 순위가 확실해진다는 규칙을 찾았고, 대학교 알고리즘 수업 때 배웠던 transitive closure가 생각났다. 이행적 폐포란 a -> b 이고 b ..

이 문제는 맵을 이용해서 풀었다. 내가 처음에 구현하려고 생각했던 방법은 sellCnt를 처음에 미리 다 더해서 한번에 구하는 것이었는데, 이 방법은 오답이다. 왜냐하면 나머지를 계산하는 과정에서 버림이 발생하고, 이로 인해 2, 2 를 따로 하는 것과 4 한번에 하는 것이 다르게 나올 수 있기 때문이다. 그래서 sellCnt 를 벡터로 바꿔주고, 각 enroll에 대해 인덱스를 계산하여 해당 사람으로부터 solve를 호출하여 answer에 누적하도록 하였다. #include #include #include using namespace std; #define MAX 10000 map peopleIndex; int parent[MAX]; vector sellCnt[MAX]; vector answer; vo..

이 문제는 구현이 매우 어려운 문제였다. 일단 입력이 매우 작아 이차원 배열 최대 크기가 400이고, 400 ^ 3 까지도 가능할 정도로 넉넉한 알고리즘을 짤 수 있다는 얘기이다. 이 문제에서 핵심은 키와 자물쇠를 대볼때, 키의 인덱스와 자물쇠의 인덱스가 다르다는 것이다. 이를 해결하기 위해 dy와 dx를 생각했고, 이는 자물쇠의 y, x 좌표와 키의 y, x 좌표가 얼만큼 차이나는지를 나타낸다. 처음에는 예시에 따라 dy와 dx의 값 범위를 -M과 M 사이로 했는데, 이렇게 하면 세어지지 않는 범위가 생긴다. 이는 키의 길이가 더 짧을 수 있기 때문이다. 그래서 inRange 함수로 어차피 범위에 없으면 아예 세지 않기 때문에, 넉넉하게 -N부터 N까지를 세도록 했고, 정답을 받을 수 있었다. 이 문제..

이 문제는 스택을 이용해서 풀었다. 일단 입력 배열의 최대 길이가 100만이므로 O(n) 이하 알고리즘을 사용해서 시간 안에 풀 수 있다. 이 문제에서 핵심은 임의의 두 풍선을 선택했을 때, 결국 둘 중 하나만 터진다는 것이다. 즉, 만약 1,2,3,4,5 라는 풍선이 있고 둘 중 무조건 큰 풍선만이 터진다고 하면 순서에 상관없이 1이 나오는 것처럼, 숫자가 많거나 짝수거나 홀수거나는 중요하지 않고 결국 제일 작은 값이 남는다는 것이다. 이를 이용하면, a 배열에 대해 i 인덱스에서 왼쪽에 있는 수 중 작은 수가 존재하고, 오른쪽에 있는 수 중에도 작은 수가 존재한다면 한번만 작은 수의 풍선을 터트려서는 불가능하다. 그 다음은 이 원리를 구현하는 방법인데, 우선순위 큐, 이분 탐색 등 다양한 생각을 했지..