전체 글

(C++) 백준 1074번 - Z

풀이 재귀를 이용하여 풀이하였다. 2의 거듭제곱으로 커져가기 때문에 한 변의 길이가 2, 4, 8, 16, ... 순으로 증가한다. 그렇기 때문에 한 변이 2일 때를 재귀를 종료하는 base condition으로 두고, 사각형들을 4개로 분할하여(한 변의 길이를 2배씩 줄여) 나가면서 풀었다. #include using namespace std; int calZ(int n, int r, int c){ if(n == 1){ // 2 * 2 일 때 if(r == 0 and c == 0) return 0; else if(r == 0 and c == 1) return 1; else if(r == 1 and c == 0) return 2; else return 3; } int half = (1= half and ..

(C++) 백준 11729번 - 하노이 탑 이동 순서

문제 링크 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 재귀 문제의 대명사격인 하노이 탑 문제이다. s에서 l로 n개를 이동하려면 다음과 같은 과정을 거치면 된다. 1. 제일 아래에 있는 가장 큰 판을 제외한 n-1개의 판을 s에서 6-s-l로 이동시킨다. 2. 제일 큰 판을 s에서 l로 이동시킨다. 3. 1에서 6-s-l로 이동한 n-1개의 판을 l로 이동시킨다. 이 과정을 재귀로 반복하여 문제를 풀이하였다. #inc..

(C++) 백준 1629번 - 곱셈

문제 링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 재귀를 활용하여 풀이하였다. "n의 k승을 알면, n의 2k승과 n의 2k+1승을 알 수 있다."는 사실과 "(a x b) % k = (a % k) x (b % k)"라는 사실을 활용하여 풀이를 진행하였다. #include using namespace std; using ll = long long; int power(ll a, ll b, ll c){ if(b == 0) return 1; // 모든 수의 0승은 1 if(b == 1) retur..

(C++) 백준 1697번 - 숨바꼭질

문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 응용한 문제로 실버 1 문제치곤 어렵지 않게 해결할 수 있다. 다만 조건에 수빈이와 동생이 같은 위치에 있을 순 없다는 말이 없으므로 같은 위치에 존재하면 그냥 0을 출력하고 종료할 수 있도록 해야 한다. #include #include #include #define X first #define Y second using namespace s..

(C++) 백준 4179번 - 불!

문제 링크 : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 풀이 BFS를 응용한 문제로, 불에 대한 BFS와 지훈이에 대한 BFS를 동시에 사용하는 방법으로 풀이하면 된다. 골드 4 문제답게 조건들을 설정하는 것이 매우 복잡했다. #include #include #include #define X first #define Y second using namespace std; int dx[4] = {1,0,-1,0}; int d..

(C++) 백준 7576번 - 토마토

문제 링크 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 BFS를 이용한 거리 문제와 비슷하게 풀이하면 된다. 거리를 토마토가 익는 데 걸리는 시간의 길이라고 생각하고 풀면 어렵지 않게 해결할 수 있다. 문제 해결 시 중요한 점은 시작점이 될 수 있는 후보들, 즉 익은 토마토들의 위치를 먼저 파악 후에 이들을 Queue에 넣고 시작해야 한다는 점이다. #include #include #include #define X ..

(C++) 백준 2178번 - 미로 탐색

문제 링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 BFS를 사용하여 풀이하였다. 다른 BFS 문제를 풀어보았다면 실버 1 문제라기엔 크게 어렵지 않은 문제이다. 오히려 공백없이 들어오는 숫자들을 어떻게 한 자리씩 입력받아 저장할지를 더 많이 고민하였다. #include #include #include #define X first #define Y second using namespace std; int dx[4] = {1,0,-1,0}; int dy[4] =..

(C++) 백준 1926번 - 그림

문제 링크 : https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 BFS를 사용하여 풀이하면 되는 문제이다. 그림의 시작점을 찾기 위해 전체적으로 이중 for문으로 스캔하면서 아직 방문하지 않은 시작점을 찾는다. 그 후 BFS를 사용하여 인접 칸들을 순회하면서 그림의 크기를 알아내었다. #include #include #include #define X first #define Y second using namespace std; int dx[4] ..

(C++) 우선순위 큐(Priority Queue)

우선순위 큐란? 우선순위를 가지는 데이터들을 저장하는 큐(Queue)를 말한다. 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. 우리가 흔히 말하는 큐(Queue)와의 차이는 일반적인 큐는 아래 그림과 같이 선형적인 구조를 가지는 반면 우선순위 큐는 트리 구조로 생각할 수 있다. 우선순위 큐의 동작 원리 일반적으로 우선순위 큐는 최대 힙(Max Heap)을 이용해 구현한다. 그래서 우선순위 큐의 동작 원리를 알아보기 전에 먼저 최대 힙에 대해 알아보자. 최대 힙은 부모 노드가 자식 노드 보다 값이 큰 완전 이진트리를 의미한다. 그렇기에 루트 노드는 전체 트리에서 가장 큰 값을 가진다. 이제 우선..

(CS) 캐시 메모리, 메모리 관리 기법, 페이지 교체 알고리즘

캐시 메모리 1. 캐시 메모리란? 캐시 메모리(Cache Memory)는 CPU와 RAM 간의 데이터 전송 속도를 높이기 위해 사용되는 중앙 처리 장치(CPU)와 주 기억장치(RAM) 사이에 위치한 고속 기억장치다. 캐시 메모리는 속도가 빠른 장치(CPU)와 느린 장치(RAM) 간의 속도 차이로 발생하는 병목현상을 완화하여 성능을 향상하는 데 중요한 역할을 합니다. 주기억장치에 비해 접근이 빠르지만, 용량이 작다는 특징을 가지고 있다. 캐시 메모리는 CPU가 처리할 데이터나 명령어를 저장하여 CPU가 필요할 때 빠르게 액세스 할 수 있도록 해준다. CPU는 일반적으로 계층 구조를 가진 캐시 메모리를 사용한다. CPU와의 거리에 따라 L1 캐시, L2 캐시, L3 캐시 등 여러 단계로 나뉜다. 숫자가 작을..