cpp 썸네일형 리스트형 [Baekjoon]백준 1520 내리막 길(골드 3) - C++, Python 문제를 살펴보면 제일 왼쪽 위에서 제일 오른쪽으로 이동할 때 아래에 위치한 숫자가 더 작은 경우에만아래로 이동이 가능하다는 조건이 있다우선 현재 지도의 상태를 입력받을 배열 하나를 선언해주고, 값을 저장할 2차원 배열을 하나더 선언해주었다해당 배열은 이전에도 사용하였던 동적 프로그래밍 알고리즘을 위해 만들어주었고,해당 문제에서는 dp[i][j]는 i부터 j까지 이동가능한 경로의 개수를 저장하게 된다 (코드를 직접 작성하고 수정하면서 두 배열과 높이, 가로 모두 전역변수로 선언하였음)#include using namespace std;int height, width;int dp[501][501] = {0, };int map[501][501] = {0, };이후 해결 과정을 위한 함수를 하나 만들어주었다 위.. 더보기 [Baekjoon]백준 11049 행렬 곱셈 순서(골드 3) - C++, Python 문제를 살펴보면 행렬을 곱하기 위해 필요한 곱셈 연산을 최소화하였을 때의 경우의 수를 찾는 문제이다행렬이 서로 곱해지기 위해선 a x b, b x c와 같이 행과 열의 개수가 같은 부분이 존재하여야한다그래서 이를 구현하기 위해 어떻게 해야할까...하면서 문제를 다시 보니 행렬의 순서를 바꾸면 안 되고, 항상순서대로 곱셈을 할 수 있는 크기만 주어지기 때문에 이를 고려하지 않고 정답을 찾아낼 수 있다 먼저 행렬을 저장할 2차원 배열을 하나 만들어주었다(matrix[502][2]) 뒤에서 설명하겠지만, 완성된 코드를 제출했더니out of bound 오류가 발생하였다 계산 과정에서 오류가 있는 줄 알고 다시 검토해보고 일부 수정해보았음에도오류가 지속적으로 발생하여 matrix의 크기를 더 크게하였더니 오류가 .. 더보기 [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]백준 1927 최소 힙(실버 2) - Python, C++ 문제를 살펴보면 이전에 풀었던 최대 힙의 반대 문제이다 이때는 파이썬으로 풀이를 작성할 때import heapq를 선언한 후에 일부러 자연수에 -를 붙여 음수의 값으로 힙에 넣어주었다하지만 이번 문제는 최소 힙이기 때문에 기존의 코드에서 -만 빼면 정상적으로 동작하는 것을 확인할 수 있다https://reflesh02.tistory.com/135 [Baekjoon]백준 11279 최대 힙(실버 2) - Python문제를 살펴보면 최대 힙을 이용하여 자연수를 넣고, 0을 입력하게 되면 가장 큰 값을 출력함과 동시에해당 값을 배열에서 제거하면 된다 파이썬에는 heapq라는 모듈이 존재하지만 이는 최소 힙reflesh02.tistory.com해당 코드에서 -만 빼면 정답임을 확인할 수 있다import sys.. 더보기 [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.. 더보기 이전 1 2 3 다음
