본문 바로가기

백준288

백준 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.
백준 1562 c++ "계단 수" -PlusUltraCode- https://www.acmicpc.net/problem/1562 [필자 사고] 어려운 문제다.처음에 DNS를 이용하여 풀려고 했지만 경우의 수를 생각해보니 시간초과가 나온다.어쩔 수 없이 30분 고민하고 풀이 힌트를 보았더니 비트마스킹을 이용한 동적프로그래밍 문제다. 나는 처음으로 비트마스킹 알고리즘을 만나게 되었따. 간단히 말하자면1000000000 이라는 2진수로 이루어진 bit가 있고1위의 기존 bit | new bit 를 하게 되면1000010000 식으로 게임 처럼 1로 바껴서 on모드가 된다.이러한 방식으로 아래의 문제를 해결했다.   소스코드 해설은 아래와 같다 1.코드 개요이 코드는 숫자의 길이 N이 주어졌을 때, 계단 수를 계산하는 프로그램입니다. 계단 수는 숫자의 각 자릿수가 1씩 증.. 2024. 12. 26.

티스토리툴바