BOJ (34) 썸네일형 리스트형 BOJ 1911 흙길 보수하기 BOJ 백준 1911 흙길 보수하기 C++ JAVA https://www.acmicpc.net/problem/1911 알고리즘을 꾸준히 풀지 않으면 쉽게 풀릴 것 같은 문제조차 어렵게 느껴진다. 꾸준히 풀자! 문제를 보고 처음 든 생각은 딱히 다른 알고리즘 개념이 있다기보다는 평범한 그리디 문제 같았다. 비슷한 유형으로 [ 1913 회의실 배정 https://www.acmicpc.net/problem/1931 ] 이 생각났음 문제를 풀고 난 후 분류를 봤는데 "스위핑" 알고리즘이라는 것이었다. ( 라이님 블로그 참고.. blog.naver.com/kks227/220907708368 ) sweeping에서 유추 가능하듯 전체를 한 번 스캔하면서 작업하는 알고리즘! 생각의 흐름 1) (회의실 배정과 같이) .. BOJ 1525 퍼즐 BOJ 백준 1525 C++ 퍼즐 https://www.acmicpc.net/problem/1525 처음에 이 문제를 봤을 때 접근 시도 첫 번째, 재귀(DFS)가 생각났다. 재귀를 이용하려 해결하려 했지만 재귀 깊이가 어느 정도 가능할지? & 방문 확인을 어떻게 할 것인지? 에 관해 의문이 들었다. 그래도 한번 구현해봤다. 결과는 틀렸습니다. 간단한 경우의 입력에서는 원하는 출력이 나왔지만 아마 예외 케이스에 모두 걸렸을 거로 생각한다. (31을 출력해야 하는 예제에서 -1을 출력한다.) 접근 시도 두 번째, 우선 맵으로 주어진다. 그리고 '최소 이동 횟수'를 원한다. = BFS를 이용할 수 있지 않을까? 라는 생각이 강하게 든다. 그런데 지금까지 접해왔던 BFS와는 약간 다르다. 물론 방문했는지 확인.. BOJ 1062 가르침 BOJ 백준 1062 C++ 가르침 https://www.acmicpc.net/problem/1062 풀이 방법에 대해 아주 많이 헤맸던 문제이다. 기본적으로 조합을 한다고는 생각했고, 처음에 생각했던 풀이는 N개 단어에 대해 '1개를 선택하는 조합'부터 'N개 선택하기까지의 조합'을 만든다. -> 선택의 갯수가 1부터 N까지로 아주 다양한 조합이 나옴. 문제의 예제로 설명하자면 N=3이므로 [ 1 / 2 / 3 / 1,2 / 1,3 / 2,3 / 1,2,3 ] 7개의 경우가 발생하고, 3보다 조금 더 큰 N=10을 생각하면 훨씬 많은 경우가 발생한다. 각 조합에 대해 사용된 알파벳의 갯수를 세고 K개 이하일 때 ans값이 최대인지 확인하여 갱신한다. .. 라고 풀이하려했으나, N=50까지 가능하므로 T.. BOJ 16954 움직이는 미로 탈출 BOJ 백준 16954 C++ 움직이는 미로탈출 https://www.acmicpc.net/problem/16954 1) BFS - 완전히 전형적으로 나오는 BFS에서 조금 더 생각해야 함. 이와 유사 문제가 많음. 당장 생각나는 문제는 삼성 기출의 구슬 문제. 2) 몇 달 전에는 많이 헤맸던 유형인데 이제는 예전보다 풀만하다. 정답 제출하고 다른 풀이도 몇 개 봤는데 세부적인 구현이 갈리는 것 같다. 나는 단계별로 맵을 움직이기 위해 반복문(while)을 두 개 사용해서 구현했다. 3) 처음에 문제에서 [ 욱제 이동->벽 이동 ] 이라고 해서 욱제의 위치를 움직이고 벽을 이동하는 쪽으로 구현할까? 했는데, 그보다는 벽을 '먼저' 움직여놓고(line 40), 벽과 겹치지 않는 욱제의 위치(line 68).. BOJ 16562 친구비 BOJ 백준 16562 C++ 친구비 https://www.acmicpc.net/problem/16562 1) union-find 약간 변형된 문제 2) 기본 union-find를 풀 듯이, 처음에 모든 node의 부모를 자기 자신으로 설정했다. 그리고 M번 동안 친구 관계를 입력받으면서, 친구(부모가 같은 하나의 집합)가 아니라면 unite()함수를 실행한다. 는 unite()의 line 30-31에서 부모를 같게 만들 때, 가장 적은 비용으로 친구를 만들기 위해서 비용이 큰 node의 부모를, 작은 node의 부모로 바꿔준다. 3) 친구 관계를 정리 한 후, 모든 학생과 친구가 되었는지 확인 하기 위해 check[]를 이용하여 확인 했다. 4) 개인적으로 union-find 문제 풀 때마다 드는 생각.. BOJ 6497 전력난 BOJ 백준 6497 C++ 전력난 https://www.acmicpc.net/problem/6497 1) MST(최소 신장 트리)의 Kruskal(union find 이용) 문제 2) 벡터에 주어진 (from, to, dist)를 삽입 후 dist의 오름차순으로 정렬한 후, 차례대로 꺼내며 하나의 집합으로 만든다. 3) 집보다 길의 수가 (훨씬) 많이 주어질 수 있다. 연결된 길(cnt)이 [집의 수-1]개가 되었을 때 종료한다. -> 이 때 종료되면, 하나의 집합을 이룰 때 최소 비용을 구할 수 있다. 4) 문제에서는 절약할 수 있는 비용을 원하므로, 전체 비용에서 최소 비용을 빼면 답을 구할 수 있다. 5) testcase도 여러 개 주어질 수 있다. 정보를 저장한 벡터를 비우거나, 새 테스트케이스.. BOJ 1700 멀티탭 스케줄링 BOJ 백준 1700 C++ 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1) 처음에는 N개를 채울 때까지 order[]를 차례대로 진행한다 2) N개를 모두 꽂으면, 꽂혀 있는 것 중 제거할 것을 선택해야 한다. case 0. 꽂혀 있는 것을 확인하여, 앞으로 사용 안 하는 것 있으면 제거 case 1. 꽂혀 있는 것들을 확인했는데, 모두 사용될 예정이면 (case0에서 조건 걸리지 않으면), 가장 나중에 사용될 것을 제거 [현재 order의 다음 순서(i+1) ~ 순서의 끝(K)]을 for 돌면서 아래 조건을 확인한다. if(res[order[j]][0]>0 && res[order[j]][1]==1 && !check[order[j]]) -> (앞으로 사용될 것 &.. BOJ 2824 최대공약수 BOJ 백준 2824 C++ 최대공약수 https://www.acmicpc.net/problem/2824 아. 엄청 고생했던 문제.. 잊을 수 없다. 1) 약수 구하기의 응용문제, 주어지는 수가 매우 커서 오버플로우에 주의해야 한다. 2) 처음에는 배열 인덱스를 이용해서 약수의 개수를 카운트하려고 했는데, 약수 input의 값이 최대 999,999,999이기 때문에 배열 메모리 초과를 예상하고, map 자료구조를 이용해서 -> 를 만들었다. 3) 약수를 구할 때, 두 가지 방법을 이용했다 3-1) 약수의 특성을 이용해서 j*j까지 확인하기 (j*j> N; for(int i=0; i> x; for(int j=2; j*j> M; for(int i=0; i> x; for(int j=2; j*jfirst; if.. 이전 1 2 3 4 5 다음
