DevLog: 기록하는 생활

예제 4-1 상하좌우 문제 여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N) 에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 꼐획이 적힌 계획서가 놓여 있다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. * L : 왼쪽으로 한 칸 이동 * R : 오른쪽으로 한 칸 이동 * U : 위로 한 칸 이동 * D : 아래쪽으로 한 칸 이동 이 때 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시..

앞 chapter 3 문제 와 풀이는 여기에 있습니다 https://yj-go-my-way.tistory.com/2 그리디 알고리즘 (이코테 chapter 3) 그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고 yj-go-my-way.tistory.com 01 모험가길드 문제) 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. N명의 모험가에 대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하시오. 내 풀이) 1 2 3 4 5 6 7..

그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', ' 가장 작은 순서대로' 와 같이 기준을 알게 모르게 제시한다. 이 기준과 함께 정렬 알고리즘과, 큐를 사용해 문제를 해결할 수 있다. 예제 3-1 거스름돈 문제) 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. 풀이) n = 1260..