[백준 / C언어] 14501번: 퇴사

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 난이도: solved.ac 실버 3 실버 3치고 어려웠다... 다른 분들은 맨 마지막 날부터 거꾸로 계산하던데 나는 정직하게 첫 날부터 계산했다ㅋ (거꾸로 계산하는 센스는 dp 문제를 많이 풀어봐야 얻을 수 있나보다...) 내 풀이를 예제 입력 1을 통해 설명해보겠다 예제 입력 1 7 3 10 5 20 1 10 1 20 2 15 4 40 2 200 우선 크기가 N + 1인 1차원 dp 배열을 만든다 (나는 N의 범위를 1000까지로 잘못 봐서 메모리를 적게 하려고 동적할당했는데, 정적할당으로 해도 괜찮을 것 같다) 일단 1일차. 1일..

• format_list_bulleted PS/백준
• · 2023. 5. 15.
• textsms

[백준 / C언어] 10845번: 큐

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아..

• format_list_bulleted PS/백준
• · 2023. 5. 15.
• textsms

[백준 / C언어] 1260번: DFS와 BFS

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 난이도: solved.ac 실버 2 DFS와 BFS를 구현하는 문제다 graph라는 2차원 배열을 통해 각 정점끼리 연결된 것을 표현하고 각 정점을 방문하면 visited라는 배열의 해당 index 값을 1로 바꿔주었다 그리고 BFS 한정으로 큐(Queue)를 사용했는데 front와 rear라는 변수를 통해 enqueue, dequeue할 때의 위치를 나타내었..

• format_list_bulleted PS/백준
• · 2023. 5. 14.
• textsms

[백준 / C언어] 12865번: 평범한 배낭

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Knapsack Problem으로 유명한 문제다 이 알고리즘에 대해 설명해보려고 했는데 너무 길어지고 글로 설명 못하겠어서 포기했다...ㅠ 대신 내가 참고했던 유튜브의 링크를 첨부할 테니 이 알고리즘에 대해 이해가 되지 않는 분이 본다면 분명 도움이 될 것이다 https://youtu.be/nLmhmB6NzcM https://you..

• format_list_bulleted PS/백준
• · 2023. 5. 14.
• textsms

[백준 / C언어] 15649번: N과 M (1)

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도: solved.ac 실버 3 1부터 N까지의 숫자에서 M개를 중복없이 골라 각기 다른 순서로 섞어 나열하는 순열을 만들어내는 문제다 이는 DFS를 활용한 백트래킹으로 해결할 수 있다 우선 출력할 숫자는 배열 arr에 담아두었고 배열 used에는 각 인덱스에 해당하는 숫자가 배열 arr에 저장되었다면 1, 저장되지 않았다면 0을 담았다 그리고 idx가 M이 되면 배열 arr에 저장했던 수를..

• format_list_bulleted PS/백준
• · 2023. 5. 13.
• textsms

[백준 / C언어] 11051번: 이항 계수 2 (파스칼의 삼각형)

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 난이도: solved.ac 실버 2 앞에서 다룬 문제 (이항 계수 1)의 확장판(?)이다 N과 K의 범위가 1000까지로 늘어났다 이 문제는 파스칼의 삼각형을 이용하면 쉽게 풀 수 있다 파스칼의 삼각형의 공식을 dp 점화식으로 만드는 건데, 이에 대해 설명해 보겠다 우선 파스칼의 삼각형은 아래와 같다 이 파스칼의 삼각형은 아래의 이항계수로부터 만들어진 건데 각 수는 한 칸 왼쪽 위와 한 칸 오른쪽 위의 수의 합이라는 특징이 있다 이를 수식으로 나타내면 다음과 같다 근..

• format_list_bulleted PS/백준
• · 2023. 5. 12.
• textsms