'분류 전체보기' 카테고리의 글 목록 (13 Page)

⛹️ 라이프/2020 겨울방학 모각코(개인)

[코독하구만 팀] 2021.01.27(수) - 6주차 개인 목표

2021.01.27

- 목표 - 다이나믹 프로그래밍의 개념을 실습 문제를 통해 학습하고, 이를 응용하여 백준 문제에 적용해본다. 1. 피보나치 피보나치 수열의 N번째 항을 출력하시오. [입력 값] 0 [출력 값] 0 [입력 값] 5 [출력 값] 5 [입력 값] 20 [출력 값] 6765 2. 가방 가방에 물건을 넣어 옮기려한다. 배낭에는 넣을 수 있는 물건 크기에 한계가 있으며, 각 물건은 크기와 가치가 부여되어있다. 배낭에 넣을 수 있는 물건들의 최대 가치를 구하시오. [입력 값] 5 # 배낭 크기 4 # 물건 개수 2 3 4 5 # 물건 크기 3 4 5 6 # 물건 가치 [출력 값] 7 3. 제재소 재목을 만드는 제재소에는 재료로 들어온 나무를 정확히 K미터로 자르는 기계가 있다. 재료로 들어온 나무 관리를 위하여, 나..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 11053번. 가장 긴 증가하는 부분 수열

2021.01.25

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 해결 방법 a[i]를 입력된 수열, dp[i]를 i번째까지 가장 긴 증가하는 부분 수열의 길이라고 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 2156번. 포도주 시식

2021.01.25

www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 입력 첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다. 출력 첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다. 해결 방법 포도주를 마실 수 있는 방법은 어떻게 될까? dp를 n번째 잔까지 마실 때 가장 많은 양의 포도주, grape를 n번째 잔의 포도..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 10844번. 쉬운 계단 수

2021.01.24

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 해결 방법 우선 규칙을 찾을 필요가 있다. 길이가 1인 계단의 수는 몇 개가 있을까? 1 2 3 4 5 6 7 8 9 답은 9개 그럼 길이가 2인 계단의 수는? 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 답은 17개 규칙이 보이는가? 보이지 않아도 된다. (본인도 푸는데 오래걸렸으니... 이 문제 많이 어려웠..

⛹️ 라이프/2020 겨울방학 모각코(개인)

[코독하구만 팀] 2021.01.20(수) - 5주차 개인 결과

2021.01.22

- 목표 - codekodo.tistory.com/33 [코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표 - 목표 - 네트워크 유량을 계산하는 포드 풀커슨 알고리즘의 개념을 학습하고, 이를 정리한다. 위상정렬과 A* 알고리즘의 개념도 추가적으로 학습한다. 이후 실습 문제와 백준 문제를 통해 이를 codekodo.tistory.com 1. 위상 정렬 선행 과목이 있는 경우 선행 과목을 출력하고 이후에 연계된 과목을 출력하는 문제였다. 과목명이 처음에 주어지므로 이 과목명을 dict형으로 저장한다. M개의 입력 값에서 선행 과목, 후행 과목이 입력되는데 선행 과목이 있는 경우 이를 count 해준다. count가 0이면 이는 선행 과목이 없는 경우이다. 이후 BFS를 통해 과목 이수 순서를 탐..

✏️ 알고리즘/Graph

2. DFS(Depth-Find-Search) : 깊이 우선 탐색

2021.01.22

DFS(Depth-Find-Search) 깊이 우선 탐색 지난 시간 BFS에 이어 오늘은 DFS에 대해 알아보려고 한다. DFS는 Depth-Find-Search로 깊이 우선 탐색이다. BFS와 다르게 DFS는 깊이를 우선적으로 탐색한다. 즉 최대 깊이까지 재귀적으로 이동한 후 최대 깊이에 도달한 경우 옆으로 이동한다. 또한 BFS에서는 Queue를 사용했다면 DFS에서는 Stack을 사용한다. 이 Stack에 저장된 값이 우리가 원하는 DFS의 탐색 순서이다. 알고리즘 동작 방식 다음과 같다. 1. 특정 정점이 아직 방문하지 않은 정점인 경우 이를 방문처리 해준다. 2. 해당 정점과 연결된 다른 정점에 대해 위 과정을 반복한다. 다음과 같은 그래프가 주어졌을 때 DFS를 적용해보자. ① 시작 정점을 8..

✏️ 알고리즘/Graph

1. BFS(Breath-Find-Search) : 너비 우선 탐색

2021.01.21

BFS(Breath-Find-Search) 너비 우선 탐색 그래프의 탐색 방법 중 하나의 BFS에 대해서 살펴보려고 한다. BFS는 말 그대로 너비 우선 탐색, 즉 특정 Vertice에서 가장 가까운 Vertice부터 탐색한다는 뜻이다. 우선 BFS를 사용하기 위해서는 Queue가 필요하다. Stack, Queue, Heap에 대해서는 나중에 자세히 설명하기로 하고 Queue에 대해 간단하게 설명하자면 FIFO(First in First out - 선입선출)으로 동작하는 자료구조이다. 위에서도 말했듯이 BFS의 가장 큰 개념은 가까운 정점을 방문하되, 아직 방문하지 않은 정점인 경우 방문 리스트에 정점을 저장하면 된다. 이 방문 리스트가 우리가 원하는 최종적인 BFS의 탐색 순서이다. 알고리즘 동작 방식..

⛹️ 라이프/2020 겨울방학 모각코(개인)

[코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표

2021.01.20

- 목표 - 네트워크 유량을 계산하는 포드 풀커슨 알고리즘의 개념을 학습하고, 이를 정리한다. 위상정렬과 A* 알고리즘의 개념도 추가적으로 학습한다. 이후 실습 문제와 백준 문제를 통해 이를 응용한다. 1. 위상 정렬 2. 정글의 법칙 3. 기름이 간당간당 4. 백준 2188번 - 축사배정 백준 2188번 - 축사배정 (www.acmicpc.net/problem/2188) 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 1463번. 1로 만들기

2021.01.19

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 입력 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 해결 방법 우선 규칙을 찾아보자. 계산식의 경우 여러가지 경우의 수가 나올 수도 있다. N 연산 횟수 계산식 1 1 1 2 1 2/2=1 3 1 3/3=1 4 2 (4-1)/3=1 5 3 (5-1)/2/2=1 6 2 6/3/2=1 7 3 (7-1)/3/2=1 8 3 8/2/2/2=1 9 2 9/3/3=1 10 3 (10-1)/3/3=1 어떤 규칙을 찾을 수 있을까? 우선 수가 1씩 커질 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 2579번. 계단 오르기

2021.01.14

www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 입력 입력의 첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다. 출력 첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다. 해결 방법 dp 문제이므로 점화식을 찾아야한다. 도착지점에 갈 수 있는 방법은 어떻게 될까? 두 ..

티스토리툴바