[백준 / 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

[백준 / C언어] 11050번: 이항 계수 1

https://www.acmicpc.net/problem/11050 난이도: solved.ac 브론즈 1 이 문제는 다이나믹 프로그래밍을 이용해서도 풀 수 있지만, 그건 이다음에 업로드할 11051번 문제(실버 2)에서 서술하겠다 (수의 범위만 더 커지고 똑같은 문제임) 브론즈 문제 답게 쉬운 방식으로 풀어보자 조합 공식을 그대로 코드로 옮기는 것이다 [조합 공식] 맨 오른쪽에 있는 변은 조금 복잡해 보이지만 사실 간단하다 N부터 시작해 1씩 작은 수를 K개 만큼 곱한 것을 K!로 나눈 것이다 (예시) 아래는 이를 그대로 코드로 옮긴 것이다 #define _CRT_SECURE_NO_WARNINGS #include int main() { int N, K, com = 1, i; scanf("%d %d", &..

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

[백준 / C언어] 1654번: 랜선 자르기

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 난이도: solved.ac 실버 2 이분 탐색(Binary Search), 매개변수 탐색(Parametric Search)을 활용하면 O(log n)의 시간 복잡도로 풀 수 있는 문제다 N개의 랜선을 입력받을 때 배열에 저장하는 동시에 최대값을 찾아 그 최댓값을 right라고 두고 left는 길이가 1인 가상의 랜선으로 두었다 그리고 while문 안에서 mid = (l..

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