프로그래밍
-
[프로그래머스] 짝지어 제거하기프로그래밍/코딩 테스트 2024. 9. 26. 20:58
문제.알파벳 소문자로 이루어진 문자열을 가지고 시작합니다.먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다. 예를 들어, 문자열 S = baabaa 라면b aa baa → bb aa → aa →의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.제한 사항.* 문자열의 길이 : 1,000,000이하의 자연수* 문자열은 모두 소문자로 이루어져 있습니다. 나의 접근.처음에는 반복..
-
[알고리즘] 탐욕법 알고리즘(Greedy Algorithm)프로그래밍/알고리즘 2024. 9. 17. 22:01
탐욕법 알고리즘(Greedy Algorithm)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법으로 최적화 문제를 해결하기 위해 사용하는 알고리즘 방법 중 하나이다. 예시) 노드의 합이 가장 높은 방법을 생각해보자. 이 처럼 탐욕법 알고리즘은 매 단계에서 현재 상황에서 가장 최선의 선택을 하는 방식으로 최종 해답을 찾지만 항상 최적의 값을 보장하는것은 아니다. 이러한 탐욕법 알고리즘은 모든 상황에서 보다는 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. - 탐욕 선택 속성(greedy choice property) 이전 단..
-
[프로그래머스] 구명보트(feat. 탐욕법 알고리즘)프로그래밍/코딩 테스트 2024. 9. 16. 16:16
문제. 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.제한 사..
-
[프로그래머스] 점프와 순간 이동프로그래밍/코딩 테스트 2024. 9. 16. 09:39
문제. OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는..
-
[알고리즘] 시간 복잡도(Time complexity)프로그래밍/알고리즘 2024. 9. 9. 00:19
시간복잡도(Time complexity)는 문제를 해결하는데 걸리는 수행 시간과 입력 데이터의 함수 관계를 분석하는 개념으로, 입력 데이터의 크기가 커질 때, 알고리즘이 얼마나 효율적인지 평가할 수 있다. 시간 복잡도는 주로 빅오 표기법(Big-O Notation)으로 표현되며, 알고리즘의 수행 시간은 동일 크기의 다양한 입력 데이터에 의해 달라질 수 있기 때문에, 가장 많이 쓰이는 최악의 시간 복잡도의 알고리즘 시간을 T(n)이라고 했을 때, 이것은 크기 n의 모든 입력 데이터에 대해 걸리는 최대의 시간으로 정의할 수 있다. 그 수치가 작을 수록 효율적인 알고리즘을 의미한다. 시간 복잡도에는 빅오(Big-O) 외에도 빅오메가(Big-Omega), 빅세타(Big-Theta)라는 개념도 존재한다.빅오는..
-
[프로그래머스] 피보나치 수프로그래밍/코딩 테스트 2024. 9. 7. 13:58
문제. 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어, F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5와 같이 이어집니다.2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.제한 사항. n은 2 이상 100,000 이하인 자연수입니다. 나의 접근.주어진 자연수 n+1 길이의 배열(pi)을 선언하여, pi[i-1] + pi[i-2] 한 값이 pi..
-
[프로그래머스] 숫자의 표현프로그래밍/코딩 테스트 2024. 9. 6. 21:20
문제. Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다. 1 + 2 + 3 + 4 + 5 = 154 + 5 + 6 = 157 + 8 = 1515 = 15 자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요. 제한사항. n은 10,000 이하의 자연수 입니다. 나의 접근.1부터 주어진 자연수 n까지 반복하여, i부터 자연수 n까지 순차적으로 합하여 그 합이 n과 같으면 answer에 +1해준다. class Solution { public int solution(..
-
[프로그래머스] JadenCase 문자열 만들기프로그래밍/코딩 테스트 2024. 9. 5. 22:54
문제.JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고)문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.입출력 예) 3people unFollowed me => 3people Unfollowed Me 제한 사항.* s는 길이 1 이상 200 이하인 문자열입니다.* s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.* 숫자는 단어의 첫 문자로만 나옵니다.* 숫자로만 이루어진 단어는 없습니다.* 공백문자가 연속해서 나올 수 있습니다. 나의 접근.문자열을 한글자씩 배열에 담고 배열을 반..