전체 글

처음에 어떻게 해야할지 막막한데 생각보다 센스있는 수 처리 방법이 있었습니다 이해 못 하다가 한 블로그 글을 보고 이해하게 되어 해당 블로그 글 링크를 같이 글 아래 쪽에 남깁니다 Solution #include using namespace std; int main() { int N, K; cin >> N >> K; int start = 1, end = K, ans = 0; while (start

https://www.acmicpc.net/problem/5525 알고리즘 분류 문자열 Hint 해당 문제는 서브태스크가 있어 제약 조건에 따라 점수가 달라집니다 저는 여기서 시간 복잡도와 연관되어 있다고 생각을 했고 시간 복잡도를 만족할 수 있는 생각을 했습니다 그래서 시간 복잡도에 상관 없이 코드를 짠다면 직접 모든 구간을 IOI로 구성되어 있는지 확인하면 될 것이고 시간 복잡도를 고려하여 코드를 짠다면 IOI가 있는지에 대한 판단을 할 때 계산이 필요하다 생각했습니다 Solution 시간 복잡도를 고려하여 문자열을 하나하나 탐색하지 않고 문자열을 판단할 때 int형 배열을 하나 추가적으로 이용하여 반복되고 있으면 +1을 하고 반복되지 않으면 초기화 하여 계산했습니다 뒤에서부터 탐색하여 반복되는지 확..

https://www.acmicpc.net/problem/1107 알고리즘 분류 브루트포스 알고리즘 Hint 시간이 2초라서 C++로는 생각보다 많은 연산을 할 수 있습니다 1초당 1억 번의 연산을 한다고 보통 가정합니다 N의 범위가 50만이므로 각 자리 수를 2^6번(최대 자리 기준)으로 가정한다해도 약 3000만번의 연산밖에 걸리지 않습니다 bool array로 사용 가능한 Button을 관리하면 쉽습니다 Solution #include #include #include using namespace std; int main() { int N, M; bool Button[10]; for (int i = 0; i > N >> M; for (int..

https://www.acmicpc.net/problem/10799 알고리즘 분류 자료구조 스택 Hint 굳이 STL stack 을 사용하지 않아도 Stack 논리를 활용하여 풀 수 있습니다 Solution ) 나왔을 때 직전에 ( 나오면 자르기 -> 스택에서 -1 그리고 스택 내 남은 아이템 개수만큼 카운트 + 직전에 ) 나오면 -> 스택에서 -1 카운트 +1 ( 나오면 스택에 +1 Stack: 1 예제1) 3+3+1+3+1+2+1+1+1+1 = 17 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); int stack_size = 0; // 실제 스택을 구현할 필요는 없으므로 st..

https://www.acmicpc.net/problem/30022 30022번: 행사 준비 첫째 줄에 정수 $N(2\le N\le 100,000)$과 정수 $A,B(1\le A,B\leq N;A+B=N)$가 공백으로 구분되어 주어진다. 둘째 줄부터 $N$개의 줄에 정수 $p_i,q_i(1\le p_i,q_i\le 10^9)$가 공백으로 구분되어 주어진다. $p_i,q_i$는 www.acmicpc.net 알고리즘 분류 그리디 알고리즘 Hint q의 범위를 감당할 수 있는 자료형 사용 물건을 구매하는데 필요한 최소 비용을 구하려면 상점 1과 상점 2의 같은 상품에 대해 구매할 수 있는 가격에 따라 알고리즘을 만들어야 한다 Solution #include #include using namespace std;..

https://www.acmicpc.net/problem/30024 30024번: 옥수수밭 옥수수밭 주인 민석이는 한 해 동안 열심히 기른 옥수수를 수확하려고 한다. 옥수수밭은 $N$행 $M$열의 격자로 생각할 수 있는데, 격자의 각 칸에는 한 그루의 옥수수가 심어져 있다. 민석이는 각 www.acmicpc.net 알고리즘 분류 그래프 탐색(너비 우선 탐색: BFS) 우선순위 큐 Hint 시간 제한이 1초이고 K가 최대 10만이기 때문에 최악의 경우 O(N^2)이기 때문에 시간 초과가 발생합니다 우선 순위 큐의 알고리즘을 이용한다면 쉽게 접근이 가능합니다. 해설 #include #include #include using namespace std; int main() { // 입출력 시간 단축 코드 ios..