본문 바로가기

Programming456

#1395 스위치(Segment Tree) 이번 문제는 Platinum III 난이도로 매겨진 좀 난이도가 있는 문제입니다. 기본적으로 이용하는 자료구조는 세그먼트 트리입니다. 세그먼트 트리 자료구조는 제가 나중에 한번 알고리즘적 적용 방법에 대해서 이야기하고자 합니다. 백준 사이트에서 세그먼트 트리와 관련된 문제가 꽤 여러개가 보입니다. 다 난이도가 높게 책정된 문제들입니다. 그런데 세그먼트 트리는 하나의 데이터를 업데이트할 때, \(O(\log N)\) 의 데이터 효율을 가집니다. 그리고 범위에 대해서 연산결과를 내는 것도 역시 \(O(\log N)\)의 효율을 보입니다. 그런데, 범위로 데이터를 업데이트한다고 할 때에는 이게 쉽지 않습니다. 해당 범위내의 것을 모두 업데이트를 일일이 한다고 하면, 세그먼트 트리를 쓰지 않고 배열 자료구조가 .. 2020. 2. 14.
#79 암호 알아내기(Topology Sort) 이번문제는 난이도 5%로 아주 쉬운 문제로 분류되어 있습니다. 아마 단순무식(Brute Force) 방법으로도 풀리는 문제로 분류되어서인 듯 합니다. 숫자가 많지 않기 때문에 단순하게 조건에 맞도록 배열하는 것이 가능합니다. 예를 들어서 317 236 이 있다면, 총 숫자는 5가지 숫자가 쓰였으므로 5가지 숫자를 적절하게 배열한 다음에 조건에 맞는 수열을 고르는 것입니다. 일단 문제를 살펴본다면 다음과 같습니다. 주어진 숫자가 있습니다. 예를 들어서 531278이란 숫자가 있다면요. 이 숫자를 가지고 있음을 확인하면서, 네트웍 전송상에서 원래의 숫자를 알아내기 힘들게 하기 위해서 첫번째, 세번째, 다섯번째 숫자를 보내길 요구할 수 있습니다. 그러면 517을 전송하게 됩니다. 그런데 이러한 전송이 많아지면.. 2020. 2. 8.
[C/C++] 백준 #1377 버블 소트(안정적 정렬) 이번 문제는 난이도 Gold V입니다. 저는 이런 문제를 좋아합니다. 알고리즘의 기본을 잘 이해하는지 물어보는 문제이기도 하니까요. 정렬은 알고리즘을 배우면서 가장 먼저 배우는 알고리즘이기도 합니다만, 기본을 충실하게 알고 있는 사람은 많지 않습니다. https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 대부분 기본정렬은 선택정렬, 삽입정렬, 버블정렬이 있고, 고급정렬은 병합정렬, 힙정렬, 퀵정렬이 있고, 기본정렬은 \(O(N.. 2020. 2. 5.
[C/C++] 백준 #1365 꼬인 전깃줄(가장 긴 증가하는 부분수열) 백준 알고리즘 사이트에서 많이 나오는 문제 중 하나가 가장 긴 증가하는 부분수열(LIS; Longest Incremental Subsequence)입니다. https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 수열에 있는 수들 중 일부(연속되지 않아도 상관이 없습니다.)를 선택해서 그 순서가 증가하는 수열이면 증가하는 부분 수열입니다. 여기서 문제는 그 증가하는 부분 수열의 길이가 가장 긴 경우가 얼마인지입니다. 가장 일반적인 해법은 .. 2020. 2. 4.
#1354 무한 수열 2(Dynamic Programming) 이번 문제는 #1351과 같은 문제이지만, 숫자 범위가 좀 더 커지고, 두개의 숫자 인덱스를 계산하는 것이 좀 다릅니다. 그러다 보니 제한시간이 2초에서 10초로 대폭 늘었습니다. 난이도도 Gold IV에서 Gold III로 조금 높게 평가되었습니다. 그렇지만 똑같이 동적 프로그래밍을 이용하고 있고, 동적 프로그래밍상 히트율이 많이 낮아져서 시간이 많이 걸립니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //---------------------------------------------------------- // baekjoon #1354 - Infinity Series 2 // - by Aubrey Choi // - created at 2020-02-02 //---------------.. 2020. 2. 2.
#1353 합과 곱(Mathematics, Binary Search) 이번 문제는 Platinum V 난이도로 설정된 문제입니다. 정답자도 39명뿐입니다. 난이도에 비해서 많이 풀지 않은 문제입니다. 수학적 지식으로는 산술평균과 기하평균의 대소 비교만 알고 있으면 쉽게 풀 수 있습니다. 수열 A가 있는데, 이 수열에 있는 수들을 합하면 S, 곱하면 P의 값을 가집니다. 예를 들어서 { 1, 3, 2 } 수열이라면, S=6, P=6이 됩니다. 문제는 이러한 S와 P가 주어질 때, 만족하는 양의 실수 수열의 최소 크기를 구하라는 것입니다. 문제에서는 음이 아닌 실수이지만, P의 범위가 1 이상이므로 양의 실수만 생각해도 됩니다. S=6, P=6 이라면, { 1, 3, 2 } 도 되지만, { 6 } 도 가능하므로, 최소 수열의 수 갯수는 1이 됩니다. 이 문제를 풀기 위해서는 .. 2020. 2. 1.
728x90

티스토리툴바