Algorithm/Beakjoon

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

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/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 1. Logic dp배열에는 해당 숫자를 만들수 있는 최소 갯수를 저장한다. 숫자를 중복해서 골라도 되고 해당 숫자를 고를수도, 안고를 수도 있으니 i*i를 구하는 for문 안에서 숫자를 선택하는 경우 선택하지 않는 경우를 반영해준다. 2. Code #include using namespace std; int n; int dp[50001]; int solve(i..

https://www.acmicpc.net/problem/1952 1952번: 달팽이2 M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다. 위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 www.acmicpc.net 1. Logic 2차원 배열로 BFS를 돌려서 하는 방법도 있고 단순 규칙을 찾아서 풀이할 수도 있다. 2. Code 구현 풀이 #include using namespace std; int n, m; bool vis[101][101]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main() { int n, m; cin >> n..

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 1. Logic 달팽이 탐색 부분은 2중 for문을 돌려서 확인하고 움직이는 칸수가 총 2번씩 반복된다는 규칙은 쉽게 찾았지만 저 좌표에 따라 비율 계산을 어떻게 해야하나 고민을 많이했고 아래의 블로그에서 광명을 찾아버렸다.. 댓글을 보니 나 말고도 여러 사람이 광명을 찾고 간듯..? 풀다가 막혀서 블로그를 찾아들어온 과거의 나 같은 사람들을 위해 아래에 블로그 링..

1. Banker's Algorithm이란? Deadlock을 회피하는 방법 중 한가지로 자원의 갯수가 2개 이상인 사이클에서 데드락을 회피할 때 사용하는 알고리즘이다. 알고리즘이 Banker's인 이유는 은행에서 100만원을 대출하려면 은행이 먼저 100만원을 가지고 있어야 대출해줄 수 있다. 만약 100만원이 없다면 은행은 돈을 빌려줄 수 없다. 이처럼 할당해 줄 수 있는 자원이 충분한지를 먼저 검사하고 교착상태에 빠질 가능성이 없으면 자원을 할당해주는 방식이다. 아래의 그림을 예시로 Banker's Algorithm을 살펴보자 2. 그림으로 살펴보는 Banker's Algorithm 아래 그림은 은행원 알고리즘을 이해하는데 가장 쉬운 그림이다. 차례대로 사용되는 용어를 알아보자면 A, B, C : ..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 1. Logic 기본 3차원 BFS 문제이다. Z축도 있기 때문에 6방향 탐색을 돌아주면 된다. 예외처리만 잘 해주면 무난히 통과하는 문제이다. 2. Code #include using namespace std; int l, r, c; int sx, sy, sz; char building[31][31][31]; bool vis[31][31][31]; int dz[6] = {0, 0, 0, 0, 1, -..