Algorithm/BOJ47 BOJ 12865 - 평범한 배낭(dp, knapsack) 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 - 가방에 넣는 물품의 갯수가 최대 100개여서 dfs로 풀면 넣고 안넣고의 경우의 수가 2^100 이기 때문에 O(N^2)가 아닌 다른 방식으로 풀어야한다. 이런 경우 greedy 방식이나 dp 메모이제이션 방식을 고민해볼 수 있다. 조건에서 가방의 제한무게가 10만이하로 주어졌기 때문에 d[i][j] = max(i번째 물건까지 .. 2021. 8. 19. BOJ 10216 - Count Circle Groups(유니온 파인드, 서로소 집합) https://www.acmicpc.net/problem/10216 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net - 문제에서 주어진 조건에 따라 노드가 연결되었는지를 체크하는 함수, 연결되었다면 union 연산을 통해서 같은 집합임을 체크해준다. - 이 문제에서 찾을 수 반례로 1 3 0 0 1 2 2 1 0 2 1 가 있다. 처음 두 노드는 연결이 안되어있는데 그 사이에 0,2 노드가 생기면서 모두 같은 집합이 되는 그런 케이스이다. 그래서 모든 노드를 n번 검사하는 On^2 방식으로 .. 2021. 8. 17. BOJ 21608 - 상어초등학교(정렬, 구현) https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net - 삼성 기출인 상어시리즈를 풀다보면 어느새 문제에서 시키는 데로만 짜는 기계가 된 듯한 기분이 든다. dfs, bfs식으로 상하좌우를 순회하면서 배치를 하는 패턴이 다 똑같아서 모든 상어문제들을 풀어보면 이후로는 이런 구현류의 문제유형이 쉽게 느껴지는 것 같다. - 그럼에도 살짝 시간이 걸리는 문제 포인트는 학생 정보랑 자리배치는 별개의 개념이라는 것이다. 그래서 구조체를 따로 만들어.. 2021. 8. 17. BOJ 11066 - 파일 합치기(DP) https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net - 여러 개의 파일을 1개가 남을 때까지 합쳤을 때의 최소비용을 구하는 문제이다. - 페이지를 합치는 부분문제들의 합을 구해야되므로, overlapping subproblem이 있고, 그 중 최소값을 구해야되므로 optimal substructure에 해당된다. 그래서 DP로 접근할 수 있다. - 탑다운 방식 #include #include using namespace std; #defi.. 2021. 8. 17. 이전 1 2 3 4 5 6 ··· 12 다음
