겜돌이의 개발일지

문제 백준 20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N > N >> Q; for (int i = 0; i > num; int temp = num; bool canreach = true; stack st; //경로를 스택에 넣어줌 while (temp != 0) { st.push(temp); temp /= 2; } //스택 꺼내면서 경로확인 while (!st.empty()) { temp = st.top(); //경로의 해당 땅을 지나갈 수 없으면 if (check[temp] == true) { cout

문제 백준 3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 풀이 경곗값 설정을 잘 못해서 고생 좀 했습니다. 최소 시간의 최댓값은 1 1000000000 1000000000 경우의 1000000000000000000입니다. 따라서 이분 탐색 시에 최솟값을 1, 최댓값을 1000000000000000000으로 설정해야 합니다. 그 후에는, 배열을 돌면서 sum에 해당 심사대 에서 입국할 수 있는 사람의 수(mid/arr[i])를 더해줍니다. sum 값이 목표값 보다 크거나 같으면 end ..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 유명한 0-1 배낭 문제입니다. dp[i][j]의 의미는 i개까지의 물건을 넣는 경우에서 무게가 j일때 가치의 최대값입니다. 예제 입력으로 분석해보겠습니다. n / k 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 1 0 0 0 0 0 13 13 2 0 0 0 8 8 13 13 3 0 0 6 8 8 13 14 4 ..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 입력이 단순 숫자가 아니라 문자열 형태로 들어오기 때문에 그것 또한 고려해줘야 했습니다. 명령은 뒤집기 R과 맨 앞 삭제하기 D가 있는데 R일 때 실제로 배열을 뒤집어 버리면 시간 초과가 납니다. 방향을 체크하는 변수를 만들어주고, 변수를 통해 명령어를 처리해줘야 합니다. 먼저 문자열을 입력받고, 숫자만 dq에 push해줍니다. 현재 방향을 확인하여, R입력을 받으면 상태를 전환해줍니다. D입력을 받으면 방향이 거꾸로일 때는 뒤에서 삭제, 정..

문제 백준 11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si 따라서 pq2.top의 종료시각이 pq1.top의 시작시각보다 커질때까지..

문제 백준 11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 1. 각각의 칸을 bfs로 탐색하여 없어지는 칸들을 구합니다. 2-1. 없어지는 칸이 없다면 더 이상 연쇄가 일어나지 않는 것이므로 루프를 종료하고 combo를 출력합니다. 2-2. 없어지는 칸이 있다면 그 칸들을 .으로 바꿔줍니다. 3. 그 후 아래칸부터 접근해 해당칸이 .이고, 그 윗칸이 .이 아닐 경우 당겨줍니다. (중력 적용) 4-1. 당겨지는 칸이 있을 경우에는 3번 과정으로 돌아가 계속 해서 당겨줍니다..

문제 백준 16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 문제 풀이 자체는 직관적인데 구현에 시간이 좀 걸렸습니다. 먼저 먹이를 bfs로 찾아줍니다. (먹이는 상어 크기보다 작아야 하고 상어 크기보다 큰 물고기는 지나갈 수 없습니다!!) 먹을 수 있는 먹이가 있으면, 상어가 이동하는 거리를 계산해 dtarr 배열에 넘깁니다. bfs가 끝나고 먹을 수 있는 먹이가 없으면, 종료하고 cnt를 출력합니다. 먹이가 있다면 가장 짧은 거리, 거리도 같다면 왼쪽 위에 있는 먹이를 목표로 설정합니다..

문제 백준 15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 풀이 리프 노드는 자식이 없으므로 서브 트리의 정점 개수는 자기 자신 1개입니다. 따라서 dp 배열을 1로 초기화해줍니다. 루트 노드부터 dfs를 실행하고, 서브 트리의 탐색이 모두 끝났다면 부모에게 자신의 서브 트리 값을 더해줍니다. 부모가 -1인 경우는 루트 노드이므로 더하지 않습니다. 예제를 보겠습니다. 숫자는 해당 정점에서의 서브 트리의 정점 개수이고, 괄호 안은 방문 순서..

문제 백준 2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 먼저 탑의 높이와 인덱스를 받는 stack을 선언합니다. 탑의 높이를 입력해주고, 뒤에서 부터 다음 과정을 실행합니다. 1. 스택이 비었을 경우에는 탑의 높이와 인덱스를 스택에 push 합니다. 2. 스택이 비어있지 않을 때는, 스택의 top과 현재 탑의 높이를 비교하여, top이 작다면 레이저가 도달한 것이므로 레이저가 닿는 탑의 위치를 저장하는 배열 receive에 탑의 위치를 저장해준 후, stack을 pop 합니다. 3. 계속해..

문제 백준 1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 전형적인 트리 - dfs 문제입니다. 부모가 없는 노드(입력이 -1)를 루트 노드라고 하고, 루트 노드부터 dfs를 진행합니다. 이 때 제거하는 노드 처리가 중요한데, 루트 노드를 제거하였을 때는 0을 바로 출력해줍니다. 그 이외일 때는 제거한 노드를 기억하여, dfs를 실행할 때 방문하지 않습니다. 리프 노드는 자식이 없는 노드이므로 vector의 사이즈를 확인하여, 0이면 cnt를 ++해줍니다. 또한 제거된 노드 하나만을 자식으..