재원블로그 재원블로그

복잡한 쿼리 문제를 풀 때에는 요구사항을 나눠서 하나씩 해결하는게 효과적이라는 걸 느꼈다. 그 중에서 가장 도움이 되었던 건 쿼리의 실제 실행 순서를 알면 쿼리를 짜는게 쉬워진다는 것이었다. MySQL 기준으로 쿼리를 작성할 때에는 1. SELECT 2. FROM 3. WHERE 4. GROUP BY 5. HAVING 6. ORDER BY 의 순서로 작성하게 된다. 하지만 실제 쿼리의 실행 순서는 1. FROM 2. WHERE 3. GROUP BY 4. HAVING 5. SELECT 6. ORDER BY 순으로 실행이 된다. 이 사실을 알면 group by에서 sum, avg와 같은 함수가 어떻게 select 문에 컬럼으로 존재할 수 있는지가 해결된다. 쓴걸로 보면 select가 group by 보다 먼..

이 문제는 bfs로 푸는 문제이다. 처음에 이 문제를 풀때 순간 플로이드 워셜이 떠올라서 그렇게 풀어봤는데 애초에 값이 제대로 안 나왔다. 그래서 bfs로 다시 방향을 고치고 풀었는데, 이번에는 시간 초과가 났다. 처음에 bfs를 짤때는 start와 end를 두어 모든 짝에 대한 USADO를 저장했는데, 이런 식으로는 5000 * 5000 * 5000의 연산이 필요하게 되어 시간 초과가 난다. 다시 생각해보니 그럴 필요가 전혀 없었고, 시작점에서 출발하여 정점들을 방문하면서 USADO를 측정하고, 그 값이 k보다 크거나 같으면 카운트하면 되는 문제였다. 문제를 풀 때 알고리즘을 안 보고 푸는 연습을 꼭 해야할 것 같다. 실제 코딩 테스트 시에는 이 문제가 어떤 알고리즘의 문제인지 알려주지 않기 때문이다...

이 문제는 우선순위 큐(힙)를 이용해서 푸는 문제이다. 로직은 어렵지 않게 구현했지만, 계속 오류가 발생했다. input 큐를 돌면서 매번 현재 시간보다 넘어간 job들을 모두 푸시하는 부분이 문제가 없다고 판단하고 다른 곳을 고쳤으나 문제가 해결되지 않았다. 그래서 입력으로 주어진 배열을 정렬하고 제출하니 정답이 나왔다. 사실 내가 생각한 대로라면 입력 배열의 정렬 유무와 상관없이 동작해야 한다. 하지만 tempInput.first b.second; } }; int solution(vector jobs) { int answer = 0; sort(jobs.begin(), jobs.end()); queue input; for (vector job : jobs) { input.push({job[0], job..

이 문제는 구현, 시뮬레이션 문제이다. 구현이 매우 복잡하지만 순서에 따라 함수를 나누고, 세부 내용을 구현하는 방식으로 코딩하면 어렵지 않게 풀 수 있다. 한가지 유의할 점은 파란 칸이나 보드를 벗어날 때 stack 에서 뺐던 말들을 다시 제자리에 집어넣는 로직이 들어가야 한다는 것이다. 구현하면서 한가지 아쉬웠던 것은 moveHorse 함수 안에서 switch 문을 통해 말을 이동시키는 부분의 코드가 너무 길어 수정할 때 어려움을 겪었다는 것이다. 이렇게 길어지거나 복잡한 코드는 함수를 더 나눠서 해야 한다는 생각이 들었다. #include #include #include #include #include using namespace std; #define WHITE 0 #define RED 1 #de..

이 문제는 datediff 를 사용하면 쉽게 풀리는 간단한 문제지만, 한 가지 유의할 점이 있다. 예를 들어 6월 1일부터 6월 30일까지의 일수 차이를 구하면 29일이 맞지만, 이 문제에서는 대여 시작 날이 포함되도록 예시를 보여주고 있다. 즉, datediff 를 사용하고 1을 더해야 정답이 나온다. SELECT HISTORY_ID, CAR_ID, DATE_FORMAT(START_DATE, '%Y-%m-%d') AS START_DATE, DATE_FORMAT(END_DATE, '%Y-%m-%d') AS END_DATE, CASE WHEN DATEDIFF(END_DATE, START_DATE) + 1 >= 30 THEN '장기 대여' ELSE '단기 대여' END AS RENT_TYPE FROM CAR..

이 문제는 시뮬레이션 문제이다. 시뮬레이션 문제 특성상 구현이 매우 복잡하지만 일단 구현하면 문제는 풀린다. 문제를 제대로 읽지 않아서 이동 시 범위를 넘어갔을 때 다시 순환형으로 돌아온다는 사실을 모르고 구현했다가 다시 풀었다. 모듈러 연산을 활용하여 연산 횟수를 줄이기 위해서는 인덱스가 1로 시작하면 매우 복잡하다. 따라서 입력을 받을 때 r과 c를 1씩 빼서 0부터 시작하도록 수정하였고, matrix의 한 요소를 벡터로 하여 항상 push 할 수 있도록 하여 구현을 그나마 간단하게 하였다. 어려운 구현 문제는 꼭 함수를 분리하여 추상화를 먼저 하고 순서를 짜놓은 뒤 세부 구현을 하는게 훨씬 간편하다. #include #include #include using namespace std; #define..

이 문제는 bfs 를 이용해서 푸는 문제이다. 처음에는 이 문제를 풀 때 보통 bfs 구현처럼 큐에 push 할 때 visited 를 수정했다. 그러나 이 문제는 그렇게 하면 굉장히 복잡해지고 정답을 맞추기 쉽지 않아진다. 이 문제는 visited 를 큐에서 pop 하자마자 체크하면 간단히 풀리는 문제였다. 또한 visited 를 int 로 하여 최단 거리를 계산하지만, 이 경우 여러 경로를 탐색해야 하므로 bool 로 선언해서 문제를 푸는게 훨씬 간단하다. 너무 정형화된 패턴으로 문제를 풀면 복잡해진다는 교훈을 얻었다. #include #include #include using namespace std; int n, k, answer = -1, cnt; bool visited[100001]; bool ..

이 문제는 강한 연결 요소 (SCC) 를 이용해서 풀 수 있는 문제이다. 사실 이 문제는 dfs 를 약간만 설정해서 사이클의 판단만 해주면 풀리는 문제이다. 그러나 강한 연결 요소를 통해 유향 그래프의 사이클 요소를 찾을 수 있다는 생각이 떠올라 SCC로 풀었다. 이 문제에서 중요한 건 입력으로 주어지는 간선은 outgoing edge가 단 하나라고 명시되어 있지만, transpose graph 에서는 outgoing edge 가 하나가 아니라는 것이다. 그 사실을 망각하고 풀어서 많은 시간을 쏟게 되었다. #include #include #include using namespace std; vector edges; vector transEdges; vector visited; vector tempScc..