본문 바로가기

Algorithm

[Baekjoon]백준 11066 파일 합치기(골드 3) - C++, Python 문제를 살펴보면 파일을 병합하는 과정에서 최소한의 비용이 되도록 하는 경우의 수를 찾아야한다그래서 동적 계획법 알고리즘이 제일 효율적일것이라 생각하였고, 부분합을 구하는 리스트 하나와각 구간별 최솟값을 구하기위한 리스트 하나가 있어야한다고 생각하였다일단, sum[j+1] = sum[j] + tmp와 같은 방식으로 하나의 값을 입력받음과 동시에 구간별 합을 구하도록 작성하였다이후에 두 개의 for문을 통하여 index를 이동하며 동적 계획법의 결과물 즉, 구간별 최솟값을 갱신한다첫번째 for문에서는 구해야할 범위를 지정하고 두번째 for문에서는 합치는 범위의 시작 지점을 지정하게 된다예시를 들어보자면1 2 3 4 5와 같은 숫자가 주어져있을때 첫번째 for문의 range가 3이라면 두 번째 for문의 st.. 더보기
[Baekjoon]백준 11286 절댓값 힙(실버 1) - Python 문제를 살펴보면 이번에는 절댓값을 기준으로 최소힙을 구현하여야한다그렇다고 해서 절댓값으로 바꾸어 힙에 넣거나, 출력하는 것이 아니기 때문에 기존의 값도 저장되어야한다그래서 최소힙과  최대힙을 둘 다 만들어 이를 저장하고 결과를 출력하는 방법을 선택하였다 음수의 경우 부호를 양수로 바꾸어 최소힙으로 구현하되, 값을 넣고 출력할 때 부호만 바꾸어주면절댓값으로 값을 비교할 수 있게 된다 양수의 경우 그대로 최소힙으로 구현하면 된다해당 방법을 사용하면 max_heap에는 음수의 절댓값이 작은 값부터 저장되어있을 것이고, min_heap에는 양수가 작은 값부터 저장되어있을것이다 그렇다면 절댓값을 비교할 때에는 min_heap[0]과 max_heap[0]을 비교하면 된다import sysimport heapqinp.. 더보기
[Baekjoon]백준 1927 최소 힙(실버 2) - Python, C++ 문제를 살펴보면 이전에 풀었던 최대 힙의 반대 문제이다 이때는 파이썬으로 풀이를 작성할 때import heapq를 선언한 후에 일부러 자연수에 -를 붙여 음수의 값으로 힙에 넣어주었다하지만 이번 문제는 최소 힙이기 때문에 기존의 코드에서 -만 빼면 정상적으로 동작하는 것을 확인할 수 있다https://reflesh02.tistory.com/135  [Baekjoon]백준 11279 최대 힙(실버 2) - Python문제를 살펴보면 최대 힙을 이용하여 자연수를 넣고, 0을 입력하게 되면 가장 큰 값을 출력함과 동시에해당 값을 배열에서 제거하면 된다 파이썬에는 heapq라는 모듈이 존재하지만 이는 최소 힙reflesh02.tistory.com해당 코드에서 -만 빼면 정답임을 확인할 수 있다import sys.. 더보기
[Baekjoon]백준 11279 최대 힙(실버 2) - Python 문제를 살펴보면 최대 힙을 이용하여 자연수를 넣고, 0을 입력하게 되면 가장 큰 값을 출력함과 동시에해당 값을 배열에서 제거하면 된다 파이썬에는 heapq라는 모듈이 존재하지만 이는 최소 힙이 구현되어 있기때문에 자연수를 넣을 때, -1, -2와 같은 방식으로 넣게 되면 최대힙으로 구현할 수 있다 최대 힙에 대해 간단하게 설명하기 위해 최대 트리에 대해 설명이 필요하다최대 트리란 각 노드의 key값이 그 자식의 key값보다 크거나 같은 트리이다최대 힙은 이런 최대 트리의 특징을 가지면서 동시에 완전 이진 트리라는 점이 특징이다완전 이진 트리는 노드를 삽입할 때 왼쪽부터 차례대로 삽입한다는 점이 있다         1     2     34 와 같은 형식이라고 생각하면 되며, 만약 다음과 같은 형식이라면 .. 더보기
[Baekjoon]백준 12015 가장 긴 증가하는 부분 수열 2(골드 2) - C++, Python 문제를 살펴보면 이전에 풀이하였던 문제(11053)과 동일한듯 하나, 수열 A의 크기가 1,000에서 1,000,000으로늘어난 상태이다 따라서 이전에 풀이하였던 방식으로 작성할 경우 시간 초과 또는 메모리 초과가 발생할 수 있다해당 문제를 어떻게 풀이를 하였나 살펴보니 동적 프로그래밍으로 작성한 사람도 많았지만, 필자의 제출 풀이 코드를 확인해보니 이분 탐색을 사용하여 해결한 코드를 사용하였다 대신직접 이분 탐색 함수를 구현하지는 않았고, 파이썬에 이미 정의된 from bisect import bisect_left를 사용하였다그래서 이분 탐색을 연습하는 목적이므로 직접 이분 탐색 함수를 구현하여 코드를 작성하였다 C++로 코드를 작성함에 앞서, 문제에서 주어진 최대 크기를 기준으로 배열을 두 개 만들어.. 더보기
[Baekjoon]백준 1300 K번째 수(골드 1) - C++, Python 문제자체는 매우 간단하다 N×N인 배열 A에는 A[i][j] = i×j의 규칙으로 값이 들어가게 된다이후 배열 B에 A의 값들을 오름차순으로 넣고, K번째 위치한 수의 값을 구하면 되는 문제이다사실 이분 탐색 단계임을 모르고 이 문제를 접하였다면, 감을 잡는데 꽤나 오랜 시간이 걸렸을 것 같다이분 탐색 단계임을 알기 때문에 이를 고려하여 규칙성을 찾고자 노력하였다 그리고 당연한 부분에서 규칙을 찾을 수 있었다어떠한 배열에서 이를 오름차순으로 정렬하였을 때, k번째 index의 값인 J는 해당 배열에서 k번째로 작거나 같은 수이며, 이를 다르게 해석하면 J보다 작거나 같은 수가 k개 있다는 뜻이다따라서 N, K를 입력받은 문제조건에서 K를 기준으로 숫자를 찾으면 정렬한 값을 따로 배열에 저장하지 않고숫자를.. 더보기
[Baekjoon]백준 2110 공유기 설치(골드 4) - C++, Python 문제를 살펴보면 공유기의 위치가 각각 주어진다 이후 C개의 공유기를 두어야하는데, 놔두었을 때각 사이의 거리를 최대가 되도록 만들어야한다이전에 이분탐색 단계에서 계속해서 풀었기 때문에 이번에도 기준을 쉽게 정할 수 있었다 일단 각 거리에 대한 정보를 sort()를 통해 정렬을 해주어 가장 긴 거리가 마지막 index에 위치하도록 하였다그리고 시작 지점(최소거리)을 1, 끝지점(가장 먼 두 집 사이의 거리)을 첫 지점에서 끝지점까지의최대 거리로 설정하여 값을 갱신하며 공유기를 놓을 수 있는 경우의 수에 대해 조사하게 된다여기서 중요한 점은 이 문제는 다른 문제들과 다르게 거리에 따라 공유기를 두어야하기 때문에이전에 위치한 공유기의 위치를 저장해주어야한다 따라서 prev_house라는 변수를 추가해주었다그리.. 더보기
[Baekjoon]백준 2805 나무 자르기(실버 2) - Python, C++ 문제를 살펴보면 이전에 풀이한 문제(백준 1654 랜선 자르기)와 유사하다이번에는 나무를 잘라서 들고가야하는데, 그 자른 나무의 총 길이의 합이 목표치가 되도록 설정하여야한다저번 문제에서처럼 start, end를 각각 1과 나무의 최대 길이로 설정하여주었다이후 while문을 통해 자르고 난 후의 나무의 길이를 변수에 저장해주면 된다 대신 여기서 주의하여야할 점은저번 문제에서는 나눈 몫을 더하였지만 이번에는 잘랐을 때의 나무의 길이를 더해주어야한다는 점이다이를 고려하지 않았고, 잘못된 코드를 제출하였다Tree_num, need_length = map(int, input().split())Tree = list(map(int, input().split()))start, end = 1, max(Tree)whil.. 더보기

티스토리툴바