본문 바로가기
반응형

분류 전체보기123

백준 12865. 평범한 배낭 🅰 백준 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 ✏️ 문제 풀이 먼저 버틸수 있는 무게 K만큼 반복하면서 현재의 물건이 가방에 넣을 수 있는지 확인해서 dp를 수행한다. product배열에 물품들의 무게, 가치를 저장해주고 dp배열은 N+1,kg+1로 생성해준다 2중 for문을 사용하면서 바깥 for문에는 물품의 수만큼 반복하고, 안쪽 for문에는 넣을수 있는 무게만큼(kg) 반복해준다 예제 입력 데이터 4 7 .. 2021. 9. 26.
백준 2294. 동전 2 🅰 백준 2294. 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net ✏️ 문제 풀이 coin배열에 사용할 수 있는 동전을 전부 저장한다. 이중for문을 이용해서 바깥쪽 for문에는 coin의 개수만큼 반복하고, 안쪽 for문에는 가치의 합인 k만큼 반복을 한다 점화식 : if(j-coin[i] >= 0 && D[j-coin[i]!=max_value) : D[j] = min(D[j], 1 + D[j - coin[i]]) 만약 j를 현재 coin[i]로 계산할 수 있고, 이.. 2021. 9. 26.
백준 11066 파일합치기 https://kyunstudio.tistory.com/75 [C++] 백준 11066 - 파일 합치기(동적 계획법, 이후에 다시 보자) 0. 주어진 문제 파일 합치기 성공 한국어 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 7555 3967 2521 51.862% 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데 kyunstudio.tistory.com https://developerbee.tistory.com/97 [알고리즘 / 백준] 11066 - 파일 합치기 www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한.. 2021. 9. 26.
백준 1890. 점프 🅰 백준 1890. 점프 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net ✏️ 문제 풀이 dp에 현재 경로값을 저장해서 나감 배열 전체를 탐색하는 것이 아니라서 시간이 오래 안걸림 이중for문을 통해 배열을 반복하면서 이동할 수 있는지 확인 한 후, 이동 가능하면 check배열에 갈수있는 경로에 현재 check의 개수를 더해준다 배열을 확인 다 하면 마지막 지점이 정답이 된다. ✏️ 소스코드 package dp; import java.io.*; import java.util.*; public cla.. 2021. 9. 23.
백준 11048. 이동하기 🅰 백준 11048. 이동하기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net ✏️ 문제 풀이 dp로 생각해보면 한 좌표에서 올 수 있는 값은 위, 왼쪽, 왼쪽 위 대각선 3가지 이다. 가져올 수 있는 사탕의 최대값을 구해야 하기 때문에 이전 3가지 값 중 최적의 값을 가져오면 된다. 하지만 첫째줄 행, 첫째줄 열은 대각선탐색, 위, 왼쪽 탐색등에 제약이 있으므로 basevalue로 값을 넣어주고 나머지 행에 대해서 이전 값 중 최적값을 구해서 마지막 map[N][M]이 정답이 된다. ✏️ 소스코.. 2021. 9. 23.
[2021-09-23] Sliding Window Sliding Window - 배열이나 리스트 요소의 일정 범위(k개)의 값을 비교할 때 사용하면 유용한 알고리즘 - 서브 배열의 요소를 순회하다 보면 중복되는 요소들이 존재하고 이 중복된 요소를 재사용하는 방법 - 방법 1. 윈도우(일정 범위의 요소 ==> k개)의 요소를 원하는 방법으로 처리 2. 윈도우의 시작부분을 빼고, 윈도우 맨 끝에 새 요소를 추가 ex) 2, 4, 7, 10, 8, 4, 6, 5, 7, 1 정수로 이루어진 배열에서 길이가 4인 서브 배열의 합이 가장 큰 서브 배열 구하기 시간복잡도 O(N) 2021. 9. 23.
백준 2293. 동전 1 🅰 백준 2293. 동전 1 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net ✏️ 문제 풀이 0.5초의 시간제한과, 4MB의 메모리 제한이 있기 때문에 1차원 배열로 풀었다. 예제를 이용해서 설명을 하면 || 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 dp[] = 1 1 1 1 1 1 1 1 1 1 2 0 1 1 2 2 3 3 4 4 5 dp[] = 1 2 2 3 3 4 4 5 5 6 5 0 0 0 0 1 2 2 3 3 4 dp[] = 1 2 2 3 4 6 6 8 8 10 동전.. 2021. 9. 22.
[Kruskal Algorithm] 크루스칼 알고리즘(feat. Union-find) 크루스칼 알고리즘을 이해하기 위해서는 신장트리, 최소 신장트리에 대한 개념을 먼저 이해해야 한다. 신장트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. * 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 이렇게 서로 사이클이 발생하지 않고 모든 정점을 잇는 경로를 신장트리라고 한다. 그럼 최소신장트리(MST)란 무엇일까? 최소 신장 트리(MST)란 최소한의 비용으로 구성되는 신장 트리를 말한다. 이처럼 간선에 대한 가중치가 주어졌을 때 최소한의 가중치를 가지고 모든 정점을 잇는 트리이다. 이제 크루스칼 알고리즘에 대해 알아보겠다 크루스칼 알고리즘이란 MST를 구하는 방식 중 하나로 간선의 가중치의 합이 최솟값이 되도록.. 2021. 9. 16.
[Union Find, Disjoint Set] 유니온 파인드 함수 구현 방법(재귀 사용!) 백준 1717번 문제를 풀 때 UnionFind를 사용하였다. 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net Union Find는 그래프알고리즘의 일종으로 여러노드가 존재할 때 각 노드가 연결되어 있는지를 집합을 이용하여 확인하는 방식이다. Union Find를 하기위해서는 크게 3가지의 함수가 필요하다. (꼭 필요한 함수는 2가지 이다) 1. make()함수 - 먼저 각 노드들의 부모노드를 저장할 parents배열을 초기화 시켜준다. (parents 배열을 만드는 .. 2021. 9. 12.

티스토리툴바