Algorithm (105) 썸네일형 리스트형 [BOJ] 16174 점프왕 쩰리 G5 (JAVA) 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 문제 이해 * 1. 범위 안에서만 움직인다. * 2. 젤리는 0,0에서 시작한다 * 3. 이동 가능한 방향은 오른쪽과 아래뿐이다 * 4. 도착점은 N-1, * N-1이다. * 5. 한번에 이동할 수 있는 칸의 수는 현재 밟고있는 칸에 쓰여진 수 * 6. 승리여부출력 아이디어 물구나무서서 봐도 그래프 문제였다. bfs건 dfs건 괜찮을거같은데 난 bfs로 풀었다. 코드 import java.io.*; import java.util.*; public class bj_16.. Stack 스택 (JAVA) 간단 개념 1. 스택은 가장 나중에 들어간 요소가 가장 먼저 나오게 되는 구조를 가진다(Last In First Out) 2. 배열, 리스트를 이용해서 구현할 수 있다. 구현 명세 [배열스택] 1. 삽입 2. 삭제 [링크드리스트스택] 1. 삽입 2. 삭제 구현 1. 배열 스택 Step 1. Push - 삽입하기 전에 스택 배열을 생성한다. static int[] arrStack; - top위치를 저장할 변수를 생성한다. - 배열의 인덱스가 0에서 시작하기 때문에 빈 스택을 나타내려면 -1로 한다. static int top = -1; // index 0부터라서 -1해야 빈 스택 - push 메소드를 작성한다. - 배열 스택은 크기가 한정되어 있어서 크기가 넘어가면 메시지를 출력하게 했다. - 삽입시 to.. [BOJ] 2887. 행성터널 G1 JAVA 문제 이해 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. 아이디어 - 단순 크루스칼로 풀었는데.. ㅎㅎ 메모리초과가 떴다.. - 보니까 10만개 행성이라서 간선을 모두다 연결하면 터지는거였다 - 그래서 .. [BOJ] 1520. 내리막길 G4 JAVA 문제 이해 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 아.. [BOJ] 4386. 별자리 만들기 G4 JAVA 문제 이해 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.(출력은 절대/상대 오차는 10-2까지 허용 = 소수 둘째짜리까지 ) 아이디어 - MST(Minimum Spanning Tree) 문제이다. - 이 프로세스로 코드를 짰다. 1) 입력 2) 모든 별들 사이의 거리(=비용)을 구하기 3) Kruskal로 구하기 4) .. [BOJ] 2667. 단지번호 붙이기 S1 JAVA 문제 이해 - 정사각형 모양의 지도에서 1은 집이 있는 곳, 0은 집이 없는 곳 - 단지 = 연결된 집의 모임 단지에 번호를 붙인다. - 연결되었다는 것은 어떤 집이 상/하/좌/우로 붙어있는 경우 (대각선상은 제외) - 지도를 입력하여 단지수를 출력, 각 단지에 속하는 집의 수(오름차순) 출력 아이디어 - dfs, bfs 등의 그래프 탐색으로 단지 카운팅 - 단지 카운트와 동시에 집 개수 카운팅 - 출력 코드 import java.io.*; import java.util.*; public class Main { static class Pos {//좌표값을 나타내기 위한 클래스 int x, y; public Pos(int x, int y) { this.x = x; this.y = y; } } static .. 이전 1 ··· 6 7 8 9 10 11 12 ··· 18 다음
