본문 바로가기

Algorithm

 (172)
[BOJ-14502][BFS/시뮬레이션] 연구소 - Java 문제 바로가기 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net N x M 크기의 연구소에서 벽을 꼭 3개를 세워서 바이러스가 퍼지는 것을 막는 문제입니다. 벽을 세운 뒤 바이러스가 퍼지고 안전 영역의 최대값을 구하면 됩니다. import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Dir { int y; int x; Dir(int y,..
[SWEA-1210] Ladder1 - Java 사다리를 타서 2가 걸리는 시작지점이 어딘지를 찾는 문제입니다. 밑에서 2를 찾아서 올라가는 방식으로 구했습니다. 한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하는 경우가 없기 때문에 왼쪽, 오른쪽, 위의 순서로 방향을 봐주면서 다음 좌표를 업데이트해주면 됩니다. import java.util.Arrays; import java.util.Scanner; public class Ladder1 { static int size = 100; private static boolean isIn(int y, int x) { if(0
[SWEA-1208] Flatten - Java 아무런 알고리즘이 필요없는 간단한 문제입니다. 주어진 횟수만큼 제일 큰 놈에서 제일 작은 놈으로 옮겨주면 됩니다. 가로의 길이가 항상 100개이므로 정렬하면서 가장 큰 쪽을 하나 빼고 가장 작은 쪽을 하나 더하면 됩니다. import java.util.Arrays; import java.util.Scanner; public class Flattern { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String output = ""; int T; T=10; for(int test_case = 1; test_case
[BOJ-11726][DP] 2×n 타일링 - Java 문제 바로가기 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제입니다. 점화식을 구해보면 dp[n] = dp[n-2] + dp[n-1] 가 됩니다.. n=4 정도까지 해보니 얼추 나오는디 사실 어떻게 하면 점화식을 잘 구하는지 잘 모르겠슴다 ㅜ //top-down private static int topDown(int n){ if(n == 0 || n == 1) return 1; if(dp[n] != 0) return dp[n]; dp[n] = topDo..
[BOJ-1765][DFS] 닭싸움 팀 정하기 - Java 문제 바로가기 1765번: 닭싸움 팀 정하기 문제 닭싸움은 월드의 전통이다. 이번 캠프에서도 어김없이 닭싸움 대회가 열렸다. 그런데, 닭싸움을 하기 위해서는 반드시 누가 우리 편이고, 누가 우리 편이 아닌지를 알아야 할 것이다. 닭싸� www.acmicpc.net BFS 태그에서 찾았는데 DFS로 풀었씀다.. 내 친구의 친구는 내 친구이다. 내 원수의 원수도 내 친구이다. 이 규칙을 잘 생각하고 풀면 됨미다.. friend 그래프와 enemy 그래프를 만들고, N 번을 돌면서 check 배열을 두어 해당 사람을 봐줬는지 체크하면서 봐주면 됩니다.. 뭔서린지 모르겠ㄴㅔ import java.util.ArrayList; import java.util.Scanner; public class Main { sta..
[BOJ-1463][DP] 1로 만들기 - Java 문제 바로가기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net N이 주어지면 1) 1을 빼거나, 2) 2의 배수면 2로 나누거나, 3) 3의 배수면 3으로 나누는 세가지 액션 중 하나를 해서 1로 만드는 최소 횟수를 구하는 문제입니다. 기본적인 Dynamic Programming 문제입니다.. DP는 메모이제이션(Memoization)이란 기술을 사용해서 풉니다. 메모이제이션이란 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술입니다. DP를 푸는 방법은 크게 Top-Down 방식과 Bottom-Up 방식이 있습니다. Top-..
[BOJ-1181][문자열] 단어 정렬 - Java 문제 바로가기 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 중복 제거후, 단어의 길이로 먼저 정렬을 하고, 단어 길이가 같은 경우에는 사전순으로 정렬을 하면 되는 문제입니다. 자바로 custom하게 어떻게 정렬하는지 한참 찾아보고 풀었습니다. import java.io.IOException; import java.util.*; class sortByValueFirst implements Comparator{ @Override public int compare(String o1, String o2) { ..
[BOJ-2667][BFS] 단지번호붙이기 - Java 문제 바로가기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 아주 간단한 BFS 문제 입니다. 다만 각 단지에 속하는 집들의 수를 오름차순으로 정렬해야 하니 주의하세여. import java.io.IOException; import java.lang.reflect.Array; import java.util.*; class Dir{ int y; int x; Dir(int y, int x){ this.y = y; this.x = x; } } public class Main { static int N; stati..

티스토리툴바