그리디
-
[프로그래머스] 조이스틱알고리즘/프로그래머스 2021. 7. 28. 16:42
문제 링크 풀이 마냥 쉬운 문제는 아닌 것 같습니다. 조이스틱의 위아래 조작의 최소 횟수를 찾는 건 쉽습니다. A->Z 방향, Z->A 방향으로의 조작 중 더 작은 값을 취하면 됩니다. 문제는 좌우 조작입니다. 몇 번 직접 사례를 찾아가면서 규칙을 찾아야 합니다. ABABAAA의 경우를 보면 오른쪽으로 세 번만 움직이면 됩니다. 이것이 최소 횟수입니다. AABAAAAAB의 경우에는 먼저 왼쪽으로 한 번 갔다가 오른쪽으로 세 번 움직이는 게 최소 횟수입니다. ABAAAAABA의 경우는 일단 오른쪽으로 한 번 갔다가 왼쪽으로 세 번 가는 방법이 최소 횟수입니다. 이 세 가지의 경우 중 가장 작은 값을 구하면 되는 것입니다. 여기서 한 가지 공식을 만들 수 있습니다. 원점 기준 A가 아닌 위치를 찾고 나서, ..
-
[프로그래머스] 가장 큰 정사각형 찾기알고리즘/프로그래머스 2021. 7. 11. 15:51
문제 링크 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 풀이 가로의 길이가 1이거나 세로의 길이가 1인 경우에는, 최대 사각형의 크기가 1을 넘을 수 없으므로 해당 처리만 따로 해줍니다. 이 문제의 풀이법이 명확하게 동적 계획법인지 그리디인지는 잘 모르겠습니다. 현재의 가장 최선인 값을 구해가면서 푸는 것이기도 하고 기존에 구했던 해를 메모이제이션 통해 활용하기도 하기 때문입니다. 둘이 섞였나 봅니다. 이중 반복문을 돌려 board[i][j]를, 그 위치에서 최대 정사각형의 길이값을 넣어줍니다. 예를 들어보겠습니다. board[i][j]가 0이라면 계산하지 않습니다. 계산할 필요도 없고 계산하면 ..
-
[프로그래머스] 체육복알고리즘/프로그래머스 2020. 2. 11. 10:05
문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를..