설모의 기록

이 문제는 상, 하, 좌, 우로 1칸씩 이동하거나 말처럼 입력받은 K번만큼만 (상, 하) (좌, 우)로 두칸 또는 한칸씩 움직여 오른쪽 아래칸으로 이동하는데에 걸리는 시간을 구하는 문제입니다. 처음엔 DFS로 푸는게 더 간단할거라 생각해서 DFS로 풀다가 시간초과를 해결하지 못해 BFS로 방법을 바꿔 풀었습니다. 이번에는 계속 틀리길래 다른 분들의 코드를 검색해봤지만 로직이 뭐가 다른건지를 이해를 못했습니다T^T 2일동안 답답해하다 오류를 발견했는데, 저는 길을 찾지 못할 때 지금까지 걸린 시간을 출력해주고 있었습니다. -1을 반환해주는 코드로 바꾸니 맞았습니다. 너무 허탈하네요.. 기본 BFS에서 사용하는 dx, dy 배열을 12 길이의 배열로 바꾸고 for문에서 인덱스가 4보다 작을 때와 클 때를 나..

이 문제는 DFS와 Backtracking을 이용해 중복되지 않은 알파벳은 방문하지 않는 조건으로 (0, 0) 에서 갈 수 있는 경로의 최대거리를 구하는 문제입니다. 저는 char 자료형 특징을 이용할 생각을 못하고 지금까지 지나온 알파벳을 ArrayList에 저장해 다음 경로로 갈 때마다 체크해주는 코드로 짜봤는데요. 시간이 8000ms가 넘길래 너무 놀라서 검색해봤는데 char 자료형을 이용하면 훨씬 수월하게 탐색할 수 있는 방법이 있었습니다. 아래에 비효율적으로 짠 코드와 최적화한 코드를 차례로 첨부하겠습니다. 우선 대문자 알파벳이기 때문에 'A' ~ 'Z' 까지가 범위가 되며 int형으로 바꾸면 65 ~ 90이 됩니다. 그래서 저는 check 배열의 인덱스를 (입력 알파벳 - 'A' ) 이라 생각..

이 문제는 전형적인 bfs, dfs 문제로 배열을 돌면서 값이 1인 그룹이 몇개가 있는지를 출력하는 문제입니다. 아래의 코드는 bfs로 푼 문제입니다. 그룹의 개수가 배추흰지렁이의 최소한의 마리수입니다.

이 문제는 1 / m 만큼씩 1을 나눠 구간을 만들고 그 다음으로 주어지는 숫자들을 그 구간별로 나눈 후, 구간별로 몇 개의 숫자가 존재하는지 출력하는 문제입니다. 쉽다고 생각하고 몇번이나 코드를 제출했지만 계속 '틀렸습니다' 만 반복해서 대체 왜 그러는건가 double 에 대해 찾아봤습니다. 알게된 내용은 다음과 같습니다.컴퓨터가 숫자를 처리할 때에는 1.xxxxx(지수부) * 2^(가수부) 로 인식하기 때문에 2의 배수가 아니거나 소수인 값은 내가 저장한 값이 그대로 저장되지 않는 경우가 있다고 합니다. 이 상황에서 오차가 발생하기 때문에 그 오차를 해결하는 과정을 확인하기 위한 문제였다고 볼 수 있습니다. 예를 들어, double a = 0.1; 이러한 코드를 작성하였다 해도 a에는 0.1 이 아니..

이 문제는 주어진 숫자들 중 중복되지 않고 순서에 관계없이 6개의 숫자를 골라 오름차순으로 정렬해 출력하는 문제입니다. 재귀함수를 이용해 모든 경우를 고른 후 이전에 뽑았던 숫자조합인지를 확인해도 되지만, 굳이 전에 뽑은 숫자 조합을 다시 뽑지 않도록 한번의 반복문과 calculate 함수 내에서 백트랙킹을 이용했습니다.

이 문제는 그래프에서 한 정점에서 다른 정점으로 가는 최단경로의 합이 가장 작은 정점을 구하는 문제입니다. dfs나 bfs로 해도 풀리겠지만, 처음 알게 된 폴로이드 와샬 알고리즘을 적용해보기 위해 저는 이 알고리즘을 사용했습니다. 폴로이드 와샬 알고리즘 정점 사이의 최단경로를 구할 때에 자주 사용하는 것이 다익스트라 알고리즘인데요. 다익스트라 알고리즘의 단점은 정점 사이의 가중치가 음수일 때 사용할 수 없다는 점입니다. 이에 반해 폴로이드 와샬 알고리즘은 가중치가 음수여도 사용이 가능합니다. 이름이 어렵게 생겨서 뭐지? 했는데 알고 보니 3중 포문을 이용해 모든 정점과 정점사이의 거리를 구하는 알고리즘이었습니다. 먼저 kebin이라는 int[][] 배열을 초기화하고, 주어진 정점들의 관게를 입력합니다...

이 문제는 4개짜리 테트로미노 블럭을 주어진 이차원 배열에 놨을 때 배열의 값의 합이 최대가 되는 값을 구하는 문제입니다. 폴리오미노의 조건은 아래와 같습니다.정사각형은 서로 겹치면 안된다.도형은 모두 연결되어 있어야 한다.정사각형의 꼭지점끼리 연결되어 있어야 한다. 즉, 변과 꼭지점이 맞닿아 있으면 안된다.이 때, 정사각형 4개를 이어붙인 폴리오미노를 테트로미노라 하고 아래의 그림과 같이 5가지 종류입니다. 저도 처음에는 '5개를 어떻게 회전하지.. 4*4배열을 생성해서 그 배열을 회전해야하나..' 하는 함정에 빠졌습니다. 이것을 어떻게 해결하냐가 관건입니다. 이 문제는 dfs로 간단하게 풀리는 문제입니다. 'ㅜ' 블럭을 제외한 4개의 블럭은 한번에 그릴 수 있죠? 다시 말하면 dfs로 한번에 탐색할 ..

이 문제는 그냥 나눗셈만 하면 되는 간단한 문제였습니다. 다만 int 가 32bit 이기 때문에 각 시험장에 백만명씩 있고 총감독관과 부감독관이 감시할 수 있는 응시자 수가 1이라면 범위를 벗어나겠죠? 따라서 감독관 인원수를 담을 변수는 int 가 아닌 long으로 선언해야 합니다. 단위만 조심하면 정말 쉬운 문제입니다!

이 문제는 일별로 상담기간과 페이가 주어지고, 퇴사 날짜까지 벌 수 있는 최대 페이를 구하는 문제입니다. 이 문제는 간단한 DP 문제입니다. 저는 dp 배열에 그날까지 벌 수 있는 최대 페이를 입력해 dp[N] 을 출력했습니다.

이 문제는 벽 3개를 추가한 후 바이러스가 퍼졌을 때의 안전구역의 최대값을 구하는 문제입니다. 저는 재귀함수와 bfs를 이용했습니다. 제 규칙은 아래와 같습니다.재귀함수를 이용해 벽 3개 구하기초기 배열을 cloneMap에 복사하고 구한 3개의 벽도 추가bfs를 수행하며 바이러스를 퍼트린 후 안전영역 개수 구하기 위의 규칙을 토대로, 먼저 N, M, map 세개를 입력받고 나중에 안전구역 영역을 셀 때 또 이중반복문을 수행하지 않기 위해 안전구역갯수(safeAreaCount)를 저장했습니다. 그리고 N*M 만큼 for문을 반복해 이중for문을 피했습니다. 일단 벽 하나를 세운 뒤 recursive 함수를 호출해 벽 2개를 더 세우고 안전구역 영역을 구합니다. private static void recur..