본문 바로가기

java53

[백준] DFS - 9466번 텀 프로젝트 (Java) 문제링크 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 접근한 방법 dfs 풀이방법 참고한 블로그 dfs문제를 풀 때 boolean 자료형으로 방문여부(visited 배열)만 체크했는데, 이 문제는 그 노드의 깊이의 탐색이 끝났는지(finished 배열)도 체크를 해야했다. dfs 메소드를 선언하여 파라미터를 노드번호로 받는다. 현재 노드를 방문 처리하고, 그 노드에 이어져있는 다음 번호 방문 여부를 체크한 후, 방문을 진행한다. 일단 탐색이 끝난 여부 처리하는 걸 무시하고 생각했을 때 노드와 이어져있는 모든 노.. 2021. 5. 19.
[백준] dfs - 1012번 유기농 배추 (Java) 문제링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 접근한 방법 dfs 풀이방법 이 문제는 DFS로 해결할 수 있다. 0인 값이 상, 하, 좌, 우로 연결되어 있는 노드를 묶어 묶음의 수를 세면된다. 1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 1이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다. 2. 방문한 지점 에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다. 3. 1~2번의 과정을 모든 노드에 반복하며 방문하.. 2021. 5. 16.
재귀 알고리즘 재귀란? : 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다. 예시) 팩토리얼 구하기 package chap05; import java.util.Scanner; // 팩토리얼을 재귀적으로 구현 class Factorial { // 양의 정수 n의 팩토리얼을 반환합니다. static int factorial(int n) { if (n > 0) return n * factorial(n - 1); else return 1; } public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); System.out.print("정수를 입력하세요.："); int x = stdIn.nextInt().. 2021. 5. 16.
[이.코.테] Chapter 05 DFS/BFS - 미로 탈출 (Java) 미로 탈출 문제 (교재 152p) 난이도 ●◐○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB 동빈이는 N x M 미로에 갇혀있다. 동빈이의 위치는 (1,1) 이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있으며 괴물을 피해 탈출해야한다. 이 때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. * 미로는 반드시 탈출할 수 있는 형태로 제시된다. * 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입출력 조건) 입력 조건 - 첫째 줄에 두 정수 N, M (4 ≤ N, M ≤ 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수 (0 혹은 1)로 미.. 2021. 5. 12.
[이.코.테] Chapter 05 DFS/BFS - 음료수 얼려먹기 (Java) 음료수 얼려먹기 문제 (교재 149p) 난이도 ●◐○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB 문제N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 입출력 조건) 입력 조건 - 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 ≤ N, M ≤ 1,000) - 두 .. 2021. 5. 10.
BFS BFS(Breadth First Search) : 너비 우선 탐색 : 가까운 노드부터 탐색하는 알고리즘 : 큐 자료구조를 이용 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 예시) 더보기 클릭 더보기 다음과 같은 그래프를 살펴보자. 탐색을 수행함에 있어 O(N)의 시간이 소요된다. 코딩 테스트에서는 보통 DFS보다는 BFS 구현이 조금 더 빠르게 동작한다. 예제 코드 - ja.. 2021. 5. 4.
[이.코.테] Chapter 04 구현 - 게임 개발 (Java) 게임 개발 문제 (교재 118p) 난이도 ●○○ | 풀이 시간 40분 | 시간 제한 1초 | 메모리 제한 128MB 문제 맵은 N x M 크기의 직사각형이며, 맵의 각 칸은 (A, B)로 나타낼 수 있다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어있는 공간에는 갈 수 없다. 매뉴얼은 아래와 같다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향을 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어있는 칸의 경우에는, 바라보는 방향을.. 2021. 4. 10.
[이.코.테] Chapter 04 구현 - 왕실의 나이트 (Java) 왕실의 나이트 문제 (교재 115p) 난이도 ●○○ | 풀이 시간 20분 | 시간 제한 1초 | 메모리 제한 128MB 문제 나이트는 L자 형태로만 이동할 수 있으며, 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 8 X 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 대는 a부터 h로 표현한다. 입출력 조건) 입력 조건 - 첫째 줄에 8 X 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표.. 2021. 4. 10.
[이.코.테] Chapter 04 구현 - 시각 (Java) 시각 문제 (교재 113p) 난이도 ●○○ | 풀이 시간 15분 | 시간 제한 2초 | 메모리 제한 128MB 문제 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 경우의 수를 구하는 프로그램을 작성하시오. 입출력 조건) 입력 조건 - 첫째 줄에 정수 N이 입력진다. (1 ≤ N ≤ 100) 출력 조건 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다. 입출력 예시) 입력 예시 출력 예시 5 11475 문제 풀이 방법 모든 시각의 경우를 하나씩 세서 풀 수 있다. 왜냐하면 하루는 86,400초로 86,400가지밖에 존재하지 않기 대문이다. 경우의 수가 100,000개도 되지 .. 2021. 4. 10.
[이.코.테] Chapter 04 구현 - 상하좌우 (Java) 상하좌우 문제 (교재 110p) 난이도 ●○○ | 풀이 시간 15분 | 시간 제한 1초 | 메모리 제한 128MB 문제 아래와 같은 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오. L : 왼쪽으로 한 칸 이동 R : 오른쪽으로 한 칸 이동 U : 위로 한 칸 이동 D : 아래로 한 칸 이동 가장 왼쪽 위 좌표는 (1,1) 이며, 시작 좌표는 항상 (1,1)이다. 입출력 조건) 입력 조건 - 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 ≤ N ≤ 100) - 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 ≤ 이동 횟수 ≤ 100) 출력 조건 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력한다.. 2021. 4. 10.
구현 보호되어 있는 글 입니다. 2021. 4. 10.
[백준] 동적 프로그래밍 - 12865번 평범한 배낭(Java) 문제링크 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이방법 처음에 1차원 배열로 계산하여.. 실패하였다.. 다른 블로그들을 보며 아래 소스코드 작성 방법을 참조하여 문제를 풀었다. 소스코드 작성 방법 a를 이중 배열로 선언 크기는 [n+1][k+1]로 i는 물건의 종류, j는 무게 a[i][j]에 i-1번째 물품을 넣었을 때의 가치를 넣음 (현재(j) 무게 - 물품의 무게) > 0 이라면 max(i번째 물건을 .. 2020. 12. 6.
반응형

티스토리툴바