은비블로그

https://www.acmicpc.net/problem/2660 [풀이과정]문제 이해가 힘들었다. 그래프로 바꿔 생각하면직접 친구 = 거리 1친구의 친구 = 거리 2이런 식이었다.각각의 후보(노드)는 가장 먼 친구의 점수(거리)이고회장은 그 중 점수가 가장 작은 후보이다.이때 같은 점수를 가진 모든 후보를 출력해야 했음. 모든 정점 쌍 간의 최단 거리를 구해야 했기 때문에 플로이드 와샬 알고리즘을 사용했다. [코드]import java.io.*;import java.util.StringTokenizer;/*각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 됨.다른 모든 회원과 친구이면 1점다른 모든 회원과 친구 || 친구의 친구이면 2점다른 모든 회원과 친구 || 친구의 친구 ||친구의 친구의 ..

https://www.acmicpc.net/problem/6198 [풀이과정]예전에 비슷한 문제를 풀었던 것 같은데 문제 이름이 생각이 안난다.그때는 그냥 배열에 값 넣고 비교하며 풀었던 것 같다.이번엔 스택 이용해서 풀었는데 조금 더 복잡하고 사고해야 했었지만 더 간결한 코드가 나온 것 같아 기분이 좋다.answer 변수를 long 타입으로 선언해야 함에 주의! [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;import java.util.StringTokenizer;/*N개의 빌딩 = = = = ..

https://www.acmicpc.net/problem/17404 [풀이과정]최대한 단순하게 생각하는 것이 풀이의 핵심인 것 같다.RGB거리 실버 1보단 어려웠다.https://www.acmicpc.net/problem/1149 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*집이 N개.각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때,1. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.2. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.3. i(2

https://www.acmicpc.net/problem/12865 [풀이방식]Top-down 방식으로 풀었다.DP[n][k]: n번째 물건까지 고려했을 때, 배낭의 용량이 k일 때 얻을 수 있는 최대 가치. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*N개의 물건. 각 무게 W, 가치 VK만큼의 무게에서 최대 가치 구하기 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); sta..

음의 가중치가 없는 그래프의한 노드에서 각 모든 노드까지의 최단 거리를 구하는 알고리즘 [시간복잡도]O((V+E)logV)이지만열결 그래프라면 O(ElogV)까지 줄일 수 있다.일반적으로는 우선순위 큐를 이용하는 것이 낫다고 한다. [매커니즘]1 ) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택2 ) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신 [초기화]A노드에서 A노드로 가는 가는 지점이 가장 짧다.라고 정의 [알고리즘 적용]방문하지 않은 노드 중 가장 비용이 적은 노드를 선택하며 값 갱

음수 사이클이 없는 그래프 내의모든 정점에서 모든 정점까지의 최단거리를 모두 구할 수 있는 알고리즘. *음수 사이클 : 사이클의 모든 경로를 지나 원래 지점으로 돌아왔을 때 최종 비용이 음수인 사이클 다이나믹 프로그래밍 기법을 사용한 알고리즘.인접 행렬을 이용해서 각 노드간 최소 비용을 계산한다.한 정점에서 한 정점까지 가는 경로의 간선 개수를 0개에서 N개까지 모두 고려. 0개의 간선을 거쳐 가는 경우는 자기 자신밖에 없기 때문에초기 그래프의 모양은 (r, c) (r==c)을 제외하고 모드 매우 큰 값으로 초기화해준다.연결되지 않는 경로는 매우 큰 값으로 초기화되어 있을 것이다. 코드 // 플로이드 초기 거리 테이블 초기화 dist = new int[N][N]; for (int i = 0; i  ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 수가 11밖에 없길래 배열을 생각했음 법칙이 있어서 단순하게 풂 1로만 이루어졌을 때, 2와 1로만 이루어졌을 때, 3이 포함됐을 때를 나눠서 코드를 구현해보자 내 코드 메모리 : 14120 KB 시간 : 128 ms 코드길이 : 632 B [내 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(..

https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 반복된 계산을 많이 해야 해서 아예 배열로 만들어서 계산함. 내 코드 메모리 : 14044 KB 시간 : 120 ms 코드길이 : 1693 B [내 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int[] num = {9, 90*2, 900*3, 9000*4, 90000*5, 900000*6, 9000000*7, 90000000*8}; publi..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net M과 N의 최소공배수가 최대연도니까 그만큼 for문을 돌림. year을 +1 해주면서 x 와 y 를 계산해줌. 이때 나머지가 0인 경우를 생각해야 하기 때문에 x, y를 입력할 때 -1을 해준다. 나온 year에 +1 해준 값이 답. 내 코드 메모리 : 44152 KB 시간 : 632 ms 코드 길이 : 1131 B [내 코드] import java.io.BufferedReader; import ja..

https://www.acmicpc.net/problem/5692 5692번: 팩토리얼 진법 상근이는 보통 사람들이 사는 것과는 조금 다른 삶을 사는 사람이다. 상근이는 이런 사람들의 시선이 부담스럽기 때문에, 자신만의 숫자를 개발하기로 했다. 바로 그 이름은 팩토리얼 진법이다. www.acmicpc.net 수를 String으로 받아서 계산해줌 factorial 메소드 구현 >> 최대 5의 길이여서 아예 값을 저장한 배열을 구현해도 좋았을 것 같다. 메모리 : 25240 KB 시간 : 340 ms 코드길이 : 683 B [내 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; publ..