본문 바로가기

분류 전체보기

 (83 개)
[JAVA] 백준 1260번: DFS와 BFS 문제정점 개수, 간선 개수, 탐색을 시작할 정점의 번호가 주어질 때, DFS로 탐색한 순서와 BFS로 탐색한 순서를 출력하는 문제. 아이디어2차원 배열을 이용해 그래프를 구현한다.graph[n][n] 으로 구현한다.graph[n1][n2] = true : n1과 n2가 연결되어 있다.입력 받는 M개의 간선을 통해 노드끼리 양방향으로 연결한다.배열은 0부터 시작하므로, 인덱스 처리를 쉽게 하기 위해 입력받은 수에서 1씩 뺀 요소에 갱신한다. 1, 2 입력graph[0][1] = truegraph[1][0] = true이후 DFS, BFS 탐색을 수행한다.중요한 점은 DFS를 수행한 후 BFS를 수행하기 전에 반드시 visited boolean 배열이 초기화 되어야 한다는 점이다.또 잊지 말아야 할 점은, ..
[JAVA] 백준 1012번: 유기농 배추 문제2차원 배열로 0이 빈 곳, 1이 배추가 있는 곳으로 주어지고, 배추를 해충으로부터 보호하려고 한다.배추가 심어진 곳에 배추흰지렁이를 배치해 해충을 예방할 수 있으며, 상하좌우로 연결된 배추 모두를 보호할 수 있다.이때, 필요한 배추흰지렁이의 최소 마리 수를 구하는 문제. 아이디어그래프 탐색을 통해 연결된 노드 가지의 수를 구한다.DFS 혹은 BFS 탐색을 시도해, 연결된 노드 가지 수를 카운트한다.2차원의 visited 배열을 선언하기 싫어서, 배추 부분을 발견함과 동시에 0(false)으로 바꿔 다시는 탐색하지 못하게 했다. 풀이(DFS)import java.io.*;import java.util.*;public class Main { static int N, M, K; // 상하좌우 ..
[JAVA] 백준 17626번: Four Squares 문제자연수 n이 주어지고 제곱수 들의 합으로 n을 표현할 때, 필요한 제곱수 개수의 최솟값을 구하는 문제. 아이디어처음에는 브루트포스로 풀어야 겠다고 다짐하고 모든 제곱수를 저장한 후, 가장 n에 근사한 값 부터 나누기 및 빼기를 통해 최솟값을 찾았다.50%까진 통과했지만, 그 이후로 계속 실패해서 결국 다른 사람의 풀이를 읽었다.내가 구현했던 브루트포스 풀이는 잘못된 풀이로, 모든 조합을 고려하지 못했기 때문에 틀렸다는 결론이 났다(근데 반례는 못찾았다...)DP의 bottom-up 방식으로 접근한다.첫 번째 for 문에서 1부터 n까지 올라가며 각 제곱수를 구하고,두 번째 for 문에서 첫 번째 for 문의 i * i 를 사용해 dp 배열을 업데이트한다.이 때, dp[j] 는 현재 제곱수 i * i ..
[JAVA] 백준 11727번: 2xn 타일링 2 문제2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제. 아이디어각 경우의 수를 나열해보면 다음과 같다.1, 3, 5, 11, 21, ...이 규칙을 분석해보면 다음의 점화식을 얻을 수 있다.$$a_{n} = a_{n-1} + 2a_{n-2}$$ 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] arr = new int[1001]; int..
[JAVA] 백준 11726번: 2xn 타일링 문제2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 출력하는 문제. 아이디어각 사이즈의 직사각형을 채울 수 있는 방법의 수 간 규칙성을 찾는다.방법의 수는 각각 1, 2, 3, 5, ... 순으로 증가한다.이를 점화식으로 표현하면 다음과 같다.$$a_{n} = a_{n-1} + a_{n-2}$$ 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] arr = new..
[JAVA] 백준 11659번: 구간 합 구하기 4 문제수 N개가 주어졌을 때, i 번째 수부터 j 번째 수까지 합을 구하는 문제. 아이디어i와 j를 입력 받을 때마다 합을 계산하면 시간초과가 나므로, 미리 1차원 배열에 누적 합을 구해놓고 각 요소의 차를 이용해 해답을 구한다.1, 2, 3, 4, 5, 6이 입력되고, 1과 3이 입력된다고 가정하자.누적합을 저장할 1차원 배열을 선언한다.인덱스 1의 위치에 1+2의 결과값을 저장한다.인덱스 2의 위치에 1+2+3의 결과값을 저장한다....인덱스 5의 위치에 1+2+3+4+5+6의 결과값을 저장한다.이후 1과 3이 입력되면, 인덱스 2(3-1)에 위치한 값에서(1+2+3) 인덱스 -1(1-2)에 위치한 값을(null) 빼주면 원하던 값을 출력할 수 있다.이를 식으로 바꾸면 다음과 같다.$$answer = ..
[JAVA] 백준 9461번: 파도반 수열 문제파도반 수열이 주어질 때, N번째 삼각형의 변의 길이를 구하는 문제. 아이디어문제에 답이 나와있다.변의 길이는 각각 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 인데, 이를 자세히 보면 아래 규칙을 찾을 수 있다.$$a_{n} = a_{n-2} + a_{n-3}$$이 규칙을 배열을 이용해 그대로 구현한다. 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder ..
[JAVA] 백준 9375번: 패션왕 신해빈 문제주어지는 옷들을 조합해 입고 다니되, 같은 옷의 조합을 입으면 안된다는 조건이 붙을 때, 옷을 조합해 입고다닐 수 있는 날의 최댓값을 구하는 문제. 아이디어선글라스 3개, 바지 2벌의 경우를 생각해보자선글라스만 골랐을 때, 각 종류의 선글라스 3개를 각각 고르는 경우 3가지 + 선글라스를 고르지 않는 경우 1가지, 총 4가지의 경우의 수가 나온다.바지만 골랐을 때, 각 종류의 바지 2벌을 각각 고르는 경우 2가지 + 바지를 고르지 않는 경우 1가지, 총 3가지의 경우의 수가 나온다.따라서, 선글라스와 바지를 조합하는 경우는 4 x 3, 여기에 둘 다 고르지 않는 경우는 존재하지 않아야 하므로 - 1가지를 해 총 11가지의 경우의 수가 존재하게 된다.즉, "각 타입의 종류 수 + 1" 한 값을 각각 모..

티스토리툴바