알고리즘/BOJ36 [백준/C++] #1744 수묶기 (Greedy) 문제https://www.acmicpc.net/problem/1744 풀이 (37m / 한번에 x) 수들끼리 짝지어서 곱해 더할 수도 있고, 그냥 더할 수도 있는데, 합이 최대가 되도록 해야했다. 생각났던 로직 순서대로- 가장 큰 양수부터 시작해서 두개씩 짝지어서 곱해서 더함- 양수의 개수가 홀수라면 남은 양수는 그냥 더함- 1은 다른 양수랑 곱해서 더하기보다 그냥 더하는게 더 커지니 따로 그냥 더함- 0도 있고 홀수도 있다면, 0 개수만큼 가장 작은 홀수들 부터 없애기+) 음수가 2개 이상이라면 0이랑 상쇄시키기보다 일단 가장 작은 홀수들부터 두개씩 곱해서 양수 만들기+) 음수가 홀수개이고, 0이 있다면 마지막으로 가장 큰 음수는 0이랑 상쇄시키기. 0이 없다면 그냥 더하기 생각보다 예외 케이스들이 바.. 2025. 3. 26. [백준/C++] #11559 Puyo Puyo (BFS) 문제https://www.acmicpc.net/problem/11559 풀이 (1h 16m / 한번에 O)뭐 거창한거 없이 그냥 하라는 대로 하면 되었다. 한 시점에 터지는건 하나로 치니까, 시점을 반복문(while)을 통해 구분하자는 생각이 들었다. 그래서 반복문 안에서 flag를 통해 한 시점에 터지는게 있는지를 나타냈다. flag가 0이면 그냥 반복문을 나가고, 연쇄가 몇번 연속으로 일어났는지 출력해줬다. 터지는지 파악하는 데에 bfs를 사용했다. 왜냐하면 동서남북 인접한 곳에 4개의 같은 색의 칸이 있는지 파악을 해야 했기 때문이다. 그렇게 4개 이상의 같은 색의 칸이 인접해있으면, 탐색했던 곳이 기록된 visited 배열을 사용해 해당 위치를 터뜨렸다. 동시에 더 터뜨릴 칸들이 없으면, 중력.. 2025. 2. 19. [백준/C++] #5021 왕위 계승 (위상 정렬) 문제 이 문제는 가족 관계를 방향 그래프(DAG)로 나타내어, 각 개인이 왕의 혈통을 얼마나 이어받았는지 계산하는 문제이다.부모가 두명으로 이루어져있다는 점에서 좀 난항을 겪었다가, 자식에 대한 부모 정보를 따로 저장하는 map을 만들어 문제를 해결했다. 풀이자식이 부모의 부모가 되는 경우가 없다는 조건이 명시 되어 있으므로 사이클이 없는 방향 그래프(DAG)임을 알 수 있다. 따라서 위상 정렬을 이용하여 부모의 혈통이 먼저 계산된 후 자식에게 전파되도록 구현할 수 있다.!!혈통 계산 방식은 부모로부터 반씩 혈통을 받는 방식이다. 왕의 혈통을 1.0으로 설정한 후, 각 자식의 혈통을 부모들의 혈통의 절반씩 더한 값으로 계산하면 된다. 위상정렬은 사이클이 없는 방향 그래프(DAG, Directed Acyc.. 2025. 1. 30. [백준/C++] #14284 간선 이어가기 2 (Dijsktra) 문제https://www.acmicpc.net/problem/14284 풀이간선 정보들 연결리스트로 관리하고, 최단 경로 길이 배열에 저장하고, 최단 경로 구할때 시간복잡도 줄이기 위해 우선순위 큐를 쓰는.. 가장 전형적인 다익스트라 문제였다.다익스트라 문제들은 거의 풀이 형태가 같으니 한번 제대로 익혀놓는걸 추천한다!#include #include #include #define INF 987654321using namespace std;/*특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되도록 추가하는 간선의 순서를 조정-> 최솟값은? */int n; // 정점의 개수int m; // 간선 리스트의 수int s, t;vector>.. 2024. 11. 11. [백준/C++] #11057 오르막 수 (DP) 문제https://www.acmicpc.net/problem/11057 풀이1. 팩토리얼 사용해서 integerOverflow 발생한 코드: 팩토리얼을 계산하는 과정에서 숫자가 매우 커지기 때문에 long long으로도 수를 감당할 수 없게 되어 integerOverflow 발생 사용할 수의 개수만큼 0~9중에 고르기 & 마지막 자릿수 제외한 자릿수 중에 어디"까지" 특정 수가 나올지 고르기이렇게 두 로직을 combination으로 계산할 수 있다. 예를 들면, 수의 길이가 4라고 하자. 길이가 4인 수는 숫자 4개 혹은 3개 혹은 2개 혹은 1개로 오르막 수를 구성할 수 있다. 숫자 4개를 이용하는 수를 만들기 위해서는 0~9 수들 중 중복되지 않는 수 4개를 고르고(10 C 4), 마지막 자리를 제.. 2024. 11. 11. [백준/C++] #1904 01타일 (DP) 문제https://www.acmicpc.net/problem/1904 풀이 (총 소요 21m)1. 시간초과 나는 재귀 풀이: make 함수가 모든 가능한 타일 배열을 만드는 모든 경우를 확인하면서 진행. 즉, 재귀 방식으로 호출되는 모든 부분 문제를 반복적으로 해결하게 되면서 계산량이 매우 커지고 시간 초과가 발생하게 됨.#include#include#define endl "\n"using namespace std;int leng;int num = 0;void make(int length) { if (length == leng) { num++; num %= 15746; return; } else { if (length + 2 > leng;.. 2024. 11. 11. 이전 1 2 3 4 ··· 6 다음
