문제 설명게임에서 캐릭터의 필살기인 '럭키 스트레이트'는 현재 캐릭터의 점수를 N이라고 할 때, 자릿수를 기준으로 점수 N을 반으로 나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 자릿수의 합을 더한 값이 동일한 상황일 때만 사용할 수 있습니다.현재 점수 N이 주어지면 럭키 스트레이트를 사용할 수 있는 상태인지 아닌지를 알려주는 프로그램을 작성하세요. 입력조건첫째 줄에 점수 N(10 N의 자릿수는 항상 짝수출력조건럭키 스트레이트를 사용할 수 있으면 "LUCKY", 사용할 수 없으면 "READY"입출력 예시 입력예시출력예시123402LUCKY7755READY    문제 풀이점수 N을 String으로 입력받아서 문자열의 길이를 반으로 나눈다.left는 왼쪽 부분의 자릿수의 합, right는 오른쪽 부분의..

구현(Implementation)코딩테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' 이다.풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 말한다. 구현 유형의 예시알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제  일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다. for (int i = 0; i  완전 탐색, 시뮬레이션 유형을 '구현' 유형으로 분류하는데, 이러한 유형의 문제에서 2차원 공간에서의 방향 벡터가 자주 사용된다.//동, 북, 서, 남int[] dx = {0, -1, 0, 1};int[] dy = {-1, 0,..

문제 설명다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다.다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.예를 들어 S = 0001100 일 때,1. 전체를 뒤집으면 11100112. 4번째 문자부터 5번째 문자까지 뒤집으면 111111이 되어서 두 번 만에 모두 같은 숫자로 뒤집을 수 있다.하지만 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 0000000이 되어서 한 번 만에 모두 같은 숫자로 만들 수 있다.문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하세요. 입력조건첫째 줄에 0과 1로만 이루어진 ..

문제 설명각 자리의 숫자(0 ~ 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하여 숫자 사이에 '×' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.단, +보다 ×를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정한다.만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.  입력조건첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S(1 출력조건첫째 줄에 만들어질 수 있는 가장 큰 수를출력입출력 예시입력예시출력예시02984576567210    문제 풀이어떤 두 수에 대한 연산을 수행할 때, 두 수 중 하나라도 '0' 또는 '1'일 경우에 ..

문제 설명한 마을에 모험가가 N명 있습니다.모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높을수록 위험 상황에서 대처 능력이 떨어집니다.모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최대값을 구하는 프로그램을 작성하세요.몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정 그룹에 넣을 필요는 없다. 입력조건첫째 줄에 모험가의 수 N(1 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분출력조건여행을 떠날 수 있는 그룹 수의 최대값을 ..

그리디 알고리즘이란?현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘즉, 매 순간 가장 좋아 보이는 것을 선택하며 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.정렬 알고리즘과 짝을 이뤄서 출제되는 경우가 많다. 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심해볼 수 있다. 하지만 그리디 알고리즘을 모든 상황에 적용할 수 있는 것은 아니다.현재 상황의 최적의 해가 전체 상황의 최적의 해를 보장하는 것은 아니기 때문이다.그렇기 때문에 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한 방법인지 검토해야 한다.  대표적인 그리디 알고리즘의 문제로 '거스름돈' 문제가 있다.예제 1) 거스름돈손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구한다..