mumu의 일기

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1차원 BFS문제이다. 2,3 차원 문제를 풀때는 보통 각 방향을 담은 배열을 만들어서 탐색하지만 1차원은 그냥 범위기반for문으로 탐색하는게 깔끔하다. 어떻게 이동하는지도 출력해야 하므로 경로를 저장하는 배열도 하나 추가해주었다. 구현 문제 조건대로(1초마다 +1 -1 *2) 탐색을 계속 해준다. 탐색을 하는 동시에 경로도 check배열에 저장해가면서 탐색을 해..

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 2차원 BFS문제다. 불의 경우를 먼저 탐색하고 상근의 경우를 탐색한후 거리를 비교해서 판단한다. 구현 방법 '*' 좌표에서 탐색을 시작하기 위해 해당 좌표를 큐(QF)에 넣음. '@' 좌표에서 탐색을 시작하기 위해 해당 좌표를 큐(QS)에 넣음 큐(QF)에서 원소를 꺼내 우측, 좌측, 전방, 후방, 위, 아래 인접한 칸에 대해 4번 탐색함. 해당 칸이 범위 밖인경우, 방문했거나(거리가 0 이상) 벽인경우('..

3차원 BFS(너비 우선 탐색 알고리즘)문제이다. BFS(너비 우선 탐색) DFS (깊이 우선 탐색)모두 그래프를 탐색하는 알고리즘이다. 자세한 설명은 다른 게시물에서 후술하기로 하고 간단하게 BFS와 DFS의 차이점을 탐색 순서를 나타낸 그림으로 보자. https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 구현방법 'S' 좌표에서 탐색을 시작하기 위해 해당 좌표를 큐에 넣음. 큐에서 원소를 꺼내 우측, 좌측, 전방, 후방, 위, 아래 인접한 칸에 대해 ..

운영체제는 프로세스의 상태를 PCB(프로세스 제어 블록)를 통해 인식하고 관리함. 프로세스의 상태 생성상태(new) 프로세스를 생성 중인 상태. 생성 상태를 통해 준비가 완료된 프로세스는 준비상태가 되어 cpu의 할당을 기다리게 됨. 준비 상태(ready) cpu할당을 기다리는 상태로, 차례대로 cpu의 할당을 받음. 실행 상태(running) cpu를 할당받아 실행 중인 상태. 타이머 인터럽트가 발생하면 다시 준비상태. 실행 도중 입출력장치를 사용하여 작업을 기다려야 한다면 (특정 이벤트가 일어나길 기다릴 때) 대기 상태로 전환. 대기 상태(blocked) 입출력장치의 작업을 기다리는 상태. 입출력 작업이 완료되면 다시 준비 상태로 전환. 종료 상태(terminated) 프로세스가 종료된 상태. 운영체..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 처음 풀어본 최장 공통부분 수열 문제였다. ACAYKP와 CAPCAK 처럼 공통부분 수열 이므로 띄엄띄엄 있어도 괜찮다. 구현 방법을 알아보자. ACAYKP와 CAPCAK를 입력받는다. 먼저 CAPCAK의 C와 ACAYKP를 하나하나 비교한다. 먼저 비교한 문자가 같은 경우 이전까지의 과정에 + 1을 해주면 된다. 점화식으로 본다면 arr[j-1][i-..

프로세스란,,, 간단히 말하면 실행중인 프로그램이다. 보조기억장치에서 프로그램이 메모리에 적재되고 실행되면 프로그램은 프로세스가 된다. 현재 실행되고있는 프로세스는 작업 관리자 창에서 쉽게 확인할 수 있다. 우리가 볼 수 있는 공간에서 실행되는 프로세스를 포그라운드 프로세스라고 한다. 반면 사용자가 볼 수 없는 공간에서 실행되는 프로세스를 백그라운드 프로세스라고 하면 윈도우에서는 서비스 라고 부른다. 기본적으로 프로세스를 실행하는 프로세서(CPU)는 한번에 하나의 일만 처리할 수 있다. 프로세스를 효율적으로 번갈아가며 사용하기위해 운영체제는 프로세스 제어 블록(PCB)을 이용한다. 프로세스 제어 블록(PCB) PCB는 프로세스와 관련된 정보를 저장하는 자료구조로, 해당 프로세스를 식별하기 위한 정보들이 ..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net DP문제가 다 그렇지만,,, 규칙을 찾는데 시간을 좀 썼다. 가장 큰 정사각형의 넓이를 찾는 문제다. 정사각형의 넓이를 구해야 하니 한 변의 길이를 구해도 좋을것이다. 위 경우는 가장 큰 정사각형의 넓이는 1이다. 빨간 숫자는 map[i][j]의 값으로 해당 위치(i, j) 가 정사각형의 우측 하단인 경우 정사각형 한 변의 길이이다. 해당 경우는 가장 큰 정사각형 한 변의 길이는 2이다. 이제 슬슬 규칙이 보일것이다. map[i][j] 에서의 정사각형 한 변의 길이는..

전공 수업중 "main함수는 뭐고 왜 return 0; 를 해주는거에요?" 라고 질문을 받았을때 나는 명확하게 답하지 못하고 프로그램이 실행되는 함수라고만 설명하고 넘어간적이 있었다. 이번 기회에 명확하게 정리하고자 이 글을 쓴다. 내가 평소에 생각하고있던 C/C++의 main 함수에 대해 적어보자. 프로그램의 실행을 위한 함수다. return에 의해 종료된다. int와 void를 리턴한다. 우선 main 함수는 응용 프로그램을 실행하면 운영체제에 의해 (해당 응용 프로그램의 부모 프로세스)처음 실행된다. 즉 프로그램의 시작점이다. 모든 프로그램은 main함수를 하나 가지고 있어야한다. 처음 공부를 시작한 사람들이 실수하는 경우가 있는데(나도 처음에 이런 실수를 했다), 위와 같은 이유로 프로젝트 내에는..