BOBO's Note

https://programmers.co.kr/learn/courses/30/lessons/42629 코딩테스트 연습 - 라면공장 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니�� programmers.co.kr 풀이 방법 하루에 밀가루를 1톤씩 사용하므로, 밀가루 재고가 amount일 때 현재 날짜가 amount 보다 크거나 같으면 밀가루 재고가 부족하다. 따라서 이 경우에는 그 전에 밀가루를 미리 구매해야 한다. 이때, 밀가루 구매 횟수를 최소화하기 위해서는 한번에 최대한 많이 구매할 수 있는 날에 구매해야 한다. 따라서 우선순위 큐를 두어서 한번에 구매할 수 있는..

https://programmers.co.kr/learn/courses/30/lessons/49189?language=cpp 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 방법 1번 노드와 가장 멀리 떨어진 노드들의 개수를 구하는 문제이다. BFS를 이용해 거리 별로 방문하다가 가장 마지막에 방문한 노드 개수를 반환하면 된다. 우선 노드의 개수가 최대 20,000개이고, 간선의 개수는 최대 50,000개이므로 간선 정보를 인접 행렬보다는 인접 리스트에 저장하는 게 더 효율적이다. 왜냐하면 인접 행렬은 크기가 20,000*20,000인 반면, 인접 리스트는 50,000이기 ..

https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 방법 수를 제거해 최대한 큰 숫자를 얻으려면, digit이 큰 수를 최대한 앞쪽에 위치하도록 삭제해야 한다. 따라서 먼저 가장 큰 digit을 찾고, 이 digit을 삭제하지 않을 것을 mark[] 배열에 체크하고 추가한 digit 개수 added를 1 증가시킨다. char max_digit = number[start]; int max_idx = start; for(int i=start+1; i max_digit){ max_digit = number[i]; max_idx = i; if(max_digit == '9') break; } ..

https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세�� www.acmicpc.net 풀이 방법 소요시간을 기준으로 다익스트라 알고리즘을 적용해 풀 수 있다. 이때, 지원비용 내에서 최소 소요시간을 구하는 문제이기 때문에 한번 방문했던 vertex더라도 재방문할 수 있다(소요시간은 짧지만 비용이 커서 해당 경로로 못 갈 수 있기 때문이다). 처음엔 다익스트라 알고리즘에서 인접 vertex에 대해 distance 벡터를 업데이트해줄 때 다음과..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 풀이방법 다익스트라 알고리즘을 이용해 풀 수 있다. priority queue로 다음 vertex를 고르지 않으면 시간 초과가 발생한다. 두 vertex 사이에 여러 간선이 존재할 수 있으므로, 그 중 가중치가 최소인 간선만 저장하기 위해 adjacency list를 unordered_map을 이용해 변형했다. 각 vertex는 unordered_map을 갖는데, uno..

https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. www.acmicpc.net 풀이 방법 뱀의 위치, 움직임, 회전 등을 Snake라는 클래스로 나타냈다. enum Dir{RIGHT, DOWN, LEFT, UP}; class Snake{ public: Snake(): dir(RIGHT) { body.push_front(0); body_pos.insert(0); }; void rotate(int d){ if(d == RIGHT) dir = (dir + 1) % 4; else dir ..

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 방법 배열의 (r, c)의 값이 k이 될 때까지 반복문을 돌며 배열에 연산을 적용한다. 이때, 100초를 초과하면 -1을 출력하고 프로그램을 종료한다. 배열의 연산은 Array 클래스 내의 change() 메소드로 구현했다. while(!arr.is_equal(k)){ t++; if(t > 100){ cout = C) op_row(); else op_col(); } row-wis..