전체 글

https://www.acmicpc.net/problem/16974 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, www.acmicpc.net 레벨 버거와 먹은 햄버거의 수가 주어졌을 때 먹은 패티의 양을 구하는 문제이다. 레벨 버거는 빵 + 이전단계 레벨버거 + 패티 + 이전단계 레벨버거 + 빵으로 구성된 버거이다. 레벨0 버거는 패티한장만으로 구성되 있다고 한다. 수식으로 만들면 다음과 같이 만들 수 있다. B (Li - 1) p (Li - 1) B 그럼 예제를 분석해보자. 예제 입력 1 복사 2 7 레벨 2 버거를 7..
https://www.acmicpc.net/problem/1030 1030번: 프렉탈 평면 첫째 줄에 7개의 정수 s, N, K, R1, R2, C1, C2가 주어진다. www.acmicpc.net 이문제는 s,N, K, R1, R2, R3, R4를 입력받은 뒤 범위만큼의 프렉탈 크기를 출력하면된다. s = 반복횟수 N = 프렉탈의 크기 K = 검은색(1) 크기 R1, R2 = 행의 크기 C1, C2 = 열의 크기 예제를 보면서 설명하겠다. 예제 입력 1 복사 1 5 3 0 4 0 4 예제 입력 2 복사 2 3 1 0 8 0 8 예제 입력 3 복사 3 3 1 4 11 5 10 import java.util.Scanner; public class 프렉탈평면 { static int s, N, K, R1, R..
https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net NxN 색종이를 입력받은 후 정사각형이 될 때까지 나눈다. 그리고 최종적으로 나누어진 하얀색, 파란색 색종이의 개수를 출력하면 되는 문제이다. 입출력을 살펴보자. 8 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0..
https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이문제는 행렬의 지수를 절반으로 자르면서 분할계산을 하는 행렬 제곱문제이다. 분할 계산(partition) 문제를 풀기위해서는 짝수일 경우, 홀수일 경우 어떻게 숫자를 탐색해야 하는지 생각해 봐야한다. 먼저 짝수일 경우 계산 과정이다. 위에서 설명했다시피 분할 계산을 해주면 되는데 짝수일 경우는 2로 나누었을 때 나머지가 생기지 않으므로 그냥 나누어서 곱해주면 된다. 다음은 홀수인 경우이다. 홀수의 경우 2로 ..
알고리즘이란? 1. 문제를 해결하기 위한 단계적 절차 또는 방법 2. 순서대로 구체적이고 명확하게 기술해야 한다. 3. 유효한 입력을 받아 실행한 결과인 해(답)를 출력한다 1.명확성 –알고리즘의 각 단계는 애매모호하지 않고 명확해야 한다. 2.정확성 –모든 유효한 입력에 대해 올바른 해를 출력해야 한다. 3.정지성 –유효한 입력이 주어지면 유한한 시간 내에 종료되어야 한다. 위와같이 알고리즘을 작성할 때는 명확하고 정확하게 작성을해야 한다. 다음 알고리즘을 구현해 보자. import java.util.Scanner; public class 함계산 { public static void main(String[] args){ int n = 5; int sum = 0; int i = 0; while(i < n..
1주차에 조를 짜기위한 사전 평가 시험을 치뤘다. 사전 평가 때 치뤘던 문제를 복습겸 분석해보려한다. 1. 다음 코드에서 while 문의 수행이 끝났을 때 count 변수와 mystery변수의 값은 각각 얼마인가? package 이충기; public class 사전평가시험1 { public static void main(String[] args){ int count = 0; int mystery = 1; while(count < 5){ count++; mystery = mystery * count; } System.out.printf("%d %d",count, mystery); } } 간단한 문제이다. count = 0, mystery = 1인 상태에서 문제를 풀면된다. 반복문 while문에서 count..
· 백준 : BFS
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 첫째 줄에 정점의 개수 N과 간선의 개수 M, 시작할 정점의 위치 V를 입력받는다. 첫째줄에 DFS 수행결과, 둘째줄에 BFS로 수행한 결과를 출력하면 된다. 문제풀이 먼저 문제를 빠르게 이해하기 위해 입출력을 살펴보자. 예제 입력 1 복사 4 5 1 1 2 1 3 1 4 2 4 3 4 예제 출력 1 복사 1 2 4 3 1 2 3 4 정점 4개에 간선 5..
· 백준 : BFS
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 문제 첫째 줄에 정점의 개수 N과 간선의 개수 M을 입력받고, 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v를 입력받아 연결 요소의 개수를 구하면 되는 문제이다. 문제풀이 직관적인 풀이를 위해 예제 입력값을 순서대로 그려보겠다. 예제 입력 1 복사 6 5 1 2 2 5 5 1 3 4 4 6 예제 출력 1 복사 2 예제1을 보면 연..
· 백준 : BFS
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 이 문제의 핵심만 집어보자. N x M의 상자에 토마토가 있다. ( N = 가로, M = 세로 || 2
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.1 초 (하단 참고) 256 MB 74123 30211 22201 40.305% 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CA..
유민기
Youminki