전체 글

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 1. Logic 기본적인 BFS문제이다. 처음 방문하는게 가장 최단거리기 때문에 vis배열을 통해 queue에 들어가는 갯수를 줄여주면서 BFS를 진행하면 된다. 2. Code c++ #include using namespace std; int n; int arr[1001]; bool vis[1001]; int bfs() { queue q; int ans = 0x3f3f3f3f; q.p..

https://www.acmicpc.net/problem/1270 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n n; while(n--) { unordered_map land; long long cur; cin >> cur; long long landNum; long long maxNum = -1; for(int i = 0; i > num; land[num]++; if(land[num] > maxNum) { maxNum = land[num]; landNum = num; } } if(maxNum > cur/2) cout

https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 1. Logic deque를 사용해서 풀이해줬다! 2. Code #include using namespace std; int main() { deque dq; int n; cin >> n; for(int i = n; i > 0; i--) { dq.push_back(i); } while(!dq.empty()) { cout

https://www.acmicpc.net/problem/2446 2446번: 별 찍기 - 9 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 1. Logic 별찍기는 재밌어! 2. Code #include using namespace std; int main() { int n; cin >> n; for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { cout

https://www.acmicpc.net/problem/1487 1487번: 물건 팔기 첫째 줄에 최대 이익을 만들어주는 가격을 출력한다. 이익이 최대인 가격이 여러개라면, 가장 낮은 가격을 출력한다. 또, 어떤 가격으로 팔아도 이익을 남길 수 없다면 0을 출력한다. www.acmicpc.net 1. Logic n의 범위가 50이기 때문에 완탐을 돌려도 시간복잡도가 안넘는다! 먼저 입력을 받은 후 입력값을 오름차순으로 정렬한다. 그럼 작은 가격부터 기준을 잡고, 기준으로부터 배열끝까지 돌면서 가격을 계산한다. 모든 수를 다 돌게되면 시간복잡도도 넘을 뿐더러, 기준보다 작으면 선택받지 못하기 때문에 무조건 선택받을 수 있게 배열의 가격을 기준으로 잡는것이다. 가격의 기준을 잡는 부분이 첫번째 for문에 ..

https://www.acmicpc.net/problem/2444 2444번: 별 찍기 - 7 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 1. Logic 별찍기 구현! 2. Code #include using namespace std; int main() { int n; cin >> n; for(int i = n-1; i >= 0; i--) { for(int j = 0; j < i; j++) { cout

1. Paging Paging이란 프로그램을 일정한 크기의 페이지 단위로 나눠서 실제 메모리에 불연속적으로 할당하는 방법을 말한다. 페이지는 4KB, 8KB, 16KB, 32KB 등으로 설정되지만 일반적으로는 페이즈의 크기를 4KB로 사용한다. 이 글에서도 4KB로 생각하면 된다. 페이지 크기가 줄어들수록 내부 조각이 적어지지만 페이지 테이블의 크기가 증가하고 반대로 페이지 크기가 크면, 내부 조각이 많이 생기지만 페이지 테이블의 크기는 줄어든다. 여기서 페이지(Page)와 프레임(Frame) 두 가지 용어를 먼저 알고 가자. 페이지(Page) : 논리적인 메모리(프로세스의 가상 주소)를 일정한 크기로 나눈 것 프레임(Frame) : 실제 물리적인 메모리(RAM)를 일정한 크기로 나눈 것 페이지는 가상 ..

Contiguous allocation 1. 고정 분할 방식 이름 그대로 메모리를 분할해놓고, 프로그램이 분할된 메모리의 크기와 맞으면 할당하고 크기가 안맞으면 크기가 맞는곳에 할당을 하는 방식이다. 프로그램 A를 보면 분할 1의 크기에 맞기 때문에 할당할 수 있다. 하지만 프로그램 B를 보면 분할 2의 사이즈보다 크다. 그렇기 때문에 분할 2를 건너뛰고 프로그램A와 크기가 맞는 분할 3 메모리에 할당되게 된다. 이때 분할2번은 건너 뛰게 되는데 이를 "외부 조각"이라고 부른다. 분할 3 내부에서도 프로그램 B가 분할 3메모리를 다 채우지 못했는데, 채우지 못한 부분을 "내부 조각"이라고 부른다 보면 알겠지만 상당히 비효율적이고, 내부 조각, 외부 조각이 발생할 수 있다. 2. 가변 분할 방식 가변 분할..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 1. Logic 크루스칼 알고리즘을 활용해서 풀이했다. 이 문제를 풀 때 핵심은 두 행성을 연결할 떄 드능 비용이 min(|x1-x2|, |y1-y2|, |z1-z2|)라는 지문에서 찾을 수 있다. x, y, z의 좌표차가 가장 작은 값이 두 사이의 거리라는 뜻이다. 그러므로 각 x, y, z좌표를 받은 후 정렬을 하게 되면 배열의 앞뒤에 있는 좌표가 가장 차이가 ..

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 1. Logic DDR에서 이전에 갔던 곳을 똑같은 경우의 수로 갈 수 있기 때문에 메모이제이션을 활용하여 풀이했다. 규칙이 직관적으로 보여서 topdown으로 풀이하기 쉬웠다. 밟고 있던 위치를 다시 밟을경우 +1 처음 시작점인 0의 위치에서 움직일 경우 +2 인접한 위치로 움직일 경우 +3 반대편으로 움직일 경우 +4 처음에는 모든 경우의 수를 다 세줘서 보기..