알고리즘, 문제해결103 [백준 1944번] 복제 로봇 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 처음 문제를 읽어보고 나면 어떤 방법으로 접근해야 할지, 조금 막막하게 느껴질 수 있는 문제입니다 (제가 그랬음). 시작점에서 특정 도착점까지의 최단 거리를 구하는 방법에는 여러 가지가 있지만, 이렇게 격자 형식으로 판이 주어지는 경우에는 bfs가 편리합니다. 또, 이런 경우도 있을 수 있습니다. 시작점 S에서 도착점 A, B, C가 .. 2021. 9. 1. [백준 14728번] 벼락치기 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 이전에 풀었던 knapsack 문제와 완전히 동일합니다. (링크) 매우 자세한 설명은 위의 링크를 따라가면 있습니다. 오랜만에 다시 풀어본 김에 내용정리를 간단하게 하고 가자면... 이 문제는 모든 경우의 수를 고려하기에는 N 2021. 8. 31. C++의 auto에 대해 C++에 익숙하다고는 하지만, 맨날 알고리즘 문제풀이만 하던 저에게 최근에 새롭게 알게 된 키워드가 있습니다. auto 키워드인데, C++11 이후에 추가되었다고 합니다. 제가 가장 흔하게 본 상황은 아래와 같은 경우입니다. vector numbers; for (auto next : numbers) { cout 2021. 8. 31. [백준 2900번] 프로그램 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/2900 2900번: 프로그램 창영이가 에러를 찾기 위해서 디버깅을 하고 있다. 이 프로그램은 크기가 N이고 0으로 채워져있는 배열을 a를 만들고, 아래 something 함수를 호출한다. void something(int jump) { int i = 0; while (i < N) { a[i] www.acmicpc.net 위 문제를 접하고 정말 단순하게 구현하면, 구현은 됩니다. something 함수를 K번만큼 호출하고, 부분합을 구하기 위해 Q번만큼 합을 구합니다. something 함수를 보시면 loop를 N번 반복하게 되어 있고, 부분합을 구할 때 L = 0, R = N이라면 배열에 N번 접근하게 됩니다. K.. 2021. 8. 30. [백준 2696번] 중간값 구하기 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 입력받은 n개의 정수 (n은 홀수) 중, 차례로 읽으며 홀수번째 수를 읽을 때마다 그 수까지의 중간값을 출력하는 문제입니다. 가장 먼저 떠오른 생각은... 매 홀수번째 수를 읽을 때마다, 지금까지 읽은 수를 정렬한 후 중간값을 읽자... 인데 그러면 원소의 개수가 n개라면 총 (n/2)번 정렬을 해야 합니다. Quick sort가 평균 .. 2021. 8. 29. [백준 5719번] 거의 최단 경로 난이도: 플래티넘 5 문제 링크: www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 흔한 최단 경로 문제에 조건이 하나 추가된 문제입니다. 시작점과 끝점이 주어져 있고, 각 노드 간 단방향 거리가 주어졌을 때, 시작점으로부터 끝점까지의 "거의 최단 경로" 를 구하면 됩니다. 여기서 "거의 최단 경로" 란, 최단 경로에 포함되어 있지 않은 경로로만 이루어진 경로를 뜻합니다. 제가 고민한 문제 접근 방법은 이렇습니다. 1. Dijks.. 2021. 4. 29. 이전 1 ··· 6 7 8 9 10 11 12 ··· 18 다음
