율무의 하루 율무의 하루

안녕하세요, 오늘은 자바를 이용하여 간선리스트를 구현해보려고 합니다! 간선 리스트 간선 리스트는 다음과 같은 무방향 그래프가 존재할 때 리스트의 간선의 정보를 담아주는 구조입니다. 1. 간선 리스트에 담을 정보를 class로 선언해줍니다. 2. 간선 리스트를 선언 해줍니다. 3. 관계 정보를 입력 받습니다. 4. 간선 리스트에 관계 정보를 저장합니다. 공간 복잡도: O(E) ※ V(vertex): 정점 / E(edge): 간선 import java.util.*; import java.io.*; class Edge{ int from, to; Edge(int from, int to){ this.from = from; this.to = to; } } public class Main { public static..

오늘은 자바를 이용하여 인접리스트를 구현해보려고 합니다. 인접 리스트 인접 리스트는 다음과 같이 무방향 그래프가 존재할 때 정점의 개수만큼 리스트를 생성하고 정점의 리스트와 인접한 정점의 정보를 연결해주는 구조입니다. 1. arraylist를 담을 수 있는 array list를 선언해줍니다. 2. 관계를 입력받습니다. 3. arraylist[from]에 to 값을 삽입해주고, arraylist[to]에 from값을 삽입해줍니다. 공간 복잡도: O(E) ※ V(vertex): 정점 / E(edge): 간선 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOExcepti..

오늘은 자바를 이용하여 인접행렬을 구현해보려고 합니다. 인접 행렬 인접행렬은 다음과 같이 무방향 그래프가 존재할 때 이차원 배열을 이용하여 각 정점에 인접한 정점의 정보를 넣어주는 구조입니다. 1. 정점의 개수에 해당하는 크기의 2차원 배열을 선언 합니다. 2. 관계를 입력 받습니다. 3. 입력받은 from, to 정보를 배열에 저장해줍니다 공간 복잡도: O(V^2) ※ V(vertex): 정점 / E(edge): 간선 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ int N = 5; //정점 갯수 boolean[][] arr = new boo..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net Problem 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net Problem 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net Problem RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 ..

Problem 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net Problem 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. Input 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. Output 각 테스트 케이스마다, ..