컴굥일지

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42626 문제 내용 음식들의 지수가 모두 K 이상이 되기 위해 몇 번의 연산이 필요한지를 출력하면 된다. (불가능하면 -1 출력) 연산은 (가장 낮은 지수 + 그 다음으로 낮은 지수*2) 로 계산되며, 사용된 음식은 사라지고 연산에 의해 새로운 음식이 추가된다고 생각하면 된다. 문제 풀이 우선순위큐로 문제를 쉽게 해결할 수 있다.(heap) 이때 우선순위 큐의 사이즈에 주의하자. 원소가 없는데 top(), pop() 연산을 하면 에러가 난다. (한참 헤맸다) 코드 #include #include #include using namespace std; int solution(vector scovil..

문제 https://www.acmicpc.net/problem/1717 문제 내용 두 원소가 같은 집합에 있는지 아닌지를 출력하면 되는 문제이다. 합집합 연산은 0 a b 형태로 주어지고, 1 a b는 a와 b가 같은 집합인지를 출력하라는 명령이다. 문제 풀이 유니온 파인드를 구현할 줄 알면 해결할 수 있다. 코드 #include #include using namespace std; vector parent; // 값이 음수면 그 노드가 root라는 뜻, 양수는 자신의 부모를 나타냄 int findParent(int node) { if (parent[node] < 0) { return node; // 루트 정점 } return parent[node] = findParent(parent[node]); //..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/77484 문제 내용 로또 번호와 당첨 번호를 입력받아, 몇 등을 했는지를 파악하는 문제이다. 단, 일부 로또 번호가 지워져있기 때문에, 배열의 로또 최고 순위와 최저 순위를 담아서 return 하면 된다. 문제 풀이 몇 개가 일치하는지 파악한 후에, 최고 순위의 경우 지워진 번호가 모두 일치한다고 가정하고, 최저 순위의 경우 지워진 번호가 모두 불일치한다고 가정하면 된다. 일치하는 개수가 아닌 등수를 반환해야 하므로, 마지막에 처리가 필요하다. 코드 #include #include #include using namespace std; int returnScore(int n){ if(n==0 ||..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12938 문제 내용 n개의 숫자를 더하여 s를 만든다. 이때 해당 n개의 숫자의 곱이 가장 큰 경우를 구하면 된다. 문제 풀이 중복이 허용되기 때문에 그렇게 어렵지는 않다. 모든 값이 중앙에 몰려있어야 곱했을 때 가장 크게 나오기 때문에, s를 n으로 나눈 값을 기본하면 된다. 나머지가 발생한 경우, 크기 만큼 +1을 해주면 된다. 코드 #include #include #include using namespace std; vector solution(int n, int s) { int num=s/n; if(num == 0) return {-1}; vector answer(n, num); for(..

문제 https://www.acmicpc.net/problem/7662 문제 내용 I연산은 뒤에 오는 수를 이중 우선순위 큐에 "삽입"하는 연산이다. D -1 연산은 최솟값을 이중 우선순위 큐에서 "삭제"하는 연산이고, D 1 연산은 최댓값을 이중 우선순위 큐에서 "삭제"하는 연산이다. 이중 우선순위 큐에 원소가 없을 때 D연산이 들어오면, 그냥 무시한다. 이중 우선순위 큐에는 같은 원소가 여러번 들어갈 수 있다. 우리는 모든 연산이 끝난 후, 비어있다면 EMPTY를, 그렇지 않으면 최솟값과 최댓값을 출력하면 된다. 문제 풀이 문제 이름은 이중 "우선순위 큐" 이지만, 문제를 잘 보면, 최대/최솟값을 모두 찾아야 함을 알 수 있다. 따라서 heap(priority_queue)가 아니라 set을 사용할 예..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 문제 내용 N개의 송전탑과 이를 연결하는 N-1개의 전선이 있다. 입력으로 주어지는 송전탑들의 관계는, N-1개의 전선으로 모두 이어져있다. 이때, 전선 1개를 끊어서 송전탑을 2 부류로 나눈다. 양측의 탑의 개수의 차를 최소화 했을 때의 차이를 구하면 된다. 문제 풀이 주어진 N-1개의 전선을 한번씩 끊어보면 된다. 끊고 bfs를 돌리면 탑들이 2부류로 나뉘게 된다. 이때의 차를 구하는 것은 어렵지 않다. 코드 #include #include #include #include using namespace std; int divideTowerAndCalcNum(vectorarr[], in..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 문제 내용 table에 놓인 도형들을, 최대한 game_board에 채워 넣어야 한다. 단, 도형은 딱 맞는 곳에만 들어갈 수 있다. (넣었을 때 옆에 공백이 남으면 안 된다.) 도형을 집어넣을 때, 조각을 회전시킬 수는 있지만, 뒤집을 수는 없다. 최대한 많은 조각을 채워 넣었을 때, 몇 칸을 채워 넣은 것인지를 구하면 된다. 문제 풀이 table의 도형이, game_board의 빈칸에 완벽하게 들어가야 하기 때문에, table과 game_board에서 도형과 빈칸을 각각 추출해야 한다. 그리고 해당 도형들을 매칭시켜주면 되는데, 이때 도형을 돌릴 수도 있다. 1. 도형/빈칸 추출 i..

문제 https://www.acmicpc.net/problem/14500 문제 내용 위의 도형 5가지는 회전시키거나 뒤집을 수 있다. 각 칸에 정수가 적힌 배열을 입력받고, 그 배열에 위 도형 중 하나를 올려놓는다. 올려진 부분의 정수를 모두 더한 값이 최대가 되도록 하면 된다. 문제 풀이 브루트포스로 문제를 해결할 수 있다. 도형이 차지할 수 있는 범위를 모두 적어두고, 반복문을 전부 돌려보면 된다. 코드 #include #include using namespace std; int n, m; int arr[500][500]; vector puzzle = {{{true, true, true, true}}, {{true}, {true}, {true}, {true}}, {{true, true}, {true,..

문제 https://www.acmicpc.net/problem/1991 문제 내용 노드와 해당 노드에 연결된 왼쪽 자식, 오른쪽 자식 정보를 입력받는다. 입력받은 트리의 전위 순회, 중위 순회, 후위 순회 결과를 출력하면 된다. 문제 풀이 구현은 둘째 치고, 트리의 순회에 대해 알고 있는 것이 더 중요하다. 트리의 순회는 아래와 같이 재귀적으로 구현할 수 있다. 1. 전위 순회 1. 현재 정점을 방문 2. 왼쪽 서브 트리를 전위 순회 3. 오른쪽 서브 트리를 전위 순회 **) 전위 순회는 dfs의 방문 순서와 동일하다 2. 중위 순회 1. 왼쪽 서브 트리를 중위 순회 2. 현재 정점을 방문 3. 오른쪽 서브 트리를 중위 순회 **) 이진 탐색 트리라면, 중위 순회를 돌렸을 때 크기 순으로 출력이 된다. ..

문제 https://www.acmicpc.net/problem/11724 문제 내용 정점과 간선의 정보를 입력받아, 몇 개의 연결 요소로 이루어져 있는지 구하면 된다. (사이클을 말하는 게 아니라 연결 요소를 말하는 것) 문제 풀이 모든 노드에 대해 아직 방문하지 않은 경우, bfs를 돌리면 된다. 나는 이 문제를 인접 행렬로 구현하지 않고, 인접 리스트로 그래프를 구현했다. 코드 #include #include #include using namespace std; int n, m; vector arr[1001]; int visited[1001]; int main() { cin >> n >> m; int node1, node2; for (int i = 0; i > node1..