본문 바로가기

알고리즘/백준 알고리즘 강의

 (40)
백준 알고리즘 중급 - 그리디 알고리즘 (도전) 3문제 뿐이었지만, 도전 챕터답게 무게감 있는 문제들이었다. 내 힘으로 풀어내지는 못 했지만.. 문제 풀이 과정을 익히는 것만으로도 충분히 가치 있었다. 추후에 써먹을 곳이 많을 것 같으니 잘 정리해두자. 정리 시작! - * NMK (high) : N까지의 자연수를 LIS가 M, LDS가 K가 되도록 나열하는 문제다. 1201번: NMK 1부터 N까지의 수를 한 번씩 이용해서 최대 부분 증가 수열의 길이가 M이고, 최대 부분 감소 수열의 길이가 K인 수열을 출력한다. www.acmicpc.net - 우선 N값의 범위를 생각해줘야 한다. 최솟값은 어떻게 될까? 증가하는 숫자가 최소 M개, 감소하는 숫자가 최소 K개 있어야 한다. 증가와 감소의 분기점 또한 존재할 것이므로 중복을 하나 빼준다. 따라서 N은 ..
백준 알고리즘 중급 - 그리디 알고리즘 (연습) 뭐랄까.. 문제 자체는 그렇게 복잡하지 않았는데.. 지나치게 많은 시간이 소요된다. 어찌된 노릇일까. 속도를 좀 더 빠르게 할 수는 없을까..? ㅠㅠ뭐 실력이 쌓이면 속도도 자연스럽게 빨라지겠지.. 의식적으로도 시간을 단축하기 위해 슬슬 노력하자. 정리 시작! - * 잃어버린 괄호 (mid) : 식에 괄호를 적절하게 쳐서 최소값을 구하는 문제다. 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net - 마이너스가 나오는 순간부터 그 뒤는 모두 마이너스가 된다는 것만 알면 바로 풀 수 있다. 근데 그게 생각 안..
백준 알고리즘 중급 - 그리디 알고리즘 - 2 이번 챕터에서는 얻을 게 엄청 많았다. 특히 큰 수가 들어갈 때 항상 쩔쩔 맸는데, 전환점이 될 수도 있을 정도로 많은 것을 얻은 것 같다. 체크 해뒀다가 잘 써먹어보자. 이제 효율적인 공부 흐름을 어느정도 터득한 것 같다. 이 흐름대로 꾸준히 잘 해보자. 정리 시작! - * 보석 도둑 (high) : 보석 도둑이 훔칠 수 있는 최댓값을 구하는 문제다. 어려웠다. 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net - 보석의 가격을 기준으로 한 풀이와 무게를 기준으로 한 풀이, 2가지의 해결법이 있다. 보..
백준 알고리즘 중급 - 그리디 알고리즘 - 1 이미 풀어본 문제가 많아서 빠르게 클리어 했다. 그땐 쩔쩔 맸던 문제들이 지금은 수월하게 풀린다는 것에 놀라기도 했다. 패턴을 찾아도 알고리즘을 짜는 게 은근 까다로워서 고생한 문제도 있었다. 정리 해보자! - * 그리디 알고리즘 : 결정해야 하는 그 순간에 가장 좋다고 생각하는 것을 찾아가며 답을 찾아가는 알고리즘이다. 뒤이에 올 것은 생각하지 않고 그때 그때 가장 좋은 선택을 한다고 욕심쟁이라는 이름이 붙었다. 바로 예제로 들어가보자. * 동전 0 (low) : 가장 간단한 그리디 문제인 거스름돈 문제다. 필요한 동전 개수의 최솟값을 구하면 된다. 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 ..
백준 알고리즘 중급 - BFS (연습) - 2 정말 늪같은 챕터였다.. 문제도 많고.. 어려웠어.. 하지만 그만큼 많은 걸 배웠다. 근데 제발 시간을 재면서 풀자. 한번 매달리면 거의 하루종일 그 문제만 쳐다보는데.. 끈기는 좋지만 효율이 안 나온다. 똑똑하게 공부하자. 정리 시작! - * 벽 부수고 이동하기 (mid) : 벽을 하나까지 부술 수 있는 조건에서 최단 경로를 구하는 문제다. 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net - 벽을 부쉈는지, 안 부쉈는지까지 생각해서 기록해줘야 한다는 것이 포인트였다. #inclu..
백준 알고리즘 중급 - BFS (연습) - 1 점점 업로드 주기가 길어진다.. 좀 게을러진 것 같아 반성이 된다. 좀 더 마음을 다잡고 다시 해보자. 중요한 건 속도가 아니고 방향이니, 너무 성급해하지는 말고. 어쩌라는겨 아무튼 정리 시작! - * 뱀과 사다리 게임 (mid) : 변칙 조건이 주어진 보드판에서 도착점에 도달하는 최소 주사위 굴리기 횟수를 구하는 문제. 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net - 뱀이 있는 칸에 가면 뒤로 가고, 사다리가 있는 칸에 가면 앞으로 간다. 100번 칸에 가기 ..
백준 알고리즘 중급 - 브루트 포스 : 비트마스크 (연습) 근 일주일만의 기록이다. 면접도 준비하고, 바람 좀 쐬느라 늑장을 부렸다. 다시 차근차근, 해오던 거 하자. 정리 시작! - * 부분수열의 합 (mid) : 앞에서 재귀로 풀었던 부분수열의 합 문제를 비트마스크를 이용해서 풀어보자. 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 � www.acmicpc.net #include #include using namespace std; bool check[2000001]; int main() { int n; cin >> n; v..
백준 알고리즘 중급 - 브루트 포스 : 재귀 (연습) - 2 지금까지 강의 중에 제일 어려웠다. 백트래킹 부분이 많이 약한 것 같다. 보통 앞의 문제를 풀어보면 요령이 생겨 뒤의 문제를 곧잘 푸는데 이건 정말 손도 못 댔던 것 같다. 그만큼 더 잘 이해하고 넘어가야 하는 이유다.. 하나하나 곱씹으면서 정리해보자. - * N -Queen (high) : 크기가 n*n인 체스판 위에 n개의 queen을 놓는 경우의 수를 구하는 문제다. 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net - queen은 상하, 좌우, 대각선까지 다 갈 수 있다. 따라서 queen의 위치를 잡았을 때, 상하좌우..

티스토리툴바