한번 꼬여서 계속 덮어뒀던 문제,,, 새롭게 시작하니 생각보다 되게 간단하게 풀렸다,,,! Problem https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 문제를 요약하자면, 한번 작동할 때 앞서 이동한 거리가 k광년이면 k-1, k, k+1광년만큼을 이동할 수 있는 우주선이 있다. 해당 우주선을 이용해 이동을 할 것이다. 예를 들어 우주선을 처음 작동할 때는 무조건 1광년만큼을 이동할 수 있으며 도착..

https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 가장 기본적이게 보이는 하노이 탑 문제이다. 우선 내가 이문제를 해결할 방식은 다음과 같다. N층의 하노이 탑을 N-1층의 하노이탑 문제를 해결할 수 있도록 함. 즉 재귀로 구현할 수 있을 것이다. 이런 과정을 거치면 우선 N층의 이동 횟수는 ( N-1층 이동 횟수 ) * 2 + 1 이다. 위 내용들을 바탕으로 코드 구현 ( ** 정답 아님 ** ) #include using namespace st..

분할 정복: 큰 문제를 작은 문제로 나누어 각각을 해결하고 다시 병합하는 방식으로 문제를 해결하는 방식.1. DIvide : 큰 문제를 작은 문제들로 나눈다.2. Conquer : 작은 문제를 더 나눌 수 있으면 더 작은 문제로 나누고, 나눌 수 없으면 문제를 해결한다.3. Merge : 작은 문제를 합하면서 큰 문제를 해결한다.  분할 정복의 조건1. 큰 문제를 작은 문제로 나누어도 큰 문제와 해결 방식이 같아야함. ( 작은 문제로 나누어도 문제의 해결 방식이 동일해야함 )2. 쪼개진 문제 간의 연관이 없어야함. 작은 문제가 다른 작은 문제에 영향을 미치면 안됨.  대표적인 예시로 Merge Sort가 있다.  오늘 내가 이 글에서 주목하고자 하는 것은 분할정복을 통한 거듭제곱의 해결이다.[ 백준 C+..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 치킨배달과 굉장히 비슷한 문제라고 느껴진다. https://chhggg.tistory.com/28 [백준 C++] 15686 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태 chhggg...

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 우선, "최대 M개"라는 워딩이 매우 신경쓰인다. 무조건 M개만 남기고 없애는 게 아니라 막,, M-3개를 남기는 게 더 효율적일 수 도 있나?라는 생각을 했음 → 그럴리 없다. 무조건 M개여야 치킨거리가 가장 작다!! 우선 정답 코드는 바로 아래 코드이다. #include using namespace std; typedef long long ll; ll n, m, tmp; ..

어렵다 어려워……. 모르겠어……. Abstracting Physical Resources ✔️ OS가 충족해야하는 조건 1. Time-sharing : 여러 프로세스가 한정된 하드웨어(H/W) 자원을 time-sharing하며 사용할 수 있어야함 → 프로그램이 주기적으로 H/W를 양보한다면 굳이? 필요없을 것. 하지만 악의적으로 독점한 채 양보하지 않으면 다른 프로그램은 영영 H/W를 사용하지 못할 것임. 따라서 UNIX는 주기적으로 프로그램이 H/W 자원을 양보하도록 만듬. 2. Isolation : 한 프로세스의 bug나 fail이 다른 프로세스에 영향을 주면 안됨 → 직접 H/W에 접근하는 것보다 추상화된 H/W에 접근하는 것이 여러방면에서 좋음. Ex, 프로세스는 시스템콜을 사용하여 H/W에 접근..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리 구현... #include using namespace std; typedef long long ll; ll n, m, k; //수의 개수, 수의 변경 횟수, 구간의 합 구하는 횟수 ll SegmentTree[4000004]; ll arr[1'000'000 + 10]; ll a, b, c; ll make_SegmentTree..

운영체제는 하나의 물리 메모리(RAM)를 이용해 모든 프로세스를 관리한다. → 효율적으로 관리해야 함(특정 프로세스가 다른 프로세스가 로드한 데이터를 읽지 못하게 해야함) 페이징 ⇒ 메모리를 고정된 크기의 페이지로 나누어 관리하는 것. ✔️ 레지스터에 시작주소를 담아서 사용하기에는 어찌됐든 그 내용을 담을 연속된 메모리 영역이 필요하다. 연속된 메모리 영역을 확보하는 것이 어렵기에 (외부 단편화) 프로세스의 물리 주소가 연속되지 않아도 되도록 하는 것. 페이지 테이블을 이용하여 논리메모리를 실제 메모리로 변환하여 실제 메모리에 접근. (일반적으로 물리메모리는 동일한 크기의 프레임으로, 논리 메모리는 동일한 크기의 페이지로 나눔) 페이징을 통해 외부 단편화의 필요성을 피할 수 있음 외부 단편화란? 메모리의..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 단순히 infix에서 postfix로 변환하는 문제이다. 스택을 이용해 해결 가능할 듯하다. 모든 식이 괄호로 묶여있는 것이 아니므로 연산자의 우선순위를 고려해서 하면 될 듯하다. infix를 한글자씩 읽으면서 진행 1) 피연산자 -> 바로 출력 2) '(' -> 스택에 push 3) * or / -> 본인과 우선순위가 같은 연산자 (* or /)가 스택에 있으면 pop해서 출력 (+ or -..

Sleep Implement the UNIX program sleep for xv6; your sleep should pause for a user-specified number of ticks. A tick is a notion of time defined by the xv6 kernel, namely the time between two interrupts from the timer chip. Your solution should be in the file user/sleep.c #include "kernel/types.h" #include "kernel/stat.h" #include "user/user.h" int main(int argc, char *argv[]){ if(argc < 2){ fpr..