문제 이해 단계 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net N개의 앱이 존재한다. N개의 앱에는 2가지 정보가 들어있는데, (사용 중인 메모리의 바이트 수, 비활성화했을 때의 비용) 2가지이다. M 바이트를 확보해야 하기 때문에, N개의 앱 중 몇 가지를 골라서 비활성화해야 한다. 이때 비활성화 했을 때의 비용을 최소화하여 M 바이트를 확보해야 한다. 최소 비용일 때를 출력하는 문제 문제 접근 단계 제한 사항 분석 앱의 개수(N)는 최대 100개..

문제 이해 단계 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net NxM 크기의 맵이 존재하고, 빨간 구슬과 파란 구슬이 존재한다. 맵의 테두리는 모두 벽으로 막혀있고, 하나의 구멍이 존재한다. 목표는 파란 구슬은 구멍은 남겨둔 채, 빨간 구슬을 구멍을 통해 빼내는 것. 할 수 있는 동작은 상하좌우로 기울이는 것이다. 기울인다는 것은 해당 쪽에 벽에 닿을 때까지 쭉 흐른다는 것. 예를 들어, 오른..

구현해 보는 이유 C++ 헤더 에 lower_bound와 upper_bound 함수가 있다. 근데 있는 거 두고 굳이 왜 직접 구현해 보는 걸까? 이유는 총 2가지이다. 1. 학습적인 목적(이진탐색 구현) 2. 이진 탐색 변형 이 목적으로 한번 구현해 본다. lower_bound와 upper_bound 메서드 lower_bound lower_bound는 찾고자 하는 값보다 크거나 같은 값이 처음 나타난 곳의 인덱스를 반환한다. 예를 들어서, {2,4,6,7,9}에서 lower_bound를 사용하여 2를 찾는다면 배열에서 2의 인덱스인 0을 반환한다. 또한 5를 찾는다면, 처음으로 5보다 큰 6의 인덱스인 2를 반환한다. upper_bound upper_bound는 찾고자 하는 값보다 큰 값이 처음 나타난..

문제 이해 단계 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20 30,50}이고, 길이는 4이다. 문제 접근 단계 특이점 알아내기 가장 긴 ~ 부분 수열 시리즈 문제 항상 비슷하면서 풀이가 다른 게 해당 시리즈 특징이다. 일단 수열..

임계구역 문제를 해결하기 위한 지원을 제공하는 세 가지 하드웨어 명령어를 제시 메모리 장벽(Memory Barriers) 메모리 모델 컴퓨터 아키텍처가 응용프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식 일반적으로 두 가지 범주 중 하나에 속함 강한 순서 : 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임 약한 순서 : 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음 메모리 모델은 프로세서 유형에 따라 다름 → 커널 개발자는 공유 메모리 다중 처리기에서 메모리 변경의 가시성에 대한 가정 불가 → 이러한 문제를 해결하기 위해 메모리 장벽을 사용 메모리 장벽 : 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어 이를 통해 다른 프로세서에서..

동기화 도구들이 왜 필요할까? 협력적 프로세스가 데이터를 공유하는 방법 협력적 프로세스 : 시스템 내에 실행 중인 다른 프로세스에게 영향을 주거나 받는 프로세스 논리 주소 공간(코드, 데이터)을 직접 공유, 공유 메모리, 메시지 전달 → 공유 데이터를 동시에 접근하면 데이터의 일관성을 망칠 수 있음 데이터의 일관성을 유지하기 위해 논리 주소 공간을 공유하는 협력적 프로세스의 질서 있는 실행을 보장 프로세스가 병행 또는 병렬로 실행될 때 공유하는 데이터의 무결성에 문제를 일으킴 문제가 발생하는 예시 static int count = 0; // 전역 변수 // 스레드 t1은 count를 1씩 더함 Task t1 = new Task(() => { for (int i = 0; i < 10000; i++) cou..

문제 이해 단계 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048이라는 게임이 존재한다. 이 게임 상하좌우 이동 중 하나를 고르는데, 한번 이동할 때 모든 블록이 해당 방향으로 벽이나 다른 블록에 부딪힐 때까지 움직인다. 이때 같은 값을 가지는 두 블록이 충돌하면 두 블록은 하나로 합쳐지면서 값도 하나로 합쳐진다. 한 번 이동할 때 이미 합쳐진 블록은 다른 블록과 다시 합쳐질 수 없다. 이러한 게임에서, Nx..

문제 이해 단계 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 높이 h와 너비 w를 가진 2차원 맵이 존재한다. 여기서 원하는 것은 문서를 최대한 많이 획득하는 것이다. '. ' : 빈 공간 ' * ' : 벽 ' $ ' : 문서 알파벳 대문자 : 잠겨 있는 문 알파벳 소문자 : 열쇠 해당 문자의 대문자에 해당하는 문을 열 수 있음 처음에는 빌딩 밖에 있고, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 그리고 같은 열쇠를 여러 번 사..