L.O.K

2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 1. 문제 추상화 주어진 값들 중 세 개를 추출하여 블랙잭 수보다 같거나 작은 최대값을 구하시오. 2. 알고리즘 굉장히 쉬운 문제지만 브루트포스를 몰라 어렵게 풀었다;; 브루트포스(BruteForce)란, Brute( 무식한 )과 Force ( 힘 )의 합성어로 무식한 힘이라는 의미다. 다시 말해서, 무식하게 모든 경우의 수를 탐색하여 조건에 맞는 결과를 내놓는 알고리즘이 효율적일 때가 있다는 말이다. 나는 모든 경우의 수를 조사..

2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 1. 문제 추상화 입력된 값 N은 3의 거듭제곱이다. 만약 N이 3이면 출력은 아래와 같다. N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태로 출력하시오. 2. 알고리즘 어려운 문제다. 문제를 이해하기 힘들어서 인터넷을 찾아봐서 풀었다. 그래도 이번 문제를 통해 재귀함수를 깊이 이해할 수 있었다. 재귀적 사고와 선형적 사고는 다르다. 선형적 사고는 1..

11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 1. 문제 추상화 원판 개수에 따른 하노이탑 최소 이동 횟수와 이동 과정을 출력하시오. 2. 알고리즘 ▷ 하노이탑 개념 수학적 사고력이 뛰어나거나 하노이탑의 개념을 어느정도 알아야 풀 수 있는 어려운 문제이다. 나 또한 하노이탑에 대해서 잘 모르기에 여기저기 찾아보며 풀었다. 1번에 쌓여있는 원판들을 3번까지 옮겨야 한다. 단, 규칙이 있다. 1. 1회에 한 개의 원판만 옮길 수 있다. 2. 반드시 큰 원판 위에 작은 원판이 있어야 한다. 재귀적 사고..

3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net 1. 문제 추상화 반지름 r이 주어질 때, 유클리드 기하학의 원의 넓이와 택시 기하학의 원의 넓이를 구하라. 2. 알고리즘 택시 기하학을 모르는 경우와 택시 기하학을 아는 경우 두 가지 풀이 방법이 있다. 첫 번째 방법 ( 택시 기하학을 모르는 경우 ) 원의 정의는 같으나 택시 기하학을 모르면 어떤 원리로 원이 형성되는지 모른다. 다시 말해, '원주율'을 모른다. 그러나 이미 원주율이 예제에 주어져 있다. 유클리드 기하학에서 원주율은 ㅈ(파이)이다. 그리고 택시 기하학의 원주율은 2이..

1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 1. 문제 추상화 임의의 Z 지점이 있다. A점과 Z점 사이의 거리가 r1, B점과 Z점 사이의 거리가 r2를 만족할 때, Z 지점의 경우의 수를 구하라. 2. 알고리즘 Z점과 A점의 거리가 r1이 되는 경우의 수는 무한이다. 원이기 때문이다. Z점과 B점의 거리가 r2가 되는 경우의 수도 무한이다. 원이기 때문이다. 그러므로 r1과 r2를 동시에 만족하는 Z지점의 개수는 두 원의 교차점의 개수와 같다. 두 원의 위치관계, 내접, 외접 위치관계 또 나오네요. 이번에는 두 원의 위치관계에요. 위치관계 마지막이니까 정..

3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 추상화 3개의 좌표가 주어 질 때, 직사각형을 만드는 네 번째 점의 좌표를 구하시오. 2. 알고리즘 코드는 단순함이 중요하다. 반복문, 조건문을 자주 사용하는 것보다 가독성 있는 코드를 지향해야한다. 1. 직사각형은 x축과 y축의 대칭이다. 그러므로 x좌표와 y좌표는 x1,x2 와 y1, y2 두 값만 가진다. 2. 주어진 세 좌표 중 x1,x2 와 y1, y2가 한 번만 나온 값이 네번째 좌표가 된다. 3. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; impo..

1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 추상화 왼쪽 아래 꼭지점이 (0.0)이고 오른쪽 위 꼭지점이 (w,h)인 직사각형 안에 (x,y)좌표의 A 지점이 있다. A에서 직사각형 경계까지의 최소거리를 구하라. 2. 알고리즘 조건을 토대로 단서를 구체적으로 파악해야한다. 단서를 확보하지 않고 비슷한 문제의 알고리즘을 떠올려 템플릿 쓰듯 사용하면 효율적인 코드를 작성하지 못한다. 단서를 토대로 필요한 알고리즘이 무엇인지 생각해야한다. 첫 번째 방법 직사각형을 네 부분으로 나눈 후, ..

9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 1. 문제 추상화 짝수는 두 소수의 합으로 표현 가능하다. 이 때, 두 소수의 차이가 최소인 경우를 출력하시오. 2. 알고리즘 첫 번째 방법 조건 : 짝수 - 작은 소수 = 큰 소수 해당 조건을 만족하는 작은 소수를 구한다. 작은 소수 중 가장 큰 소수일 때, 두 소수의 차이가 작다. 두 번째 방법 C는 짝수 C/2 +C/2 = C C/2-1 + C/2+1 = C C/2-2 + C/2+2 = C . . 반복문을 통해, 하나는 -1 씩, 하나는..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 1. 문제 추상화 M과 N 사이의 소수를 출력하시오. 2. 알고리즘 첫 번째 방법 ( % 연산 ) 1. M부터 N까지의 자연수를 반복문 변수 i에 저장한다. 2. 이중 for문을 만들어, % 연산을 통해 소수여부를 판단한다. 3. 소수여부는 플래그 변수를 만들어 true, false로 파악한다. 두 번째 방법 ( 아리스토테네스의 체 ) 1. N + 1 크기의 boolean 배열을 만든다. 2. 이중 for문 구조를 만들어, 2의 배수, 3의 배수.... 를 true로 저장한다. 3. true로..

1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 1. 문제 추상화 입력받은 N개의 수 중, 소수가 몇 개인지 출력하시오. 2. 제약조건 N은 100이하이고 수는 1000이하의 수가 주어진다. 3. 알고리즘 첫 번째 방법 : 아리스토테스의 체 1. 0~1000까지의 boolean 배열을 만든다. 2. 0~1000까지 i를 1씩 증가시켜 각 i의 배수를 true로 저장한다. 3. 반복문이 끝난 후, false로 남아있는 인덱스가 소수이다. 두 번째 방법 : 제곱근 1. 주어진 수가 5라면 5보다 작은 정수를 5에 나누었을 때 나머지가 0이 아니면 소수이다. 2. 1을 제외하고 2,..