백준/자료구조39 백준 20040 c++ "사이클 게임" -PlusUltraCode- https://www.acmicpc.net/problem/20040[필자 사고]문제를 읽어보면 사이클이 생기냐 안생기냐 를 구분하는 문제이다.입력이 순서대로 주어질 때 처음으로 사이클이 생기는 경우를 골라야 된다.필자는 사이클의 유무와 처음으로 사이클이 생기는 경우 이 두가지를 조합하여 유니온 파인드 알고리즘을사용하여 문제를 해결했다.[코드 해설] Union-Find 자료구조의 초기화프로그램은 N개의 노드와 M개의 간선 정보를 입력받습니다.먼저 parent 벡터를 초기화하여, 각 노드가 자기 자신을 부모로 가지도록 설정합니다.이는 각 노드가 독립된 집합으로 시작함을 의미합니다.Find 함수find 함수는 주어진 노드의 루트 부모를 찾는 역할을 합니다.경로 압축(Path Compression)을 통해 탐색.. 2025. 1. 3. 백준 2164 c++ "카드2" -PlusUltraCode- https://www.acmicpc.net/problem/2164 [필자 사고]자료구조 문제이다. 그 중에서도 큐를 이용하면 쉽게 문제를 풀 수있다. 여기서 중요한 점은 카드를 버리는 시점에 큐의 사이즈이다. 카드를 버리는 시점에 큐의 사이즈가 1이 될 경우 게임을 중단하고 답을 출력하면 문제를 쉽게 해결 할 수 있다. [소스 코드]#include #include #include using namespace std;queue pq;int N;void Input() { cin >> N; for (int i = 1; i 2024. 8. 19. 백준 17298 c++ "오큰수" -PlusUltraCode- https://www.acmicpc.net/problem/17298 [필자 사고]현재 N의 크기가 1000000정도가 되면 시간복잡도 N^2으로는 풀리지 않는 문제이다. 처음 이 문제를 접하게 되면 스택을 이용하여 문제를 해결하는 아이디어가 쉽게 떠오르지 않을 것이다. 필자는 과거 유사한 문제를 풀어 본 경험이 있어 스택을 이용해 이 문제를 해결했따. 1. 스택이 비어있으면 현재 idx 를 스텍에 넣는다.2. 스택의 맨 위의 idx의 실제 값과 비교하려는 값을 비교한다.3. 스택의 맨 위값이 더 작으면 스택의 idx에 해당하는 배열에 비교하려는 큰 값을 넣는다.4. 위 규칙이 어긋날때까지 반복 후 비교하려는 idx 를 스택에 저장한다. [소스 코드] #include #include#include us.. 2024. 8. 17. 이전 1 ··· 7 8 9 10 다음
