문제를 효율적으로 해결하는 것은 무엇일까? 똑같은 문제를 해결해도 빠르게 해결하는 것이 중요하다. 같은 입력을 제공했을 때, 어느 프로그램이 더 빠른가? 내 프로그램은 얼마나 빠를까? 라는 의문을 가지고 나오게 된 것이 시간 복잡도이다. 프로그램이 대략적으로 몇 개의 명령을 수행하는가? public class Main { public static void main(String[] args) { int a =1, b= 5; int sum = a+b; System.out.println(sum); } } 위와 같은 코드는 a, b를 선언하고 sum 에다 a+b 값을 넣어주고 출력해주는 코드이다. 위는 대략 3번이 실행되는 데 이것은 O(3)이라고 한다. O는 Big-O를 나타내고 읽을 때는 빅-오 또는 오더라..
완전 탐색 문제입니다. 핵심 우선 세로 길이가 4인 블록을 넣을 수 있는지를 확인해야 한다. 가능하다면, 블록을 넣고 그때의 점수를 찾고, 다시 블록을 지우는 것이 핵심이다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int c = sc.nextInt(); //가로 int r = sc.nextInt(); //세로 //값넣기 int[][] arr = new int[r + 1][c + 1]; for (int i = 1; i
오늘은 완전 탐색 알고리즘에 대해 알아보자 완전탐색 알고리즘이란? 완전탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. 즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미한다. 이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부른다. 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 영어로 brute는 "짐승 같은, 난폭한"이라는 뜻이고, brute-force는 "난폭한 힘, 폭력"이라는 뜻이다. 오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식하다고 생각할 수도 있겠지만, 항상 정확도 100%를 보장한다는 점에서 암호 해독법 중 가장 확실하고 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해..
2주 차에서 다룰 내용은 다음과 같다. 1. Computer Architecture 고정 소수점/ 부동 소수점 패리티 비트/ 해밍 코드 ARM 프로세서 2. Java 고유 락 문자열 클래스 Garbage Collection Primitive type & Reference type Computer Architecture 컴퓨터에서 실수를 표현하는 방법은 고정 소수점과 부동 소수점 두 가지 방식이 존재한다. 고정 소수점/ 부동 소수점 고정 소수점(Fixed Point)이란? 소수점이 찍힐 위치를 미리 정해놓고 소수를 표현하는 방식이다. (정수 + 소수) ex) -6.12345 -> 부호(-)와 정수부(6), 소수부(0.12345) 3가지 요소가 필요함 장점: 실수를 정수부와 표현하여 단순하다. 단점: 표현의..
완전 탐색 관련 문제입니다. 핵심 문제에서 좌표로 주어진 자리를 우리는 배열을 이용해서 표현해야 한다. 즉 좌표를 x축으로 대칭시킨 모습이 배열과 같다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int width = sc.nextInt(); // 공연장의 가로길이 int height = sc.nextInt(); // 공연장의 세로길이 int order = sc.nextInt(); // 대기순서 int x = 0, y = -1; boolean down = true, up = false, right = false, lef..
이번에 풀어볼 문제는 우리가 어릴 때 자주 해보았던 숫자 야구게임이다. 핵심 완전 탐색 문제답게 가능한 모든 수를 대입해보아야 한다. 즉 123~987까지 해당 조건(스트라이크, 볼의 카운트)에 맞다면, 참이 되는 수를 1 추가한다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int [][] arr = new int[105][3]; int n = sc.nextInt(); for (int i=0;i
완전 탐색 알고리즘 문제입니다. 핵심 처음에 이 문제를 풀려고 한다면, 여러 가지 방법을 떠올릴 것이다. 개인적으로 쉬운 방법은 배열의 거리를 구하는 것이다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int X = sc.nextInt(); int Y = sc.nextInt(); int R = sc.nextInt(); for (int i =1; i
완전 탐색 알고리즘 문제입니다. 핵심 문제가 어려워 보일 수 있으나, 단순한 문제이다. 0으로 된 배 열위에 값을 입력받고, 그 값이 몇 번 나왔는지 체크하는 것이다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int[][] arr = new int[101][101]; int n = sc.nextInt(); for (int i=1;i
우선 완전 탐색 알고리즘이란 가능한 모든 경우를 탐색하는 것이다. 아래의 체스 문제를 생각해보면, 룩이 이동 가능한 경우를 모두 탐색해보면 된다. 이때 출력은 1이다. 핵심 이 문제를 풀 때, 어떤 것을 기준으로 할까에 따라 풀이가 살짝 달라진다. 룩을 기준으로 하여, 룩의 이동경로 중 킹이 있다면 1 없다면 0을 출력하면 된다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[][] arr = new int[8][8]; int[] rookX = new int[2]; int[] rookY = new int[2]; i..
