https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. Logic 먼저 이 문제를 풀기 위해서는 2차원 배열에서 누적합을 구하는 방법을 알아야 한다. 2차원 배열에서 누적합을 구하는 점화식을 먼저 보자 prefixSum[i][j] = prefixSum[i][j] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] 예시로 (2,2)의 누적합을 구하..
분류 전체보기
1. CPU scheduling이란? CPU는 한번에 하나의 프로세스만을 수행할 수 있다. 여러개의 프로세스가 있어도 현재 CPU가 실행하고 있는 프로세스가 끝날때 까지 기다려야한다. 또한 I/O요청이 들어올 경우 CPU는 들어온 I/O요청이 끝날 때 까지 기다린 후 I/O가 끝나면 다시 실행된다. 즉, 다른 프로세스들을 실행하지 못하고 무한 대기하고 있기 때문에 대시 시간만큼 CPU를 낭비하는 것이다. 이를 해결하기 위해 멀티 프로그래밍 환경에서 CPU를 효율적으로 사용하기 위해 I/O요청이 오면 다른 프로세스한테 CPU를 양도하고 I/O가 끝나면 다시 Ready-queue에 들어가서 실행을 준비하고 실행하고 이런 CPU를 효율적으로 사용하기 위한 방법을 Scheduling이라고 한다. 2. CPU I..
https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 1. Logic DP를 푸는 방법은 늘 그렇듯 부분문제를 쪼개는게 핵심이다. 이 문제에서 부분문제를 생각해보면 파일을 어떻게 나눌건지를 생각해야된다. 문제에서 나온 테스트케이스를 보면 40 30 30 50이다. 여기서 파일의 순서를 임의로 바꿀 수 없는것을 유의하면 부분문제는 총 3가지로 볼 수 있다. 나누는 부분을 보면 아래와 같다. 40 / 30 30 50 40 30 / 30 50 4..
https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 1. Logic 11066번 파일합치기 DP문제를 풀다가 누적합이라는 개념을 알게되어 공부할 겸 풀어봤다. 물론 이문제는 누적합 없이도 풀리긴 한다. 아래 행렬의 누적합을 구해보자 y\x 1 2 3 1 1 2 4 2 8 16 32 나는 처음에 행렬의 누적합은 당연히 다 1,1에서 해당 좌표까지 다 더하는 줄 알았다 그래서 내가 생각한 누적합은 아래와 같았다ㅋㅋㅋㅋ y\..
1. Implicit Threading이란? 스레드를 개발자가 명시적으로 생성하거나 제어하지 않고 언어나 프레임워크에게 스레드의 생성과 관리 책임을 넘기는 것. 개발자는 따로 스레딩을 생성할 필요없이 병렬로 실행해야 할 프로그램을 걸러내어 함수형으로 실행만 시켜주면 된다. 2. Implicit Threading의 종류 2-1. Thread pool / 스레드 풀 프로세스 사용? 스레드 사용? 프로세스를 스케줄링 하는 것보다 스레드를 만들어 사용하는 게 자원 소비, 오버헤드 관점에서 훨씬 효율적인 방법이긴 하다. 이유는 프로세스 간 통신을 할 경우 shared-memory또는 Message passing같은 IPC방식을 사용해야 하기 때문에 오버헤드가 크고 context switch를 할 때 프로세스는 레..
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 1. Logic 단순 BFS를 돌아서 갯수를 세주면 된다. 2. Code #include using namespace std; int graph[101][101]; bool vis[101][101]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; int n, m, k; int bfs(int yy, int xx) { queue q..
1. 빈이 중복 조회되는 상황 현재 실습하고 있는 예제에서 상품을 주문했을 때 할인 정책을 DiscountPolicy라는 interface를 구현해서 사용하고있다. 이럴 때 DiscountPolicy 인터페이스 구현체는 고정 할인 fixDiscount와 할인률을 정해서 할인해주는 rateDiscount두개가 있다. orderServiceImpl에서 DIP를 지키기 위해 생성자 주입을 통해 인터페이스 타입 파라미터로 의존성을 주입받으려 할 때 현재 빈에는 fixdiscount와 rateDiscount 두개의 DisountPolicy 타입 빈이 등록돼있다. 스프링이 의존성 주입을 할 때 주입 대상을 타입 기준으로 조회를 하기 때문에 현재 상황에서는 DiscountPolicy 구현체 두개가 조회되어 expec..
https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 1. Logic 입력을 받은 후 물건이 있는 좌표를 받으면 0~5까지의 char타입으로 변경해서 넣어줬다. BFS를 돌면서 입력 받을 때 char타입으로 변경해서 넣어준 물건을 만나면 다시 int타입으로 변경해서 shift연산을 통해 비트계산을 해서 몇번째 물건을 집었는지 기록한다. BFS를 돌면서 E(출구)를 만났을 때 내가 받은 물건과 도착한 시점에서의 물건갯수가 일치하면 걸린시간을 리..
https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 1. Logic 열쇠가 6개밖에 없기때문에 비트로 표현 가능하다. 큐에 현재 열쇠를 모은 상태를 비트로 저장해서 관리해준다. 이 문제에서 나눠질 부분문제를 생각해보면 1. 열쇠를 만날경우 - 현재 열쇠를 모은거와 지금 열쇠를 or연산하여 모은 상태를 구하고 모았던 열쇠면 다시 갈 필요 없기 때문에 건너뛰고 안모은 열쇠면 갱신한 열쇠 컬렉션 상태를 큐에 넣어준다. 2...
https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 1. Logic 구현은 어렵지 않은문제인데 실수하기 쉬운 문제인 것 같다. 1. 입력을 받고 공기청정기가 있는 위치의 y좌표를 저장해둔다. 2. 미세먼지의 합을 더할 임시 배열에 먼지를 /5한 값을 4방향으로 더해준다. 3. 이전 먼지 배열과 임시배열을 더해줌과 동시에 0으로 초기화해준다. 2. Code #include using namespace std; int r, c, t; int dust..
