재원블로그 재원블로그

이 문제는 플로이드 워셜을 사용해서 푸는 문제이다. 정점의 개수가 최대 200개로, O(n^3) = 800만이므로 시간 안에 충분히 계산이 가능하다. INF 값을 적절히 할당하는 것이 중요한데, 정점 개수가 최대 200개이고 간선의 가중치가 최대 10000 이므로 2억이라고 단순 계산했다. 따라서 그것보다 큰 3억으로 INF를 설정했고, 정답을 맞출 수 있었다. 처음에는 그래프와 가중치가 나와서 다익스트라를 생각했지만, 여러 쌍의 경우를 전부 알아야 하므로 플로이드 워셜이 효율적이라 생각해서 문제를 풀었다. #include #include #include using namespace std; #define INF 300000000 int dist[201][201]; void init() { for (in..

이 문제는 프로그래머스 level 3 문제이다. 이 문제를 처음에 풀 때 입력이 25 * 25 = 625로 작아 백트래킹으로 풀릴 줄 알았다. 그러나 방향이 4가지이기 때문에 모든 칸이 빈칸인 경우 각 칸마다 4가지씩, 즉 어림잡아 4^625 정도로 절대 시간 안에 풀 수 없다. 그래서 bfs를 떠올리게 되었고, 그 중에서 다익스트라 알고리즘과 유사한 형태가 떠올라 그 방식으로 풀었다. 다익스트라 알고리즘의 핵심은 우선순위 큐 사용인데, 처음에 방향에 따른 cost를 생각하지 않고 정해진 방향으로 풀면 정답이 나오지 않는다. 방향에 따른 루프를 시작할 때, 무조건 현재의 방향을 우선으로 고려해야 정답이 나온다. 또한 이미 저장된 cost와 현재 값을 비교할 때 그 값이 같을 때에도 큐에 값이 들어가야 한..

이 문제는 프로그래머스 level 3 문제이다. 처음에는 완전 탐색을 이용해서 풀어보려고 했지만, 당연히 시간 초과가 났다. 징검다리의 횟수가 최대 2억번이기 때문이다. 그래서 그 다음으로는 스택을 사용하는 것처럼 i번째에서 이전 돌들과 비교해서 같거나 큰 징검다리가 나올때까지의 횟수를 세고, 이 값이 k보다 크면 그 높이를 정답으로 내는 방식으로 풀었다. 그러나 이 방식으로는 징검다리가 내림차순으로 되어있는 경우 제대로 된 값이 나올 수 없다. 구글링을 해서 풀이를 보니 이분 탐색으로 문제를 풀 수 있었다. 입력이 큰 것부터 이분 탐색을 생각했어야 했는데 아쉬웠다. 이분 탐색을 생각만 한다면 굉장히 쉽게 풀리는 문제였다. #include #include #include using namespace st..

이 문제는 백트래킹과 맵을 이용해서 풀었다. solution의 첫 for문은 각 banned_id에 부합하는 user_id를 찾아내는 것이고, solve 함수는 이를 기반으로 백트래킹을 돌려 해당 조합이 사용되었는지 확인한 후, 사용되지 않았으면 1을 리턴하는 것이다. 입력의 크기가 user_id, banned_id 모두 8 이하로 매우 작아 완전 탐색으로 가능한 문제였다. #include #include #include #include using namespace std; vector banned_list[8]; map listUsed; bool userUsed[8]; int solve(vector ban, int bannedSize, int bannedIndex) { if (ban.size() == ..

이 문제는 프로그래머스 level 3 문제이다. 이 문제를 처음에는 백트래킹을 이용해서 풀었으나, 당연히 시간 초과가 났다. dp를 이용해서 푸는 문제임을 알았지만, 방법을 떠올리지 못했다. 이 문제는 dp 배열을 i번째 스티커까지 왔을 때 최댓값으로 생각하면 풀 수 있다. 여기서 중요한 것은 0번째 스티커를 뜯으면 마지막 스티커를 뜯을 수 없고, 1번째 스티커를 뜯으면 마지막 스티커를 뜯을 수 있다는 것이다. 따라서 루프를 두번 돌려 값을 비교한 뒤 최댓값을 출력하면 된다. #include #include #include using namespace std; int dp[100001]; int solution(vector sticker) { int answer = 0; int N = sticker.si..

이 문제는 프로그래머스 level 3 문제이다. 이 문제는 입력이 2억이므로 O(n)으로도 약 2초가 걸린다. 따라서 배열을 사용한 방식으로는 불가능하다. now를 1로 하고, 입력으로 주어진 stations 를 활용해서 문제를 풀어야 한다. 이 생각을 하지 못하면 풀기 힘들 것 같다. #include #include using namespace std; int solution(int n, vector stations, int w) { int answer = 0; int now = 1; int stationIndex = 0; while (now = stations.size() || now < stations[stationIndex] - w) { answer++; now = now + 2 * w + 1; ..

이 문제는 프로그래머스 level 3 문제이다. 나는 처음에 이 문제를 이분 탐색을 통해서 풀려고 했다. 그래서 upper_bound를 이용한 뒤 erase를 하는 방식으로 구현했는데, 이런 식으로는 답은 나오나 시간 초과가 떴다. 내가 생각했을 때에는 vector 내의 erase 함수가 내부적으로 O(n) 이 걸리기 때문에 입력이 100000까지 나오는 경우 O(n^2)은 불가능하기 때문이라고 생각했다. 그래서 다른 풀이를 보니 투 포인터를 이용해서 간단하게 풀 수 있었다. 요즘 문제를 풀다 보면 이분 탐색이 가능한 문제는 보통 투 포인터로도 풀린다는 연관성이 보인다. 물론 입력이 O(n) 으로도 안될 정도로 큰 문제는 이분 탐색밖에 안되겠지만, O(n) 으로도 가능한 입력은 투 포인터도 사용 가능하다..

이 문제는 SQL 고득점 kit에서 join 카테고리에 있는 level 4 문제이다. 어려운 SQL 문제를 풀면서 느끼는 건 처음부터 요구사항을 모두 만족하는 쿼리를 짜려고 하면 문제가 더욱 어렵게 느껴진다는 것이다. 복잡한 join 문제를 풀때는 우선 하나의 테이블 당 요구 조건을 만족하는 단일 쿼리를 짜보고, 그 다음에는 두개의 테이블을 join하는 쿼리를 짜고, 그 다음의 요구사항을 맞추는 방식으로 풀면 결국 풀리게 된다. 이 문제를 처음 제출할 때에는 틀렸습니다가 나왔는데, 아무리 생각해도 논리 구조가 맞아서 혹시 날짜 범위에 문제가 있나 싶어 수정하니 바로 정답이 나왔다. 처음에는 start_date와 end_date가 11월 1일과 11월 30일 사이인 걸 not in 안의 서브쿼리로 넣었는데..