알고리즘 (74) 썸네일형 리스트형 백준 9470 Strahler 순서 - 노드마다 count를 세야하는 위상정렬 문제 문제 링크 www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 풀이 아이디어 (처음 틀린 방식) 오랜만에 푸는 위상정렬 문제였다. 본인은 이 문제를 2번이나 틀리고 3번째만에 맞추게 되었는데, 2번씩이나 틀린 이유는 이 문제를 노드마다 count를 안 세고 야매로 풀려다가 된통 당했기 때문이다. 맨처음 틀린 접근 방식은 다음과 같다. 위상정렬로 순서대로 접근하는 건 다른 문제들과 똑같은 방식이니 패스하겠다. 처음에 int cost[1001]을 잡고, 해당 노.. 백준 2638 치즈 - 여러번 bfs를 돌려야하는 문제 문제 링크 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 풀이 아이디어 문제를 풀기 위해 핵심적으로 파악해야 하는 여부가 '치즈가 외부 공기와 2군데 이상 닿아 있는지 여부를 확인하자' 이다. 치즈가 전부 녹아 없어질때까지 이 여부를 확인해보면서 진행 해야한다. 주의할 것이 내부 공기는 외부 공기가 아니므로, 단순히 치즈 주변이 0으로 둘러 쌓여 있는가를 가지고 판단하면 안된다. 확실한 외부 공기로부터 bfs를 통해 치즈가 외부 공기와 닿아있는지 .. [프로그래머스] 2021 카카오공채 7번 매출하락 최소화-가장 쉽게 트리 dp로 푸는법, 쉬운설명 문제 링크 programmers.co.kr/learn/courses/30/lessons/72416 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr 풀이 아이디어 우선 트리dp의 기본적인 풀이 방법을 알고 있다고 가정하고 작성한다. 해당 유형을 안풀어 봤을 때 hqjang.tistory.com/104?category=913845 를 참고할 것. 풀이의 핵심은 한 그룹에서 '최소 한명' 이 워크숍에 참석해야 한다는 것이다. 따라서 케이스는 두가지로 나뉜다. 1. 그룹장이 워크숍에 참석하는 경우 -dp[n.. 백준 11972 contaminated milk - usaco 브론즈 완전탐색 python 풀이 문제 링크 www.acmicpc.net/problem/11972 11972번: Contaminated Milk Farmer John, known far and wide for the quality of the milk produced on his farm, is hosting a milk-tasting party for \(N\) of his best friends (\(1 \leq N \leq 50\)). Unfortunately, of the \(M\) types of milk featured at the party (\(1 \leq M \leq 50\)), www.acmicpc.net 풀이 아이디어 문제의 간단한 해석을 하자면 오염된 우유는 단 1종류이고, 이 우유를 마신 사람은 파티 도중에 식중독.. 백준 12003 Diamond collector(silver) : 구간 2개를 구해야 하는 슬라이딩 윈도우 문제 문제 링크 www.acmicpc.net/problem/12003 12003번: Diamond Collector (Silver) The first line of the input file contains \(N\) and \(K\) (\(0 \leq K \leq 1,000,000,000\)). The next \(N\) lines each contain an integer giving the size of one of the diamonds. All sizes will be positive and will not exceed \(1,000,000,000\). www.acmicpc.net 풀이 아이디어 문제 해석을 간단히 하자면, 케이스 안에 다이아몬드를 넣는데 케이스 안에 들어간 다이아몬드들 끼리는 크기 .. 백준 2213 트리의 독립집합 - 어떤놈인지까지 찾아야 하는 트리dp c++ 문제 링크 www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 풀이 아이디어 트리 dp 문제를 단계로 나눠보자면 1단계는 사회망 서비스 hqjang.tistory.com/104?category=913845 문제를 들 수 있다. 단순히 그 트리 내에서의 요구하는 값의 최댓값 혹은 최솟값을 찾아내면 되는 문제. 이 문제는 2단계 정도에 해당한다. 최댓값/최솟값을 찾고, 그 값을 이루는 노드들을 구해야 한다. 당연히 dfs를 이용한 트.. 백준 1158 요세푸스 문제 : 큐,벡터로 각각 푸는 2가지 방법 문제 링크 www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 아이디어 규칙성을 찾아 벡터를 이용해 푸는 방법과 큐를 이용해 직접 k-1번씩 앞에 숫자를 빼서 뒤에넣은 후 k번째 숫자를 출력하는 방법이 있다. 어느것으로 풀어도 상관없음. 코드 방법 1. 큐를 이용해 푸는 법 #include using namespace std; queue q; int n,k,temp; int main(void){ cin >> n >> k; for(int i=1; i 백준 2150 strongly connected component 링크 www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 풀이 아이디어 SCC 관련 문제를 처음 풀어보는데 여러 블로그들 글을 참고했다. 자손 9319님 포스팅 jason9319.tistory.com/98 이 가장 깔끔하게 알고리즘을 설명해주신 글 같다. 코사라주 알고리즘을 이용해 문제를 풀었고, 코사라주 알고리즘을 간단히 설명하자면 스택과 역방향 그래프를 만들어 dfs를 2번 탐색함으로써.. 이전 1 2 3 4 ··· 10 다음
