study

문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제해결 - 피보나치 수열푸는 방식과 동일함 - n의 값이 1로 들어올때 dp[2] = 1;이 성립될수 없으므로 dp 배열의 사이즈는 넉넉하게 n+2로 한다 import java.util.Scanner; public class B2193 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); i..

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제해결 - dp를 2차원 배열로 만들어 1차원에는 자리수, 2차원에는 맨 오른쪽 숫자를 표현하고 값은 각각 0~9로 끝나는 계단수의 개수를 저장한다 - n이 1일경우(한자리수일 경우) 0을 제외한 1~9이기 때문에 1로 초기화 한다 - 2자리수의 끝이 5인 계단수는 1자리수인 4, 6에 +1, -1한 값인 45, 65이다 - 맨 오른쪽 숫자가 0일경우 그 전 자리수의 1에 -1한 값만 올수 있다(1->10) - 맨 오른쪽 숫자가 9일경우 그 전 자리수의 8에 +1한 값만 올수 있다(8->89) - 이 규..

운영체제에 들어가기 앞서 하드웨어가 어떻게 돌아가는지 공부 computer: CPU + Memory I/O device: disk, 키보드, 모니터 등 - I/O 디바이스는 각각 device controller 라는 하나의 작은 CPU를 가지고 있음 - I/O 디바이스는 CPU가 직접 관리하는 것이 아닌 device controller가 관리함 - CPU와 memory가 있듯 각각 I/O 디바이스도 local buffer가 존재 - CPU는 매 클럭 사이클마다 memory로부터 instruction을 읽어와서 실행함 - Interrupt line: CPU의 속도와 I/O 디바이스의 속도는 크게 차이가남, CPU가 프로그램 A의 instruction을 실행하고 있을때 disk로부터 값을 읽어와야 하면(I/..

문제 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제해결 - 같은 숫자가 2개 연속으로 나오면 안되기 때문에 dp 배열을 2차원 배열로 만든다 - n을 만들 수 있는 식 중 1로 끝나는 식은 dp[n][1]에, 2로 끝나는 식은 dp[n][2]에, 3으로 끝나는 식은 dp[n][3]에 담는다 - dp[n][1]에는 i-1을 만들수 있는 식 중 2로 끝나는식, 3으로 끝나는 식 개수를 넣는다 - dp[n][2]에는 i-2를 만들수 있는 식 중 1로 끝나는식, 3으로 끝나는 식 개수를 넣는다 ..

문제 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제해결 - 11052 카드 구매하기 문제와 비슷하다 https://broship.tistory.com/220 - 다만 n개의 카드 구매를 위해 최대값을 구하는게 아니라 최소값을 구하면 된다 import java.util.Scanner; public class B16194 { public static void main(String[] args) { Scanner sc = new Scanner(S..

문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제해결 - dp 배열을 만들고 dp[1] : 카드 1개 사는 최대값 dp[2] : 카드 2개 사는 최대값 .... dp[n] : 카드 n개 사는 최대값을 넣는다 - dp[i]를 구하기 위해선 또다시 반복문을 돌며 모든 dp[i-j] + dp[j]의 값중 가장 큰 값을 dp[i]에 넣는다 i가 5일때 dp[5] : 5장 카드 살때 dp[5-1] + dp[1] : 4장 카드 구매하는 최대값 + 1장 ..

문제 문제해결 - 정수 1을 1, 2, 3의 합으로 나타내는 방법은 1 총 1개 - 정수 2를 1, 2, 3의 합으로 나타내는 방법은 1 + 1 2 총 2개 - 정수 3을 1, 2, 3의 합으로 나타내는 방법은 1 + 1 + 1 1 + 2 2 + 1 3 총 4개 - 그렇다면 정수 4를 1, 2, 3의 합으로 나타내는 방법은 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 (4) 2 + 1 + 1 2 + 2 (2) 3 + 1 (1) 이렇게 4 + 2 + 1 = 7가지다, 잘 보면 1 + 우측에는 3을 나타내는 경우의 수(4) 2 + 우측에는 2를 나타내는 경우의 수(2) 3 + 우측에는 1을 나타내는 경우의 수(1) 즉 3의 경우의수 + 2의 경우의 수 + 1의 경우의 수인것을 볼수..

운영체제 - 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프투웨어와 하드웨어를 연결하는 소프트웨어 계층 - 좁은 의미로는 커널이라고 함 - 넒은 의미로는 커널뿐 아니라 주변 시스템 유틸리티까지 포함 목적 - 하드웨어를 효율적으로 관리 자원: 프로세서, 기억장치, 입출력 장치 등 사용자간 형평성 있는 자원 분배 및 주어진 자원으로 최대한의 성능을 내는 것이 목표 - 컴퓨터 시스템을 효율적으로 관리(소프트웨어) - 여러 사용자가 하나의 컴퓨터를 사용해도 각자 다른 컴퓨터를 사용하는 듯한 느낌을 들게해줌 운영체제의 분류 - 동시 작업 가능 여부 1. 단일 작업: 한번의 하나의 작업만 처리, MS-DOS 2. 다중 작업: 동시에 두개 이상의 작업 처리, 리눅스, 윈도우 - 사용자 수 1. 단일 사..

문제 문제해결 - 1*2 와 2*1의 타일로만 채우는 문제에서는 dp[i-1] 에 세로 타일 하나 추가한 경우의 수 + dp[i-2] 에 가로 타일 두개 추가한 경우의 수를 구하면 되었다 - 이 문제의 경우 2*2 타일이 있으므로 dp[i-1] 에 세로 타일 하나 추가한 경우의 수 + dp[i-2] 에 가로 타일 두개 추가한 경우의 수 + dp[i-2]에 2*2 타일 하나 추가한 경우의 수 - dp[i] = dp[i-1] + dp[i-2] + dp[i-2] - dp[i] = dp[i-1] + dp[i-2] * 2 - 피보나치 수열 구하는 방법이랑 똑같이 하되 점화식만 바꿔주면 된다 import java.util.Scanner; //dp[i] = dp[i-1] + dp[i-2] * 2 public clas..

문제 문제해결 - 1*2와 2*1의 직사각형으로 2*n을 만들 수 있는 경우의 수는 1, 2, 3, 5, 8.... - 2*3의 직사각형을 만들기 위해선 모든 2*2 직사각형에(dp[i-1]) 세로 타일 하나 추가 한 경우의 수 + 모든 2*1 직사각형에(dp[i-2]) 가로 타일 두개 추가한 경우의 수 즉 dp[i] = dp[i-1] + dp[i-2] - 2*0을 제외하고 보면 피보나치 수열임을 알수있다 - 2*0일 경우를 임의로 1로 설정하면 피보나치 수열 해결 방식으로 문제 풀이가 가능하다 - 피보나치 수열의 경우 n이 증가함에 따라 값이 기하급수적으로 커지므로 10007이라는 값을 항상 나눠줘서 overflow가 안나게 한다 import java.util.Scanner; //피보나치 수열 publ..