본문 바로가기

Algorithm

[Baekjoon]백준 17299 오등큰수(골드 3) - Python 문제를 살펴보면 이전 문제와 거의 유사하지만, 등장횟수에 따라 결정된다는 점에서 차이가 있다간단하게 이전 동작 과정은 설명하였기 때문에 이 글에서는 과정을 직접 예시로 서술하도록 하겠다일단, 딕셔너리를 활용하여 각 원소가 몇 번 등장하였는지 저장하고 이를 저장하는 리스트를 따로 만들어주었다이후에는 이전 문제와 동일하게 작성하면 되는데, 해당 for문을 i의 수에 따라 예시를 보여주도록 하겠다new 3 3 2 1 1 2 3 ( count 결과 저장 )ngf  1 1 2 3 4 2 1  ( 입력값 )▶ i = 0일 때stack 0 result -1 -1 -1 -1 -1 -1 -1stack에 아무것도 없던 상태였기 때문에 stack.append(i)만 실행되어 stack에 0이 저장된다result에는 아무 변.. 더보기
[Baekjoon]백준 17298 오큰수(골드 4) - Python 문제를 살펴보면 특정 index에서 오른쪽에 존재하는 수 중에서 큰 값을 찾으면 된다대신 그냥 큰 값이 아니라 가장 왼쪽에 위치한 큰 값이다 i의 오큰수를 찾는다고 가정하면 i+1, i+2...를 거듭하면서A[i] 값보다 더 큰 값이 존재하면 출력하고 끝 index까지 갔음에도 불구하고 없다면 -1을 출력한다 2개의 for문을 사용하면 O(N^2)의 시간복잡도가 소모되므로 스택을 활용하여 더 빠르게 연산할 수 있다원래는 스택에 입력받은 값을 차례대로 넣어서 값들을 확인해볼까라는 생각을 하였는데, 해당 방법은for문 2개 사용하는 것과 큰 차이가 없다는 생각이 들었고, 그래서 stack 리스트를 index 저장용으로사용하여 코드를 작성하였다 원래 결과값도 매번 append()를 통해 값을 저장하려고 했으나.. 더보기
[Baekjoon]백준 9935 문자열 폭발(골드 4) - Python 문제는 간단하다 첫번째 입력받은 문자열에 두번째로 입력받은 문자열이 존재하지 않을 때까지 삭제하면 된다예전에 이를 풀어본 적이 있긴하지만, 그때와는 조건이 다름에도 불구하고 혹시나 하여 find함수를 통해 index를 찾고, 슬라이싱을 통해 문자열을 만드는 과정을 코드로 작성하여 제출하였다import sysinput = sys.stdin.readlinetext = input().strip()Explosion = input().strip()while True: findidx = text.find(Explosion) if findidx == -1: break text = text[:findidx] + text[findidx + len(Explosion):] p.. 더보기
[Baekjoon]백준 7579 앱(골드 3) - Python 문제를 살펴보면 N개의 메모리의 바이트 수와 비용이 주어져있다 그리고 M 바이트를 확보하기 위하여지불해야하는(?) 비용의 최솟값을 구하는 것이 문제이다예제를 통해 설명하자면 60바이트를 확보하기 위해 30 10 20 바이트를 각각 활용하여 6의 비용으로60바이트의 메모리 확보가 가능하다 그리고 이 값은 최솟값이 된다(20 40 의 경우 3+4, 총 7의 비용이 들기 때문) 그래서 이번엔 어떠한 점화식을 구해야할지 고민을 해보았다처음에는 dp[필요한 바이트 수]로 구현을 해보다가 과정이 매끄럽지 않아서dp를 2차원 배열로 생각해보다가 dp[i][j](i번째 앱까지 j 비용으로 가능한 최대 byte)로 선언하여 코드를 작성하였다 그냥 머릿속으로 생각하기에는 복잡하여서 표를 그린 후에 코드를 작성할 수 있었다.. 더보기
[Baekjoon]백준 2293 동전 1(골드 4) - Python, C++ 문제를 살펴보면 그리디 알고리즘의 거스름돈 문제가 약간 생각나게 되는 문제이다동적 프로그래밍 알고리즘의 핵심은 점화식을 찾는 것이다그래서 점화식을 어떻게 만들어서 어떻게 값을 넣을지 고민해보았는데, index를 n원을 만드는 경우의 수로설정하여 점화식을 찾아보고자 노력하였다 예를 들어 dp[2]의 경우라면 2원을 만드는 경우의 수, dp[5]라면 5원을 만드는 경우의 수가 들어가도록 설정하였다이제 이 값을 어떻게 설정할 지가 고민인데, 일단 예제를 보고 직접 값을 넣어가면서 규칙을 찾아보았다우선, 동전 1을 통해 만들수 있는 경우의 수는 모두 1이다이후 동전 2를 사용한다고 가정할 때, 동전 2를 사용해서 1원을 만들수는 없기 때문에dp[1]의 값은 더이상 갱신되지 않고 값이 확정된다는 사실을 알 수 있.. 더보기
[Baekjoon]백준 2629 양팔저울(골드 3) - Python, C++ 해당 문제는 해당 추의 개수를 가지고 원하는 무게를 만들수 있는지에 대해 물어보는 문제이다예제 2번을 보면 구슬 4개를 가지고 1, 4, 10을 만들어야한다1의 경우 3과 2, 4의 경우 3, 3과 2로 만들수 있고 10의 경우 2, 3, 3, 3의 추로는 만들수 없기 때문에 N이 출력된다 일단 dp라는 배열에 어떠한 값을 넣을지 고민해보았다 사실상 이것이 동적 프로그래밍의 핵심이다dp[사용한 추의 개수][무게 차이]를 기준으로 1이라는 값을 넣어주고 나머지는 0으로 초기화한다그렇게 하게 되면 함수를 재귀적으로 호출할 때 1인 경우 바로 return을 함으로써 불필요한 계산을 하지 않는다또한 구슬이 기존에 입력된 수보다 더 큰 경우에도 바로 return을 하여준다def sol(num, wg): if.. 더보기
[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의 크기를 더 크게하였더니 오류가 .. 더보기

티스토리툴바