문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 백트레킹 문제이다. 숫자를 하나씩 뽑으면서 인접한 두 개의 부분 수열이 동일한 것이 있는지 확인하면 된다. 좋은 수열인지 판별하는 방법은 다음과 같다. 현재 str은 새로 뽑은 마지막 문자를 제외하면 좋은 수열인 상태이다. 따라서 마지막 문자만 연관된 부분이 좋은 수열인지 판별하면 된다. 이를 반복문과 sustring을 활용하여 구현하였다. 예를들어 1212라는 수열이 전달되었을때를 확인해보자. 마..
문제 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { static class Point implements Comparable{ int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } @Override public..
문제 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.pars..
문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 코드 BFS 문제 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer ..
문제 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTok..
문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringT..
문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 DP문제다. DP를 이차원 배열로 선언했고 이차원 배열을 이용하여 0과 1의 개수를 저장했다. i 번째의 0, 1의 개수를 구하고자 한다면, i-1 번째와 i-2번째의 0, 1의 개수를 더하면된다. 코드 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(ne..
문제 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이 이 문제는 최장 증가 부분 수열(LIS)를 구하는 문제다. 최장 증가 부분 수열은 dp를 이용하여 풀면 O(N^2)의 시간 복잡도가 나온다.(이분탐색을 이용하면 O(nlogn)) 코드 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException{ Bu..
문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 코드 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.r..
문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 그냥 구현하면 되는 문제다. 직접 돌아가는 곳에 대해 인접한 톱니바퀴가 돌아가는지 안돌아가는지 판단해주었다. 반시계, 시계방향으로 돌아가기 때문에 각 톱니바퀴는 ArrayList를 이용하여 구현해주었다. 코드 import java.util.*; import java.io.*; public class Main { static ArrayList arr [] = new ArrayList ..
