BOJ (25) 썸네일형 리스트형 [BOJ] 1922 네트워크 연결 문제: https://www.acmicpc.net/problem/1922 MST(최소 비용 신장 트리, Minimum Spanning Tree)를 찾는 문제로 정말로 naive하게 MST를 찾는 알고리즘을 구현해주면 된다. 나는 이 문제를 풀기 위해서 크루스칼 알고리즘을 사용했다. 지금 생각해 보니 좀 많이 이상하지만 정보올림피아드를 이제까지 준비하면서 단 한번도 MST를 사용하는 문제를 풀거나 코딩해 본적이 없었다. Union-Find (코드에서 DisJointSet)을 좀 쉽게 구현할 수 있게 되니까 비로소 알고리즘을 이해할 수 있었다. 난이도는 1.5/5 정도인 것 같고 코드는 아래와 같다.1234567891011121314151617181920212223242526272829303132333435.. [BOJ] 1931 회의실배정 문제: https://www.acmicpc.net/problem/1931 그리디 알고리즘의 대표주자 회의실배정이다. 사실 다 아는 문제니까 그냥 넘어가도 되겠지 이러면서 이제까지 한번도 구현을 안해봤는데, 채점해보니까 처음에 틀렸다 ㅡㅡ 풀이 방법은 가장 끝나는 시간이 빠른 회의, 만약 같다면 시작을 더 빨리 하는 회의부터 그리디하게 선택하는 것이다. 끝나는 시간이 빠른 건 끝나는 시간이 빠를수록 더 많이 회의를 진행할 수 있으니까 그렇다고 쳐도 대체 왜 시작을 더 빨리 하는 회의부터 선택하는지는 잘 몰랐었는데 틀리고 나서 생각해 보니까 (7,8), (8,8) 등의 회의가 존재하면 두개를 다 먹을 수 있더라. 구현은 간단하게 STL sort를 이용해서 정렬했다. 아직도 sort를 사용자 정의 함수로 정렬.. [BOJ] 1005 ACM Craft 문제: https://www.acmicpc.net/problem/1005 위상 정렬의 대표격인 건설 순서 문제이다. 그런데 사실 난이도가 아주 없는 문제는 아니어서 이게 왜 1005번에 있나 조금 의심이 들기는 하는 부분이다. 사실 습격자 초라기에 비할 바는 못되지만... 하여튼 내 풀이를 설명하자면, DFS를 이용해 그래프를 순회하면서 함수가 종료할 때마다 저장하면 위상 정렬의 역순이 된다는 점을 이용해서 DP를 돌리는 방법으로 문제를 풀었다. 이를 위해서 순방향 간선과 역방향 간선의 인접 리스트를 별도로 만들었고, 역방향 간선의 인접 리스트의 크기가 0인 것들을 모두 DFS 돌리고 reverse해서 위상 정렬을 찾은 다음 그걸 역방향 간선 인접 리스트를 통해 바텀업 DP로 돌려서 결과값을 찾아냈다. .. [BOJ] 2439 탑 문제: https://www.acmicpc.net/problem/2493 2009년 초등부 지역본선 4번, 고등부 지역본선 2번 문제이다. 그만큼 난이도도 매우 쉬운 스택 문제기는 한데 처음 보면 스택 문제가 아니라고 생각할 수도 있을 거라 생각한다. 풀이는 다음과 같다. 이 문제를 푸는 가장 적절한 알고리즘은, 왼쪽부터 탑의 높이를 차례대로 보면서 스택의 맨 위와 비교해서, 스택의 수가 더 클 때까지 pop하고 그 때 숫자를 출력하는 것이다. 굉장히 단순하기 짝이 없지만 제대로 동작하는 알고리즘이다. 대략적으로라도 증명을 해보자. 1. 이 알고리즘을 썼을 때 원래 부딪혀야 하는 곳보다 왼쪽에서 부딪히는 경우는 없다.원래 부딪혀야 하는 것보다 왼쪽에서 부딪혔다고 가정해 보자. 스택에서 pop을 할 때 원.. [BOJ] 1011 Fly me to the Alpha Centauri 문제: https://www.acmicpc.net/problem/1011 그냥 노가다로 규칙 찾는게 증명하는 것보다 빠르다.결국은 수열 길이가 있을때 하나씩 증가/감소/유지되는 수열의 길이가 n이 되는 경우가 있느냐... 찾는 문제인데예를 들어서 수열 길이가 7이라고 하면 1 2 3 4 3 2 1 이런 식으로 이동하는 것이 최대라는 것은 자명하다.그런데 만약에 이렇게 7번의 이동으로 16의 거리를 이동했으면 그 이하의 거리는 모두 이동할 수 있을까? 당연하다.항상 수열에서 가장 큰 원소를 하나 줄이면 그 원소는 절대로 다른 원소와 2 이상 차이가 나지 않게 만들수 있는 것을 너무 간단히 증명할 수 있다.수열 $a_1, a_2, a_3, ... , a_n$ 이 있다고 하자. 만약 $a_k$가 최대 원소라고.. [BOJ] 1918 후위표기식 문제: https://www.acmicpc.net/problem/1918 후위표기식은 스택의 대표주자라 할 만큼 중요한 내용이다.알고리즘은 간단하다. 1. 열린 괄호 -> push2. 닫힌 괄호 -> 열린 괄호가 나올때까지 pop3. 피연산자 -> 그대로 출력4. 연산자 -> 자기보다 우선순위가 낮거나, 열린 괄호가 나오거나, 스택이 빌 때까지 pop 후 push 코드는 이를 그대로 구현했다.4번에 열린 괄호가 나오는 것을 별도로 처리해주지 않은데 주의. 난이도는 1.5/5 정도? 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include using .. [BOJ] 1874 스택 수열 문제: https://www.acmicpc.net/problem/1874 굉장히 간단해 보이는 문제와 굉장히 간단한 해법이다.그저 숫자를 스택에 차례대로 넣으면서 지금 빼야 하는 숫자가 top이면 pop해주면 된다.만약에 모든 알고리즘이 끝났는데도 stack이 비지 않았다면 NO. 코드를 좀 더 깔끔하게 짤 수 있을 것 같다. 고민 좀 해 봐야징아마 난이도는 1/5 정도 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include using namespace std; stack S;vector oper; int main(){ int i=1,j=1,n,a.. [BOJ] 3986 좋은 단어 문제: https://www.acmicpc.net/problem/3986 사실 괄호 문자열 처리하는 문제와 다를 것이 전혀 없습니다. 굳이 스택을 써야 하는지도 모르겠는 문제... 지만 어쨌던 간에 스택 태그가 달려있어서 풀어봤습니다. 코드에서 '_'를 먼저 추가해서 오버플로우를 방지한 영향으로 만족 조건이 S.empty()가 아닌 S.size()==1이 된 것에 주의합시다. 난이도는 1/5. 기초 중의 기초. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std; int solve(){ char str[100005]; stack S; S.push('_'); scanf(.. 이전 1 2 3 4 다음