공부한것들을 정리하는 블로그 입니다.

1. Swap 을 이용한 순열 // 순서 없이 n 개중에서 r 개를 뽑는 경우 // perm(arr, 0, n, r); static void perm(int[] arr, int depth, int n, int r) { if (depth == r) { print(arr, r); return; } for (int i=depth; i

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; pu..

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net //수 이어 쓰기1 public void bf_1748(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.valueOf(bf.readLine()); long ans = 0; // 직접 계산하는 방법도 가능하지만, N이 너무 크기 때문에 실제로 수를 모두 만들면 시간초과 // ex) 999까지 그냥 구하면 => 시행횟수가 999이지만, 자릿수로 하..

선요약 • Java에서 String 의 += 연산은 O(N+K) 이다 • Java의 경우 StringBuilder 를 이용해야 한다 Java 입출력 • Java는 입력은 Scanner, 출력은 System.out을 사용한다. Scanner sc = new Scanner(System.in); • 입력이 많은 경우에는 속도가 느리기 때문에, BufferedReader를 사용한다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); • 출력이 많은 경우에는 StringBuilder를 사용해서 한 문자열로 만들어서 출력을 한 번만 사용하거나 • BufferedWriter를 사용한다. 시간 복잡도 시간 복잡도 안에 가장 큰 입력 범위..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net //카잉달력 public static void bf_6064(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.valueOf(bf.readLine()); while (t-- > 0) { String[] line = bf.read..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net import java.util.*; public class Main { //테트로미노 static int[][][] BLOCKS_14500 = { //19 4 2 {{0,0}, {0,1}, {0,2}, {0,3}} ,{{0,0}, {1,0}, {2,0}, {3,0}} ,{{0,0}, {1,0}, {0,1}, {1,1}} ,{{0,0}, {0,1}, {0,2}, {1,2}} ,{{0,0}, {1,0..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net static boolean[] broken = new boolean[10]; public static void bf_1107(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 이동 원하는 채널 int m = sc.nextInt(); // 고자안 채널 갯수 for (int i = 0; i < ..

https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int E = sc.nextInt() -1; int S = sc.nextInt() -1; int M = sc.nextInt() -1; fo..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net import java.util.Arrays; import java.util.Scanner; public class Main { //사탕게임 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); char[][] a = new char[n][n]; int ans = 1; for (int i = 0; i < n; i++) { a[i] = sc.next().toCharArray(); } for (i..

1. 경우의 수 • N명의 사람이 한 줄로 서는 경우의 수 → N × (N-1) × … × 1 = N! • N명의 사람 중에서 대표 두 명을 뽑는 경우의 수 → N × (N-1) / 2 • N명의 사람 중에서 대표 세 명을 뽑는 경우의 수 → N × (N-1) × (N-2) / 3! • N명의 사람 중에서 반장 1명과 부반장 1명을 뽑는 경우의 수 → N × (N-1) • N명의 사람이 있을 때, 각 사람이 영화를 볼지, 보지 않을지 결정한다. 가능한 조합의 수 → 2N 2. 그냥 다 해보기 예제 : 일곱 난쟁이 https://drsggg.tistory.com/537 브루트 포스 2309번 일곱 난쟁이 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 ..

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] intArr = new int[9]; int sum = 0; int highA = 0; int highB = 0; //난쟁이 9명의..

브루트 포스(Brute Force) 브루트 포스는 '모든 경우의 수'를 다 해보는 것이다. 이 때, 경우의 수를 다 해보는데 걸리는 시간이 문제의 시간 제한을 넘지 않아야 한다. ( * '모든 경우의 수' : 가능한 벙법 ) 따라서 브루트 포스 문제의 경우 '모든 경우의 수'가 몇가지 나오는지 알아보는 것이 상당히 중요 브루트 포스는 모든 방법을 1번씩 시도해보기 때문에 아래 3가지 단계를 생각해볼 수 있다. 1. 문제의 가능한 경우의 수를 계산해본다. • 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다. 2. 가능한 모든 방법을 다 만들어본다. • 하나도 빠짐 없이 만들어야 한다. • 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용이 있다. ..

보호되어 있는 글입니다.

[참고] 관련포스트 [Java] 기초알고리즘 - 00. 버블정렬(Bubble Sort) : http://javaking75.blog.me/140186094683 [Java] 기초알고리즘 - 09. 선택정렬(SelectionSort) 알고리즘 : http://javaking75.blog.me/140176253632 [Java] 기초알고리즘 - 00. 삽입정렬 (Insertion Sort) : http://javaking75.blog.me/140187255750 [javascript] 배열 - Array 객체 - 버블정렬(Bubble Sort) 알고리즘 예제 : http://javaking75.blog.me/140183503202 [javascript] 배열 - Array 객체 - 선택정렬(Selection..

Insertion Sort 삽입정렬은 이름에서 알 수 있듯이 삽입을 통해 정렬을 완성하는 알고리즘이다. 삽입정렬은 모든 데이터를 앞에서부터 차례로 비교 하여 자신의 위치에 삽입을 통해 정렬을 수행한다. 배열이 길어질수록 효율이 떨어지지만 구현이 간단하다는 장점이 있다. 삽입정렬의 과정을 살펴보면 다음과 같다. 다음은 삽입정렬을 구현한 예이다. #using Cvoid insertionSort(int list[], int n){ int i, j, key; for(i=1; i=0 && list[j]>key; j--) // 선택된 값(key)보다 작은 값을 찾는다. list[j+1] = list[j]; // 작은 값을 찾은 경우 그 값뒤의 모든 값을 우측으로 이동 list[j+1] = key; // 해당되는 곳..