재원블로그 재원블로그

이 문제는 스택, 문자열을 이용한 그리디로 풀었다. 처음에는 이 문제에 kmp 알고리즘을 적용해봤다. 일부 테스트 케이스는 맞췄으나, 나머지에서 시간 초과가 났다. 다른 방법을 찾을 수 없어 검색을 통해 그리디 알고리즘을 사용한다는 사실을 발견했다. 만약 "110" 을 제외한 나머지 부분에 0이 하나도 없다면, 앞에 "110" 들을 나란히 붙여주는 것이 가장 숫자가 작다. 0이 하나라도 있다면 마지막 0 뒤에 110을 채워 넣어야 그 뒤에 있는 1들이 뒤로 밀려나면서 숫자가 작아지게 된다. 이를 그대로 구현하면 시간 초과 없이 정답이 나온다. #include #include #include #include using namespace std; int findLastZero(string str) { int..

이 문제는 다익스트라 알고리즘을 이용해서 풀었다. 처음에는 출발지들에 대해 루프를 돌면서 산봉우리들에 대해 루프를 돌고, 해당 출발지, 산봉우리 쌍에 대해 다익스트라 알고리즘을 사용했다. 그러나 이 방법으로는 당연히 시간 초과가 난다. 다른 방법으로 처음 다익스트라 알고리즘을 시작할 때, 우선순위 큐에 모든 출발지를 넣고 각 노드가 SUMMIT을 만나면 종료하도록 구현하는 것이다. 이 방법을 사용하면 한 번의 다익스트라 호출로 산봉우리들로 가는 최단 거리를 알 수 있다. #include #include #include #include #include using namespace std; struct compare { bool operator() (pair& left, pair& right) { retur..

이 문제는 원형 탐색, 순열을 이용한 완전 탐색을 이용해서 문제를 풀었다. 이 문제에서 핵심은 시계, 반시계 방향으로 두 가지 탐색을 하는 것이 아닌, 시계 방향 하나로만 탐색해도 전체 가짓수를 셀수 있다는 것이다. 또한 dist가 큰 사람부터 사용하는 것이 더 적게 지우는데 유리하다는 것이다. 이 두가지를 이용해서 문제를 풀었으나, 13번 테스트 케이스만 시간 초과가 났다. 검색을 통해 순열을 이용해서 부분 배열에 대한 순서쌍을 모두 탐색하는 방식으로 문제를 푸는 것을 확인했다. 내가 이전에 풀었던 방식으로는 아마 중복된 경우를 같이 카운트해서 시간 초과가 났을 확률이 높다고 생각했다. Java에는 순열 표준 라이브러리가 없어서 아쉬웠다. 그래서 C++로 풀었다. #include #include #in..

이 문제는 dfs를 이용해서 풀었다. 이 문제에서 핵심은 visited를 설정할 때 3중 배열로 설정해야 한다는 것이다. 한번 방문한 노드도 재방문할 수 있는 dfs이기 때문에 양과 늑대의 수도 매개변수에 포함시키고, 이들을 합한 3개의 매개변수에 대한 visited로 방문 여부를 판단하는 것이 핵심이다. 이 문제에서 굉장히 애를 먹은 부분이 있는데, if - else if - else 부분에서 코드 오류를 겨우 찾아냈다. 처음에는 if와 else if 의 조건 하나에 모든 요구사항을 다 넣었다. 그런데 이렇게 되면 if와 else if에 맞지 않는 조건이 else로 가버린다. 원래의 흐름은 양이냐 늑대냐 빈 노드냐 이기 때문에 정답이 나오지 않게 된다. 몇 시간의 삽질 끝에 겨우 오류를 찾아내 문제를 ..

이 문제는 bfs를 이용해서 풀었다. 처음에는 재귀를 이용해서 풀었으나, 정답이 나오지 않았다. 로봇 구현까지는 문제 없었으나, 최솟값을 계산하는 과정에서 정답이 나오지 않았었다. 그래서 풀이를 참고했고, bfs를 이용해서 쉽게 풀 수 있었다. 요즘 자꾸 재귀로만 풀려고 하는 경향이 생겼는데, bfs를 잘 이용해야겠다. 결국 내가 아는 선에서 문제를 출제할 것이라는 생각을 가지고 문제에 임해야겠다. import java.util.*; class Solution { static final int RIGHT = 0; static final int UP = 1; static final int LEFT = 2; static final int DOWN = 3; static final int INF = 100000..

이 문제는 백트래킹을 이용해서 푸는 문제이다. 처음에는 이 문제를 풀 때 apeech 보다 1 많은 화살로 한번에 빼는 방식으로 풀었으나 오답이 나왔다. 그래서 검색을 통해 그냥 백트래킹을 이용하는 것이 구현도 직관적이고 풀이도 쉽다는 사실을 발견했다. 처음 풀었던 방식의 문제점은 화살이 남는 경우에 대해 로직이 모호하다는 것이다. 마지막까지 도달했을 때 남은 화살을 전부 0점에 꽂아넣는 방식으로 구현했으나 오답이었다. 그냥 백트래킹은 당연히 시간 초과가 나기 때문에, 여러 가지 장치를 해주면 시간 안에 풀 수 있다. 먼저 start 매개변수를 두어 순서가 뒤바뀐 똑같은 결과를 만들지 않도록 순서를 강제한다. 그 다음 apeech보다 1만 많으면 되므로, ryan이 이미 화살이 더 많은 경우에는 cont..

이 문제는 해시, 이분 탐색을 이용해서 풀었다. 처음에는 입력으로 주어지는 값들을 모은 Node라는 클래스를 만들고 점수로 오름차순 정렬한 뒤 점수로 한번 필터링하고, 조건에 맞는 것들을 순회하여 찾는 방식으로 구현했었다. 그러나 이 방법으로는 효율성을 통과할 수 없다. 이 문제에서 중요한 점은 언어, 직군, 경력, 소울푸드의 모든 경우의 수가 -를 포함해도 4 * 3 * 3 * 3 = 108개밖에 되지 않는 것을 파악하는 것이다. 따라서 그냥 쿼리에서 나올 수 있는 모든 조합에 대한 키에 대해 미리 저장해두고, info를 순회할 때에도 -를 주의하며 키 생성 후 집어넣고 쿼리에서 한번에 찾는 방식으로 구현하면 시간 내에 구현할 수 있다. import java.util.*; import java.io.*..

이 문제는 완전 탐색을 이용해서 풀었다. 격자가 3 x 3 인 틱택토를 하는 문제로, 격자의 크기가 작아 모든 경우의 수를 구한 뒤 비교하는 방식으로 풀었다. 한 가지 주의할 점은 play를 수행할 때 게임이 끝나는 경우에 왔다고 해서 return을 하면 모든 경우를 볼 수 없다. 따라서 continue로 다음 경우들을 체크해줘야 정답이 나온다. import java.util.*; class Solution { List snapshot = new ArrayList(); char[][] board = new char[3][3]; public int solution(String[] b) { init(); if (isSame(board, b)) { return 1; } play('O'); for (final ..