woody

- 문제소개 - 해결과정 문제 풀이의 핵심은 컴포넌트 내 컴퓨터의 수와 컴퓨터들을 연결하고 있는 회선의 수를 동시에 알고있어야 한다는 점이다. 아래와 같은 방식으로 해결했다. 연결된 컴퓨터의 그룹과 해당 그룹의 회선의 수에 대한 정보를 담을 수 있는 내부 클래스를 생성한다. 양방향 연결이므로 단순 인접 리스트를 생성하고 BFS를 통해 연결되어 있는 컴퓨터 그룹을 찾아낸다. 컴퓨터 그룹을 찾아낸다면 양방향 연결이므로 인접 리스트를 이용해 회선의 수를 찾아낼 수 있다. 회선의 수 = 각 컴퓨터 번호를 인덱스로 하는 인접 리스트에서 모든 요소의 개수를 더한 값 / 2 아래와 같은 상황을 보자. 회선의 수는 5개다. 식으로 계산해보자. 인접리스트에서 각 인덱스의 요소의 개수를 더하고 2로 나누면 2 + 3 + ..

- 문제소개 - 해결과정 문제풀이 흐름은 아래와 같다. 인접 리스트를 만든다. 최초 모든 섬이 독립적인 연합을 이루고 있는 형태로 연합 리스트를 생성한다. 이후 인접 리스트를 순서대로 순회하며 아래의 과정을 거친다. 양방향 연결되어 있는지 확인 연결되어 있다면 비교 대상 섬 번호를 현재 연합에 더해준다. 2번 과정을 통해 독립적이었던 두 개의 연합이 합쳐졌으므로 기존 연합 리스트의 비교 대상 인덱스 자리의 요소를 삭제한다. 조건으로는 비교 대상 번호 인덱스에 값이 있는 경우에만 현재 연합에 합류할 수 있도록 설정하면 된다. 위 과정을 한번 끝내면 다시 새롭게 합류한 섬 번호를 기준으로 재귀 호출을 하게된다. 더 이상 재귀 호출을 할 수 없다면 해당 연합은 완성한 것 --> 다음 인접 리스트로 넘어간다. ..

- 문제소개 - 해결과정 모든 조각의 가격을 1로 설정했기 때문에, 단위 조각당 포만감이 가장 높은 순서로 리스트에 정렬시켰다. 이후 아래와 같은 순서로 구입하면 된다. 인덱스가 작은 순서로 과일을 꺼내온다. 현재 가지고 있는 돈보다 과일의 가격이 싸거나 같다면 통으로 구매한다. 현재 가지고 있는 돈보다 과일의 가격이 비싸다면 조각으로 구매할 것이다. 2번, 3번과정을 거치면서 남은 금액이 0원이 된다면 break. 지금까지 누적해서 계산된 포만감을 출력하면 된다. - 솔루션 import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws Exception { BufferedReader br = ..

- 문제설명 - 해결과정 입력으로 주어진 간선 정보를 이용해 인접 리스트를 만든다. 최초 시작 노드를 파라미터로 dfs를 호출한다. 시작 노드에 연결되어 있는 노드 중 가장 번호가 작은 노드를 찾는다. 해당 노드를 시작으로 다시 dfs를 호출한다. 가장 번호가 작은 노드를 찾으면 finalNode값을 갱신해줬기 때문에, 마지막 dfs를 마치고나면 자연스럽게 최종 도착지 노드를 알 수 있다. 그대로 출력하면 된다. - 솔루션 import java.util.*; import java.io.*; class Main { private static boolean[] visited; private static List[] node; private static int finalNode = 0; private stat..

- 문제설명 - 해결과정 어제 풀었던 발전기 문제에서 심화된 문제이다. 아래와 같은 흐름으로 문제를 풀이했다. BFS를 돌면서 현재 그룹에서 이어진 집의 개수가 몇개인지 확인한다. 최종 이어진 개수가 K개 이상이라면 "단지"라고 판단해 리스트에 해당 번호를 추가한다. 배열을 전부 탐색해 가능한 모든 단지가 리스트에 담겼다면 요소를 하나씩 빼서 해시맵에 같은 유형의 단지가 몇 개씩 있는지 옮긴다. 완성된 해시맵을 순회하며 가장 단지 수가 많은 유형을 찾아 반환한다. - 솔루션 import java.io.*; import java.util.*; class Main { private static int[][] town; private static boolean[][] visited; private static..

- 문제설명 - 해결과정 입력값을 받아 배열을 초기화 시킨 후 모든 배열을 탐색하면서 BFS를 호출한다. BFS가 중간에 끊긴다면 상하좌우로 이어진 모든 집을 탐색한 것이다. 이때 count를 증가시키고, 아직 방문하지 않은 나머지 집에 대해서 BFS를 호출하면 된다. 결론적으로 모든 배열을 돌고나면 몇번의 BFS가 호출되었는지 count값으로 확인할 수 있다. - 솔루션 import java.io.*; import java.util.*; class Main { private static int[][] town; private static boolean[][] visited; private static int[] dx = {-1, 1, 0, 0}; private static int[] dy = {0, 0..

- 문제설명 - 해결과정 문제의 조건에서 두 아이템의 이름이 A, B일때 B가 회복시켜주는 양이 A보다 더 크다고 나와있다. 이를 이용해 문제를 풀어보자. 아이템 사용량이 가장 최소가 되는 상황부터 아이템 사용량이 가장 최대가 되는 상황으로 올라가면서 각 단계별로 피로도를 0으로 만들 수 있는지 판단하면 된다. --> 가장 먼저 피로도를 0으로 만들 수 있는 상황을 만난다면 해당 경우가 아이템을 가장 적게 사용해 피로도를 0으로 만드는 것이다. 아이템 사용량이 가장 최소가 되는 상황이란 누적 피로도를 아이템 B의 회복량으로 나눈 몫만큼 아이템 B를 사용하고 그 나머지는 아이템 A로 피로를 회복하는 상황이다. 이 상황부터 아이템 B의 사용량을 하나 줄이고, 다시 나머지를 아이템 A로 채워 피로도를 0으로 ..

- 문제설명 - 해결과정 문제를 해결하는데 고려해야하는 포인트는 아래와 같다. 한 칸씩 나아갈 때 방문처리를 하며 나아가야한다. 이후 방문처리가 되어있는 칸을 방문할 시 게임종료. 각 칸에 써있는 count, command 정보를 알 수 있어야 한다. 위의 포인트들을 처리하기 위해서 Node라는 static class를 만들었다. 해당 클래스에는 아래와 같은 멤버변수를 담아놨고, 생성자 및 getter, setter를 만들었다. 방문여부를 알 수 있는 boolean visited; 진행방향을 알 수 있는 char command; 진행횟수를 알 수 있는 int count 두 명의 플레이어 각각에 대한 게임판이 필요하다. 따라서 배열 초기화 단계에서 동일한 두 개의 배열을 만들어준다. --> 하나의 게임판만..

- 문제설명 - 해결과정 최초 주어지는 배열만 가지고 문제를 해결할 수 없었다. 최초 배열의 정보를 가지고 누적해서 스코어를 계산해 나가야하기 때문에, 최초 배열과 동일한 사이즈의 점수판이 필요했다. 조금 다른 관점으로, 하나의 배열판만 쓰지만 타입을 직접만든 static class로 지정해줬다. 해당 클래스에는 1. init 이라는 최초 배열 정보 2. score 라는 누적 점수 정보 이렇게 두 가지가 포함되어 있는 클래스이다. 문제풀이 흐름은 아래와 같다. 입력으로 주어지는 정보를 배열로 받는다. 이때는 최초 배열이므로 생성자 주입을 통해 멤버변수 init에 정보를 담는다. 이제 폭탄을 떨구며 점수를 획득하자. 상황별로 몇 점을 주냐만 다르지 점수를 주는 방식은 getScore() 메소드로 기존 점수..

- 문제설명 - 해결과정 단순히 현재 남아있는 통증 수치를 넘지 않는 선에서 가장 효과가 큰 아이템을 사용하면 된다. 추가적인 복잡한 조건이 없었기에 그리디한 솔루션으로 풀리는 문제였다. - 솔루션 import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br...