문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 설명 N과 M(1)이 백트래킹을 이용한 순열 문제라면 N과 M(2)는 백트래킹을 이용한 조합 문제이다. 조합은 순서가 상관없다. 또한 오름차순으로 구하게되면 이전에 했던 문제와 달리 중복 체크가 필요 없다. 처음에 combination(0,1)을 호출하는데, 이후에는 combination(cnt+1, i+1)을 호출한다. 오름차순으로 구하면 중복체크 하지 않아도 되므로, visited 배열..

문제 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 가장 기본적인 백트래킹 문제이다. func라는 함수의 역할은, k번째 수를 정하는 것이다. k번째 수를 정하고, k+1의 수를 재귀적으로 정해준다. 코드 package algo0314; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class B15649_N과M1 {..

https://www.acmicpc.net/problem/9742 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 백트래킹을 사용한 문제. 테케 갯수가 정해져 있지 않기에 읽은 라인이 null일때까지 반복 package algo0314; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class B9742_순열 { static..

CPU 스케줄링이 필요한 경우 Running→Blocked(예: I/O요청하는 시스템 콜) Running→Ready(예: 할당시간 만료로 timer interrupt) Blocked→Ready(예: I/O완료 후 인터럽트)(선점형일 때) Terminate→Running→Blocked와 Terminate에서의 스케줄링은 nonpreemptive(비 선점형)→나머지 경우는 preemptive(선점형)→ 현대적인 cpu 스케줄링은 대부분 선점형 스케줄링을 사용 Scheduling Criteria (Scheduling Algorithm 의 성능 척도) CPU utillization(이용률)→시스템 입장에서 성능척도(cpu 하나가지고 최대한 일을 많이 시키면 좋음) 전체 시간중 cpu 가 놀지 않고 일한 시간 비..

12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 슬라이딩 윈도우 사용! 첫 슬라이딩 윈도우 생성 - 입력받은 문자열의 0~p-1번째 요소에 A,C,G,T가 있는지 확인 후 정답 계산 첫 슬라이딩 윈도우 생성 이후 s-p개의 부문 문자열 생성 가능 → for문을 통해 모든 부분 문자열 검사. 한 칸씩 이동하면서 검사 가능. 이전 부분문자열의 시작은 빠지고, 추가될 부분은 더해져야함. idx = i (이전 부분 문자열의 시작 인덱스), idx = i+p (이전 부분 문자열의 시작 인덱스 + ..

2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 두개의 포인터를 활용하여 시작 인덱스와 끝 인덱스를 지정하여 합이 N이 되는 경우의 수를 구합니다. 합 N : s이동(s+1), 감소 합 == N : count+1 , s+1 pseudo-code /*pseudo-code*/ N // 목표 합 start = 1, end = 1 //시작, 끝 자연수 (포인터) count = 0, sum = 1 //개수, start 부터 end까지 연속된 자연수의 합 w..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 백준 문제 11659 - 구간합 구하기의 2차원 버전 arr하나로도 구현 가능 하나, 일단 두개의 배열로 진행. 배열을 입력받아 arr에 저장 d라는 2차원 배열에 구간 합 저장. (이때 공식: d[i][j] = d[i][j-1]+d[i-1][j]-d[i-1][j-1]+arr[i][j]) (x1,y1)과 (x2,y2)를 입력받고, ans = d[x2][y2]-d[x2][y1-1]-d[x1-1][y2]+d[x1-1][y1-..

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 처음에 이중 for문으로 배열을 다 탐색하며 계산을 했으나 시간 초과 발생. 이전에 구한 값을 앞으로 구할 값에 사용 가능 → DP로 구현 가능. BufferedReader, StringTokenizer, nextToken으로 구현하는 것이 Scanner 쓰는 것 보다 훨씬 빠르다. 후기-> C++이랑 파이썬 쓰다가 자바로 코딩하려니까 적응이 안되는데.. 자바가 생각보다 실행시간도 길고 함수 사용도 복잡해서 적응하는데 시간이 좀 걸릴 것 같..

스케줄러 한정적 메모리를 여러 프로세스가 효율적으로 사용할 수 있도록 다음 실행 시간에 실행할 수 있는 프로세스 중에 하나를 선택하는 역할 프로세스들은 자신이 종료될 때까지 수많은 큐들을 돌아다닌다. OS는 이 큐 안에 있는 프로세스 중 하나를 선택해야 하며, 이러한 일을 스케줄러(Scheduler)가 담당한다. 프로세스 스케줄링 위한 Queue의 종류 작업 큐(Job Queue) : 현재 시스템 내의 모든 프로세스의 집합 준비 큐(Ready Queue) : 현재 메모리 내에 있으면서 CPU를 할당받고 실행되기 위해 기다리는 프로세스의 집합 장치 큐(Device Queue) : 각각의 장치마다 서비스를 기다리며 줄 서 있는 프로세스의 집합 스케줄러의 목적 - CPU나 자원을 효율적으로 사용하기 위함 - ..

클래스 멤버 변수, 인스턴스 멤버 변수 구분하기 인스턴스 변수는 인스턴스가 생성될 때마다 생성되므로 인스턴스마다 각기 다른 값을 유지할 수 있지만, 클래스 변수는 모든 인스턴스가 하나의 저장공간을 공유하므로 항상 공통된 값을 갖는다. 변수의 종류 선언위치 생성시기 클래스 변수 클래스 영역 클래스가 메모리에 올라갈 때 인스턴스 변수 인스턴스 생성되었을 때 지역변수 클래스 영역 이외의 영역 (메서드, 생성자, 초기화 블럭 내부) 변수 선언문이 수행되었을 때 클래스 멤버 변수 : static 키워드 사용. 클래스를 통해 접근 클래스 영역에 클래스 로딩되는 시점에 메모리에 생성 프로그램 종료시 삭제 인스턴스 멤버 변수 : static 키워드 사용 X. 객체를 통해 접근 배열처럼 자동 초기화. 힙 공간에 만들어짐..