![]()
문제 접근 tuple을 쓰자. 3차원 공간 정보를 저장해야 된다. 구조체를 써도 되기는 하지만, 그냥 속 편하게 튜플을 썼다. 익은 토마토를 방문한 토마토로 생각하자. 별도로 visited 배열을 만들지 않고, 익은 토마토를 방문한 토마토로 생각했다. 배열을 굳이 동적 할당하려고 하지 말자. 기본 입력 값과 메모리 제한이 넉넉하다면, 그냥 최대 크기로 만들고, 일부만 사용하고자 했다. https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmic..
문제 접근 정직한 제목, 정직한 풀이 DFS와 BFS 구현하는 문제다. 그래프를 알면 그냥 풀면 된다. https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 코드 #include #include #include #include using namespace std; vector graph; vector visited; void print_DFS(int current_vertex) { visited[curren..
![]()
문제 접근 입력을 굳이 2차원 배열로 받을 필요가 없다고 생각했다. 높이 데이터만 갖고, 답을 찾을 수 있기 때문에 입력으로 높이 값만 받았다. 범위를 지정하고, 무조건 성립하는 개념을 찾았다. 우선 가장 낮은 높이와 가장 높은 높이라는 정답이 나올 수 있는 범위를 지정했다. 그 뒤 일단 가장 낮은 높이까지 인벤토리에 넣은 뒤에 한 칸씩 기준을 올렸을 때, 시간 변화량이 양수가 되면 바로 전 높이가 최단 시간, 최대 높이라는 걸 알 수 있었다. 그 이유는 간단하다. 문제의 조건 중 하나가 '집터 아래에 빈 공간이 존재하지 않는다.'이기에, 바로 위 높이의 블록 개수는 지금보다 많을 수 없다. 따라서 현재 높이의 블록 개수만큼 '넣기'를 취소하고, 빈 공간만큼 '꺼내기'를 했을 때의 시간 변화량이 양수라면..
문제 접근 나무들을 정렬한 다음에 가장 높은 나무를 기준으로 자를 높이를 점점 낮춰가자고 생각했다. 나무를 정렬한 뒤, 가장 높은 나무부터 현재 확인하고 있는 나무와 그다음 나무의 높이 차이를 height, 그리고 현재 확인하고 있는 나무가 몇 번째로 높은 나무인지는 width로 두고 M과 비교해 가며 높이를 낮춰갔다. 최악의 케이스를 상정해 봤다. 최대 나무 개수가 100만이고, 하나씩 확인하는 시간 복잡도는 O(n)이니 제한 시간 안에 충분히 동작 가능하다. https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000..
문제 접근 문제 설명에 나온 개념을 정리했다. 문제에서 말하는 생성자란 무엇인지, 분해합이란 무엇인지, 내 나름대로 간단하게 정리했다. 최악의 케이스를 상정해 봤다. 1부터 최대 입력 값인 100만까지 하나하나 확인해 본다고 하면 시간 복잡도는 O(n)이다. 최악의 경우, 입력이 100만이라고 하더라도 제한 시간 안에 가능하다. 그래도 시간을 더 줄일 수 있는 방법이 있나 생각해 봤다. 최대 입력 값은 100만이다. 각 자릿수의 합이 가질 수 있는 최댓값은 N이 999,999일 때 각 자릿수의 합인 54이다. 따라서 N이 55 이상일 때, N-54 미만의 자연수가 만드는 분해합은 절대 N이 될 수 없다고 판단했다. 최종적으로는 N1과 N-54 중에 큰 값부터 N까지만 확인하도록 해서 시간을 조금이나마 아..
문제 접근 소수의 정의와 에라토스테네스의 체라는 개념이 떠올랐다. 소수의 정의는 1과 자기 자신을 약수로 갖는 수. 에라토스테네스의 체란 작은 수부터 하나씩 확인하며 소수가 아닌 수를 소거해 가며 소수를 찾는 방법. 일단은 에라토스테네스의 체를 찾아보지 않고 구현해보려고 함. 최악의 케이스를 상정해봤다. 수 하나하나에 대해서 소수인지 아닌지 판별하려면 O(n^2)이 걸린다. 입력의 최댓값이 100만이기에, 최악의 경우, 1조 번 연산하게 되기에 단순하게는 풀지 못한다. 결국 에라토스테네스의 체처럼 소수를 찾으려 하지 않고, 소수가 아닌 걸 거르는 방식으로 해결하고자 했다. Just do it! https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M..
문제 접근 산술 평균의 경우, 값을 입력받을 때마다 N으로 나눈 것들의 총합을 구해 반올림하자. 총합은 반올림을 위해 실수 자료형을 사용했기에, 모두 더하고 나누면 오버플로우가 발생할 수 있음. 중앙값의 경우, 단순히 입력받은 값 vector를 정렬해서 중앙값을 가져오자. algorithm 헤더의 sort 함수는 O(nlogn)이다. 따라서, N이 최댓값(500,000)이라고 하더라도 대략 3백만으로 충분히 시간 내에 해결 가능함. 최빈 값의 경우, 중복 횟수를 세는 vector를 만들어서 max_element 함수로 최빈값을 찾자. 최빈 값이 여러 개라면 max_element 함수가 가장 첫 번째 max 값의 iterator를 반환하므로, 첫 번째 iterator 다음부터 end까지 중 max 값과 같..
문제 접근 원하는 수열의 확인해야 되는 부분과 스택의 top을 비교한다. 값이 같다면, 스택을 pop 하고 정답에 '-'를 추가한다. 값이 다르다면, 증가하는 정수 값을 스택에 push하고 정답에 '+'를 추가한다. 증가하는 정수 값이 n보다 큰데, 접근 1의 비교 값이 다르다면 수열이 만들어질 수 없으니 "NO"를 출력한다. https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmic..
