백준31 BOJ 1948 - 임계영역(그래프, 위상정렬) https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net - 문제에서 2가지를 요구하는데 하나는 DAG가 주어지고 시작노드부터 끝노드까지 가야하는데 여기서 가장 긴 경로를 찾는 것, 다른 하나는 그 경로에 포함된 엣지의 갯수를 찾는 것이다. * 위상정렬 구현 방식(bfs로 구현할 때) - dfs나 스택도 가능함 1. 각 노드들의 진입 차수 계산 2. 진입 차수가 0인 노드들을 큐에 삽입 3. 큐에서 노드를 꺼내 연결된 간선을 .. 2021. 8. 20. 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 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 ··· 8 다음
