본문 바로가기

분류 전체보기

 (21)
[2020모각코] 6회차 2021.01.27 값을 최소로 만들기 위해선 '-'뒤에 오는 '+'연산을 괄호로 묶으로 값이 최소가 될 것이라고 생각하였다. 따라서 입력을 받아 우선 '-'기준으로 문자열을 분리해 주었다. 그 후 '-'와 '-'사이에 있는 '+'연산을 괄호를 쳐서 먼저 계산을 한 후 '-'계산을 해주었다. 입력 조건을 보면 가장 처음과 마지막 문자는 숫자라고 했다. 따라서 문자열에서 첫번째 숫자는 무조건 양수가 된다. 그러므로 첫번째 값만 예외처리를 하여 계산해 주었다. 시작시간과 종료시간을 입력받아 종료시간을 기준으로 배열을 정렬해 주었다. 종료시간이 같은 경우도 있으므로 그럴 경우에는 시간시간이 더 빠른 쪽이 앞으로 오도록 Override를 작성했다. 종료시간으로 정렬이 되었다면 그 후로는 이전 종료시간과 시작시간을 비교하여 종료후에..
[2020모각코] 6회차 2021.01.27(목표) 6회차 모각표 목표 5회차에 공부했던 Greedy Algoalgorithm을 이용하여 아래의 백준 알고리즘 문제를 풀어보며 개념을 확립시킨다. 1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 1931번: 회의실 배정 (acmicpc.net) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net
[2020모각코] 5회차 2021.01.20 Greedy Algoalgorithm이란 문제를 해결하는 과정에서 전체에서의 최적이 아닌 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 방식이다. 거스름돈의 최대값이 500엔이고 500엔에서 100엔 ,50엔 ,10엔 ,5엔 ,1엔 으로 줄어들게 된다. /5, /2 연산이 반복해서 이루어지고 있으으모 boolean자료형을 이용하여 잔돈의 값을 자동으로 계산해 주었다. 동전의 갯수가 최소가 되기 위해선 가장 큰 잔돈부터 계산하면 동전의 갯수가 최소가 되게 된다. 따라서 가장 큰 잔돈인 500엔부터 계산을 하여 동전의 최소 갯수를 구하였다. 첫번째 도시에서는 무조건 기름을 넣어야 하기 때문에 첫번째 도시의 가격을 기준으로 프로그램을 작성하였다. 현재 기름 가격과 다음..
[2020모각코] 5회차 2021.01.20(목표) 5회차 모각표 목표 Greedy Algoalgorithm에 대해 이해하고 아래의 백준 알고리즘 문제를 풀어보며 개념을 확립시킨다. www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 13305번: 주유소 (acmicpc.net) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 ..
[2020모각코] 4회차 2021.01.13 이 문제를 해결하기 위해 dp라는 배열을 생성하였다. dp배열은 i번째 값을 증가하는 부분 수열의 마지막 값으로 가지는 부분 순열의 최댓값을 저장하는 배열이다. 따라서 dp배열이 최대인 경우 증가하는 부분 수열이 가장 큰 값을 가지게 된다. i번째 값이 이전에 있는 값보다 크면 이전의 dp값들과 비교하여 그 중 가장 큰값에 i번째 값을 추가하여 dp를 구하는 식으로 프로그램 하였다. 가방의 무게를 x축으로 , 포함 될 수 있는 물건을 y축으로 삼는 dp라는 2차원 배열을 만들어 모든 경우의 수를 저장하였다. i번째의 물건이 가방에 포함 될 수 있는 경우 이전 가치의 값과 i번째 물건이 포함된 가치의 값 중 최대값으로 dp의 값을 정하여 문제를 해결하였다.
[2020모각코] 4회차 2021.01.13(목표) 4회차 모각표 목표 3회차에 공부했던 Dynamic Programmin(동적 계획법)을 이용하여 백준 알고리즘 문제를 풀어보며 개념을 확립시킨다. www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째..
[2020모각코] 3회차 2021.01.05 동적 계획법(Dynamic Programming)이란 주어진 문제를 작은 여러 개의 문제로 나누어서 풀 때 같은 문제들을 반복해서 푸는 경우가 생긴다. 그런 경우 그 문제들을 매번 재계산 하는것이 아니라 값을 저장해 두었다가 재사용하는 기법이다. 문제를 보면 정수 x에 사용할 수 있는 연산 중 하나가 1을 빼는 연산이다. 따라서 bottom-up방식으로 문제를 해결해 나가야 한다고 생각하였다. a라는 배열을 만들어 1로 만드는데 필요한 연산의 횟수를 저장하여 문제를 해결하였다. sum이라는 변수를 통해 연속된 숫자의 합을 저장하였다. sum이 0보다 작게 되는 경우 그 부분순열을 연속합을 최대로 만들어 줄 수 없기 때문에 그 다음 값으로 새로운 부분순열을 만들어 주었다. sum1 변수에는 이전까지의 최대..
[2020모각코] 3회차 2021.01.05(목표) 3회차 모각표 목표 Dynamic Programmin(동적 계획법)에 대해 이해하고 아래의 백준 알고리즘 문제를 풀어보며 개념을 확립시킨다. www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net

티스토리툴바