기본적인 구현 문제였다. 이런 문제는 c++의 stl인 queue를 사용해도 되지만, 자료구조 학습 기간이 길지 않은 초보자라면 직접 구현해보길 권장한다. front 와 back을 증가시키기만 하는 linear queue를 구현해도 주어진 input이 배열의 범위를 넘어가지 않아서 circular queue가 필요하지 않은 것 같다. circular queue는 modulo를 사용하면 된다. https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmic..

https://www.acmicpc.net/problem/17352 > n; for (int i = 0; i > a >> b; unionParent(a, b); } int parent_of_1 = getParent(1); for (int i = 2; i

https://www.acmicpc.net/problem/10409 10409번: 서버 당신은 FCFS(First-Come, First-Served)의 규칙에 따라 요청된 일을 처리하는 서버를 담당하게 되었다. 매일, 당신은 일을 처리하기 위해 최대 T분 동안 서버에 시간을 할당할 수 있다. 당신은 오늘 주어 www.acmicpc.net 여태 합한 시간(sum)과 이번에 입력받은 job의 시간의 합이 T를 넘어설 때, 이터레이션 i 를 출력하고 main을 종료한다. main을 종료하지않고 반복문을 빠져나왔다면, 모든 일이 시간 안에 끝난 것이므로 n을 출력한다. #include using namespace std; using ll = long long; const int MAX = 100001; int ..

2021.10.27 - [PS/백준] - 백준 1005 (C++) ACM Craft 백준 1005 (C++) ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총. synodic.tistory.com ACM Craft와 유사. https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. ..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 아이디어 위상정렬. 근데 약간의 다이나믹 프로그래밍을 곁들인... 위상정렬을 아는 사람이라면, 문제를 보고 위상 정렬 진행해서 같은 노드로부터 출발하면 큰 값의 delay(d[i]) 를 더하면 되겠구나, 하고 생각했을 것이다. 현재 노드를 cur, cur의 다음 노드를 nxt라고 했을때 result[nxt] 는 result[cur] + d[nxt] 중 최댓값이다. 틀렸습니다 를 받았다면? 1..

막대기에 맨 오른쪽부터 탐색한다. 어떤 막대기보다 왼쪽에 있는 막대기는 가려져서 보이지 않는 것에 유념하자. 처음에 여기서 틀렸다. #include #include using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,stick,ans=1; cin >> n; int arr[100000]; for (int i = 0; i > arr[i]; } stick = arr[n-1]; for (int i = n-1; i >= 0; i--) { if (arr[i] > stick) { // 가려지는 높이 갱신 ans++; stick = a..

아이디어 풀면서 재밌었던 구현 문제다. 숫자가 최대 100자리까지 주어진다고 했으므로 우리가 알고 있는 일반적인 변수크기로는 택도 없다. 따라서 string으로 a, b 변수를 만들고 어떻게 연산할 것인지 고민해보자. 우선 곱셈은 간단하다. 곱셈은 자릿수끼리의 덧셈이므로 string a와 b의 size(또는 length)의 덧셈만큼 0을 출력하면 된다. 덧셈에서는 경우의 수가 세가지이다 1. a > b 2. a < b 3. a == b 1. 의 경우 a.size() - b.size() - 1만큼 자릿수(0)를 출력한다. 2. 의 경우도 1과 마찬가지이다. 3. 의 경우는 "2"를 출력하고 수의 자릿수 -1만큼 "0"을 출력하면 된다. 코드 #include #include #include #include ..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 아이디어 분리집합을 알면 날먹 가능한 문제 이 유형이 대체로 티어가 높게 잡혀 날먹하기 좋다 입력받는 두 노드를 merge하기 전 사이클이 생기는지 확인한다. 사이클이 생긴다면 그대로 그때의 iteration(> n >> m; for (int i = 0; i a >> b; if (getParent(a) =..

아이디어 인접행렬 adj에 입력 받을 때, 갈 수 없는 경로를 0의 값을 INF (아주 큰 값)으로 바꿔 저장하고 플로이드 와샬로 adj를 탐색하면서 다른 노드를 통해 거쳐갈 수 있는 빠른 길이 있다면 갱신해주었다. 코드 #include #include #include using namespace std; using ll = long long; const int INF = 1e8; const int MAX = 101; int n, ans=0; int adj[MAX][MAX]; void fw() { for (int k = 1; k

분리 집합 분리 집합을 이용해 풀었다. 분리 집합의 기본을 연습하고 싶다면 이 문제를 풀어보자 2021.09.28 - [PS/백준] - 백준 1717 (C++) 집합의 표현 백준 1717 (C++) 집합의 표현 크루스칼 알고리즘은 모르는 이에게 설명하기도 쉽고 이해하기도 쉽다. unionParent함수에서 일반적으로 부모노드가 더 큰 쪽에 합치지만 일방적으로 첫번째 파라미터인 변수에 union 했다. 코드 // synodic.tistory.com 시간 비교(BFS vs Union set) 찾아보니 이분탐색 + bfs를 이용한 방법이 많다. 맨 위가 나의 제출인데 굉장히 적은 시간과 메모리가 걸린 것으로 보인다. 처음엔 주어진 집합을 전부 union하고 각각의 비용을 2차원 인접 행렬에 저장한 뒤 입력의 ..