개발로그

문제 N X N 크기의 땅이 있고, 땅은 1 X 1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 아래와 같이 진행되고, 더 이상 인구 이동이 없을 때까지 지속된다. 1. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 두 나라가 공유하는 국경선은 오늘 하루 동안 연다. 2. 위의 조건에 의해 열어야 하는 국경선이 모두 열렸다면 인구 이동을 시작한다. 3. 국경선이 열려 있어 인접한 칸만을 이용해 이동할 수 있으면 그 나라를 오늘 하루 동안 연합이라고 한다. 4. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수)..

코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 풀이 먼저, 해당 문제는 시키는대로 잘 따라가면 된다. 순서대로 진행하는데, 균형잡힌 문자열과 올바른 문자열에 대해서 어떻게 판단할 것인지 생각해야한다. 균형 잡힌 문자열은 개수가 같은 것이기 때문에 '(' 와 ')'의 갯수가 동일한 경우의 index를 반환한다. 올바른 문자열은 '('와 ')'의 균형이 맞으면서 순서도 맞아야 한다. ')'이 먼저 나오는 경우 안된다. 나머지 부분은 문제에 정의된 부분대로 구현하면 되었다. class Solution { publi..

풀이 연산자를 숫자 사이에 끼워넣는데, 순서 상관 없이 끼워넣어 모든 경우를 구하는 것과 같다. dfs로 구현했다. dfs를 구현할 때, 파라미터로 index와 지금까지 연산한 결과 now를 전달한다. dfs의 재귀호출의 깊이가 깊어질수록 number의 index는 n에 가까워지고 그때까지 연산의 결과를 유지해야 했다. index가 n에 도달하면 최대 최소 비교하도록 했다. 그리고 연산자의 경우 d 라는 배열로 관리했는데, 오히려 헷갈리기 때문에 깃헙의 풀이와 같이 각각의 변수로 관리하는 것이 코드를 보는데 더 편하다. 소스코드 import java.util.*; class Main { public static int n; public static int[] d = new int[4]; // 연산자 +,..

풀이 먼저, 벽이 3개인 경우를 찾아 선생님 위치에서 상하좌우를 확인하도록 생각했다. 1. 벽 설치 벽이 3개가 아닌 경우 벽을 설치하도록 dfs로 구현했다. 벽이 3개가 될 경우 그래프를 탐색하면서 선생님이 위치한 좌표를 찾아 체크한다. 선생님 수 만큼 체크가 되어야 한다. (모든 선생님이 학생을 못 봐야 함.) 여기서 선생님 한명만 안보여도 통과하게 로직을 짜서 문제가 되었다. public static void dfs(int cnt) { if (cnt == 3) { // 벽이 3개가 설치된 경우 int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (graph[i][j] == 'T') { // 선생님 위치에서 학생들..

풀이 바이러스는 1번부터 순차적으로 번져간다. 순서대로 꺼내서 번지는 것을 생각하면 큐를 사용하는 것이 좋았음. 바이러스 정보를 담은 객체 (좌표와 어떤 바이러스인지) 를 1번부터 순서대로 큐에 나열한다. 그리고 꺼낼 때마다 전염 시킨다. (전염할 수 있는 조건에 맞게) (중심에 있는 바이러스는 이미 주변으로 퍼졌기 때문에 더 퍼질 수 없으니 다시 넣을 필요 없다.) 종료 조건에서 시간에 따른 종료 조건에 맞게 종료한다. 시간은 1번부터 k번까지 다 전염시킨 후에 더해진다. 큐에서 꺼내올 값의 index가 다시 1이 된 경우 시간을 증가시킨다. (peek()으로 확인하는데 큐가 NULL이면 NPE 발생하므로 먼저 비어있는지 확인하고 함) import java.util.*; class Virus imple..

최장 증가 부분 수열 전체 수열에서 만들 수 있는 부분 수열 중에 오름차순을 유지하며, 그 길이가 최대 길이인 부분 수열을 말한다. (정렬된 수열의 부분 수열을 말하는 것이 아니라, 주어진 수열의 순서에서 몇 개 원소를 제거하여 오름차순을 만든 부분 수열, 그 중에 최대 길이) 최장 증가 부분 수열의 길이 구하기 최장 증가 부분 수열의 길이를 구할 때, DP(동적 프로그래밍)을 통해 구현할 수 있다. DP 테이블을 구성하고, DP 테이블에는 각 인덱스까지 최장 증가 부분 수열의 길이를 저장한다. 1. DP 테이블은 각각 1로 초기화 한다. 각각 길이 1의 부분수열로 생각했을 때, 해당 인덱스에서 최장 길이는 1이다. 2. 부분 수열의 범위를 1씩 증가시키면서 해당 인덱스에서 최장 길이를 업데이트한다. 부..

풀이 벽을 세운 개수가 3개가 될 때마다 임시 맵에 바이러스가 퍼진 결과, 그리고 안전한 공간을 계산하도록 한다. 안전한 공간의 수는 최대값으로 갱신한다. 바이러스가 퍼지는 공간은 DFS로 면적을 포함해가면 된다. public static void virus(int x, int y) { for (int i = 0; i 0,0 0,1 n,m -> 0,0 0,2 0,3 -> ... 이렇게 모든 경우를 확인할 수 있다. 그 때 벽의 개수가 3개일 때마다 바이러스의 퍼짐 정도와 안전한 공간을 계산하면 된다. public static void dfs(int cnt) { // 벽 3개 건설된 경우 i..

문제 어떤 나라에 1~N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이때 X도시에서 출발하여 도달할 수 있는 도시 중 최단거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램 작성하시오. X 도시에서 X 도시까지의 거리는 0으로 가정한다. 입력 조건 첫째 줄에 N, M, K, X가 주어진다. 둘째 줄부터 A도시에서 B도시로 이동하는 단방향 도로 정보가 주어진다. 출력 조건 최단거리 K로 도달 할 수 있는 모든 도시를 오름차순으로 출력. 하나도 없다면 -1 출력 풀이 먼저 도로에 대한 정보가 주어지는 것을 인접리스트 방식으로 그래프화 시킨다. 도시별 최단거리를 저장할 배열을 선언한다. 처음 시작 도시 X의 거리를 0으로 지정하고, 나머지는 -1로 초기화 한다. 자료구조 ..

조합을 이용한 문제 자바에서 조합을 해결하는 방식 잘 이해할 것. 계속 공부해야함. [Algorithm] JAVA에서 조합 (Combination) 참고 자료 [Java] 조합 Combination 조합 조합이란 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우를 말한다. (위키백과 - 수학에서 조합은 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 youngssse.tistory.com import java.util.*; class Combination { private int n; // 총 치킨 집 수 private int r; // 선택하는 치킨 집 수 private int[] now; // 현재 조합 (인덱스로 저장) private ArrayList result; // 최종 조합 pu..

1. 먼저 주어진 표를 행렬로 표현하기 편하도록 아래의 그림과 같이 생각한다. y = 0 이 바닥이 되고, x = 0이 왼쪽 끝이 된다. 2. 없는 것을 삭제하거나 설치된 곳에 설치하지 않는다고 하니 검증하는 단계가 없어도 된다. 삭제와 설치에 대해서 실행하고 가능한지 판단하고 안되면 복구한다. 3. 가능한지 점검할 때는 주어진 조건에 따라 조건을 맞춰 검증한다. public boolean possible(ArrayList answer) { for (int i = 0; i < answer.size(); i++) { int x = answer.get(i).get(0); int y = answer.get(i).get(1); int stuff = answer.get(i).get(2); if (stuff == ..