재원블로그 재원블로그

이 문제는 우선순위 큐(힙)를 이용해서 푸는 문제이다. 로직은 어렵지 않게 구현했지만, 계속 오류가 발생했다. 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..

이 문제는 시뮬레이션 문제이다. 시뮬레이션 문제 특성상 구현이 매우 복잡하지만 일단 구현하면 문제는 풀린다. 문제를 제대로 읽지 않아서 이동 시 범위를 넘어갔을 때 다시 순환형으로 돌아온다는 사실을 모르고 구현했다가 다시 풀었다. 모듈러 연산을 활용하여 연산 횟수를 줄이기 위해서는 인덱스가 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..

이 문제는 bfs 를 이용해서 푸는 문제이다. 이 문제에서 핵심은 섬이 꼭 육지로만 이루어져 있지 않을 수 있다는 것이다. 겉면이 육지로 둘러싸이고 내부는 바다일 수 있는 것이다. 따라서 외곽을 찾아서 bfs 를 돌릴 때 내가 출발한 섬의 번호와 같은 육지에 도착하면 실패하도록 구현해야 한다. 두번째로 bfs2 에서 while 문 내부에서 리턴하지 못하고 모두 끝나고 리턴할 때의 리턴값을 잘 설정해야 한다. 나는 처음에 아무 생각 없이 -1로 놨었는데, 그렇게 하면 최소를 구하는 문제에서 -1이 정답으로 나오는 케이스가 발생할 수 있다. 그러므로 최소를 구하는 문제에서는 리턴값을 가장 크게, 최대를 구하는 문제에서는 리턴값을 가장 작게 설정해줘야 한다. #include #include #include #..

이 문제는 bfs 를 사용하는 문제이다. 처음에는 이 문제에서 DSLR 연산의 리턴값을 string을 이용해서 구현했으나, 그렇게 하면 시간 초과가 발생하였다. 그래서 정수를 리턴하도록 하여 최대한 연산의 수를 줄였고, 정답을 받을 수 있었다. #include #include #include #include #include using namespace std; int operD(int temp) { temp *= 2; temp %= 10000; return temp; } int operS(int temp) { if (temp == 0) { temp = 9999; } else { temp--; } return temp; } int operL(int temp) { int result = (temp % 100..