c++33 [백준/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. [KAUPC/C++] 차이를 최대로 (Deque/Sliding Window) 문제https://www.codetree.ai/problems/make-dif-max/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 구상해당 문제는 특정 window 크기 안의 값들의 최소값, 최댓값을 구해야 하는 문제였다. queue를 이용하여 풀 수도 있지만, deque를 이용한 풀이가 더 효율적이었다. 먼저, 원형으로 이루어져있는 값들을 1차원 배열으로 나타내어서 0번부터 k-1번 원소가 마지막에 한번 더 필요했다. 그래서 배열 마지막에 추가로 넣어주었다. 예를 들어 위 사진과 같은 상태에서 k가 4라고 한다면, 배열을 [7,.. 2024. 9. 10. [KAUPC/C++] 조상 노드 (DFS) 문제https://www.codetree.ai/problems/node-ancestor/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 구상조상 노드의 유무를 파악하는 문제였다. 오랫만에 찐 dfs다운 문제를 만나서 잠깐이지만 좀 설렜다 ㅎㅎ 조상 노드의 유무를 파악하는 방법이 dfs를 이용하는 것이라는 것만 파악했다면 어렵지 않은 문제인데, 해당 과정이 흔하지 않아 처음 봤을땐 어렵게 느껴졌던 것 같다. dfs 과정을 루트(1번 노드)부터 시작하여 재귀적으로 진행하다보면 이것으로 노드간의 부모 자식 유무를 파악할 수 있을 것 같은 .. 2024. 9. 10. 이전 1 2 3 4 ··· 9 다음
