본문 바로가기

백준189

백준 20040 c++ "사이클 게임" -PlusUltraCode- https://www.acmicpc.net/problem/20040[필자 사고]문제를 읽어보면 사이클이 생기냐 안생기냐 를 구분하는 문제이다.입력이 순서대로 주어질 때 처음으로 사이클이 생기는 경우를 골라야 된다.필자는 사이클의 유무와 처음으로 사이클이 생기는 경우 이 두가지를 조합하여 유니온 파인드 알고리즘을사용하여 문제를 해결했다.[코드 해설] Union-Find 자료구조의 초기화프로그램은 N개의 노드와 M개의 간선 정보를 입력받습니다.먼저 parent 벡터를 초기화하여, 각 노드가 자기 자신을 부모로 가지도록 설정합니다.이는 각 노드가 독립된 집합으로 시작함을 의미합니다.Find 함수find 함수는 주어진 노드의 루트 부모를 찾는 역할을 합니다.경로 압축(Path Compression)을 통해 탐색.. 2025. 1. 3.
백준 2098 c++ "외판원 순회" -PlusUltraCode- https://www.acmicpc.net/problem/2098 [필자사고]이 문제는 비트 마스킹을 이용하여 메모리제이션을 효율적으로 가져가 푸는 문제이다.필자는 비트마스킹 개념이 약한 편이라 이 문제를 풀지 못하였고 낮은 단계부터 천천히 풀어봐야 될거 같다.문제를 보면서 DFS를 이용하여 해당 방문한곳을 체크해가며 최소값으로 cost 비용을 갱신하는 형태로 코드를 짰다.[코드 해설] 입력 처리 및 초기화 (Input 함수)사용자로부터 입력받은 값으로 N개의 노드와 그 간선의 비용을 저장한다.2차원 벡터 arr는 간선의 비용을 저장하며, 초기 크기를 N x N으로 설정한다.2차원 벡터 cost는 각 노드와 방문 상태(bit)를 조합한 경우의 최소 비용을 저장하기 위해 사용되며, 초기값은 -1로 설정된다.. 2025. 1. 2.
백준 2467 c++ "용액" -PlusUltraCode- https://www.acmicpc.net/problem/2467 [필자 사고]정렬되어 있다. 이 키워드를 통해 이 문제는 이분탐색 아니면 투포인터이지 않을까?? 와 같은 사고를 했다. 문제를 읽어보니 부르스트 알고리즘을 적용하면 시간내에 못 풀게 되어 있다.역시나 투포인터 알고리즘을 이용해야 된느 문제이다.O(nlogn) 시간복잡도로 충분히 시간 내에 풀 수 있다. 필자가 실수 했던 부분은 초기화 부분에 있었다. 1. 먼저 long 으로 해야된다.2. arr[left]+ arr[right] 등의 숫자들을 미리 담아나야된다. 이 부분만 신경쓰면 쉽게 해결할 수 있따.[코드 해설] Input 함수N개의 정수를 입력받는다.입력된 정수들을 저장할 arr 벡터를 초기화하고, 순서대로 값을 저장한다.Two_Poi.. 2025. 1. 2.
백준 12015 c++ "가장 긴 증가하는 부분 수열 2" -PlusUltraCode- https://www.acmicpc.net/problem/12015[필자 코드]먼저 LIS 를 알아야 된다.*가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)**은 주어진 수열에서 일부 숫자들을 골라내어, 원래 순서를 유지한 채로 증가하는 형태로 만들 수 있는 가장 긴 부분 수열을 찾는 문제입니다.예를 들어, 수열이 [10, 20, 10, 30, 20, 50]라면, 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]입니다.중요한 점은, 수열 내 숫자의 순서를 바꾸지 않는다는 것입니다. 따라서 단순히 숫자를 크기순으로 나열하는 문제가 아닙니다.위 코드는 LIS를 효율적으로 계산하기 위해 **이진 탐색 (Binary Search)**를 활용한 방법을 사.. 2024. 12. 26.

티스토리툴바