본문 바로가기

알고리즘 문제풀이

(16)

[프로그래머스 Lv.2] 영어 끝말잇기 풀이 날짜 : 2025.05.08문제 유형 : Summer/Winter Coding(~2018)문제 제목 : 영어 끝말잇기문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12981Intuition끝말잇기 게임에서 규칙을 어긴 첫 번째 사람의 번호와 차례를 반환해야 한다. 규칙 위반은 아래와 같다.중복된 단어를 사용한 경우이전 차례에서 말한 단어의 마지막 글자와 현재 말한 단어의 첫글자가 다른 경우이전의 사용한 단어를 어딘가에 저장하고, 빠르게 탐색해야 한다.중복 단어를 저장하기 전에 함수가 끝날 것이므로 배열보다 탐색이 빠른 Set이 적절할 것이다.규칙을 위반한 첫 번째 사람의 번호와 차례를 계산해야 한다.현재 단어의 순서를 0부터 시..

[프로그래머스 Lv.2] 구명보트 풀이 날짜 : 2025.05.07문제 유형 : 탐욕법문제 제목 : 구명보트문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42885Intuition각 사람의 몸무게(people)와 구명보트의 무게 제한(limit)이 주어질 때 필요한 최소한의 구명보트 개수를 구해야 한다.1개의 보트에는 최대 2명까지만 태울 수 있다는 조건이 있다.2명을 태운 보드가 많을수록 필요한 보트 개수는 줄어든다.가장 무거운 사람을 가능한 한 가볍고 조건을 만족하는 사람과 짝짓는 것이 최적이다. ⇒ 그리디 방식무거운 사람은 짝지을 수 있는 대상이 적고 혼자 탈 가능성이 높다. 즉, 무게 제한을 넘어가면 무거운 사람이 혼자 타야 한다.배열을 정렬 후 양끝에서 최댓..

[프로그래머스 Lv.1] 푸드 파이트 대회 풀이 날짜 : 2025.05.01문제 유형 : 연습문제문제 제목 : 푸드 파이트 대회문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/134240Intuition음식의 개수를 좌우 대칭으로 하여 가운데 '0'을 두고 음식 배치를 완성해야 하는 문제이다.주어진 배열(food)의 인덱스가 음식의 번호, 값은 음식의 개수를 의미한다.음식의 개수가 2보다 작으면 두 선수가 나눠먹을 수 없으므로 제외해야 한다.문자열 조작 문제라고 볼 수 있다.Approach0을 기준으로 왼쪽에 배치할 문자열을 누적할 변수(left)를 선언한다.food를 순회하면서 left를 만든다.첫번째 요소는 항상 1이므로 제외하고, 음식의 개수가 2보다 작으면 넘어간다.나눠..

[프로그래머스 Lv.2] 점프와 순간 이동 풀이 날짜 : 2025.04.30문제 유형 : Summer/Winter Coding(~2018)문제 제목 : 점프와 순간 이동문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12980Intuition주어진 n만큼 이동하는 데 필요한 최소한의 점프 횟수를 구하는 문제이다.순간이동은 현재까지의 이동거리 * 2 의 위치로 이동하고 건전지를 사용하지 않는다.점프는 이동하는만큼의 건전지를 사용한다.그리디 알고리즘 : 항상 선택 가능한 최선의 방법을 선택한다.순간이동을 최대한 많이 쓰고, 순간이동을 할 수 없을 때만 점프를 해야 한다.6의 경우, [ 점프(0 + 1 = 1) → 순간이동(1 * 2 = 2) → 점프(2 + 1 = 3) → 순간이동..

[프로그래머스 Lv.2] 귤 고르기 풀이 날짜 : 2025.04.29문제 유형 : 연습문제문제 제목 : 귤 고르기문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/138476Intuition귤을 k개 담을 때 귤의 종류의 수의 최솟값을 구하는 문제이다.귤의 종류별로 개수를 내림차순으로 정렬하여 개수가 큰 귤부터 담아야 하는 전체 귤 수(k)에서 제외시켜야 한다.매 순간 최선(최대 개수 귤)을 선택해서 목표(k개)를 가장 빨리 달성하는 그리디 알고리즘 유형이라고 볼 수 있겠다.Approachkey는 귤의 사이즈, value는 해당 사이즈 귤의 개수를 담는 객체(sizes)를 선언한다.tangerine을 순회하면서 사이즈 별 개수를 저장한다.sizes의 value만 모아서 내..

[프로그래머스 Lv.1] 숫자 문자열과 영단어 풀이 날짜 : 2025.04.28문제 유형 : 2021 카카오 채용연계형 인턴십문제 제목 : 숫자 문자열과 영단어문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/81301Intuition문자열 s 안에 영단어로 표현된 숫자를 숫자로 변환하여 반환하는 문제이다.영어와 숫자를 매핑하여 s를 순회하며 정답을 도출한다.Approach정답을 저장할 변수 answer를 선언하고, 객체(numbers)를 사용하여 영단어와 숫자를 매핑한다.s를 순회하는 for 루프 안에서숫자가 아니라 문자라면 변수 text에 누적한다.숫자라면 answer에 그대로 누적한다.누적된 text가 numbers에 지정된 단어라면 이에 해당하는 숫자 문자열을 answer에 ..

[프로그래머스 Lv.1] 최소직사각형 풀이 날짜 : 2025.04.25문제 유형 : 완전탐색문제 제목 : 최소직사각형문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/86491Intuition명함의 가로,세로 크기가 담긴 배열이 주어질 때, 모든 명함을 담을 수 있는 지갑의 크기를 구해야 한다.각 명함은 회전이 가능하다. (가로, 세로를 바꿀 수 있다.)각 명함마다 긴 쪽은 가로에, 짧은 쪽은 세로에 둔다고 생각해보면, 긴 쪽 중에 최댓값과 짧은 쪽 중에 최댓값을 구하면 모든 명함을 다 넣을 수 있다.문제 유형은 완전탐색(Brute force)라고 되어 있지만, 명함을 회전한 모든 조합을 시도하지 않고 그리디 알고리즘으로 푸는 게 더 효율적일 것 같다.Approach명함 크..

[프로그래머스 Lv.1] 예산 풀이 날짜 : 2025.04.25문제 유형 : 연습 문제문제 제목 : 예산문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12982Intuition정해진 예산에서 부서에서 신청한 금액을 지원해줄 때, 최대 몇 개 부서에 지원해줄 수 있는지 구해야 한다.신청한 금액이 작은 부서들부터 지원해야 최대한 많은 부서에 지원할 수 있다.현재 상황에서 가장 최적인 선택을 반복해서 전체 최적해를 구하는 그리디 알고리즘 문제로도 볼 수 있겠다.Approach부서의 신청 금액이 담긴 배열 d를 오름차순으로 정렬한다.오름차순으로 정렬된 d를 순회하며, 부서의 신청 금액(amount)이 남은 예산(budget) 보다 작으면 지원한 부서 수(count)를 1..

이전 1 2 다음

티스토리툴바