본문 바로가기

Algorithm problems, coding test

(19)
[이코테][Chapter 12][문제] 8. 문자열 재정렬 [문제 정의] 알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출련한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다. 예를 들어 K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력합니다. [입력] 첫째 줄에 하나의 문자열 S가 주어집니다. (1
[이코테][Chapter 12][문제] 7. 럭키 스트레이트 [문제] 어떤 게임의 아웃복서 캐릭터에게는 럭키 스트레이트라는 기술이 존재한다. 이 기술은 매우 강력한 대신에 항상 사용할 수는 없으며, 현재 게임 내에서 점수가 특정 조건을 만족할 때만 사용할 수 있다. 특정 조건이란 현재 캐릭터의 점수를 N이라고 할 때 점수 N을 자릿수를 기준으로 반으로 나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 각 자릿수의 합을 더한 값이 동일한 상황을 의미한다. 예를 들어 현재 점수가 123,402라면 왼쪽 부분의 각 자릿수의 합은 1+2+3, 오른쪽 부분의 각 자릿수의 합은 4+0+2이므로 두 합이 6으로 동일하여 럭키 스트레이트를 사용할 수 있다. 현재 점수 N이 주어졌을 때, 럭키 스트레이트를 사용할 수 있는 상태인지 아닌지를 알려주는 프로그램을 작성하시오. 럭키 ..
[이코테][Chapter 4] Implementation 구현(Implementation)은 말 그대로 "주어진 설명대로 프로그램을 작성할 수 있냐"는 문제이다. 사실 모든 알고리즘 문제, 코딩 테스트 문제가 이렇다. 사실 딱히 덧붙일 설명은 없는데, 자주 나오는 유형 하나가 상당히 골치 아프다. 순열과 조합이다. 순열과 조합 실제로 문제를 풀 때, 가장 먼저 파이썬의 itertools 라이브러리를 사용하여 간단하게 구현해본다. 그러나 삼성전자 코딩테스트의 경우에는 사용이 불가능하고, 실제로 itertools로 문제를 풀다가 시간초과(...)가 뜰수도 있고, 변수가 상당히 많다. 만약 문제가 발생할 경우, 순열과 조합을 만드는 코드를 따로 적어서 사용한다. itertools를 이용한 순열, 조합 import itertools arr = [1,2,3] for i..
[이코테][Chapter 11][문제] 3. 문자열 뒤집기 [문제설명] 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만드려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어, S = 0001100일 때는 다음과 같다. 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 두 번 만에 모두 같은 숫자로 만들 수 있다. 하지만 처음부터 4번째, 5번째 문자열 00을 11로 뒤집으면 한 번만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어질 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력해라 [입력조건] 첫째 줄에 0과 1로만 ..
[이코테][Chapter 11][문제] 2. 곱하기 혹은 더하기 [문제] 각 자리가 숫자 (0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'X' 혹은 '+'연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 X를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다. [입력조건] 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1
[이코테][Chapter 11][문제] 1. 모험가 길드 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. N명의 모험가에 대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하라. [입력 예시] 2 3 1 2 2 [출력 예시] 2 간단한 그리디 알고리즘 문제이다. 공포도 X가 낮은 사람일 수록 그룹 형성에 유리하기 때문에, 이렇게 접근해준다. #11-1. 모험가 길드 #풀이 #X가 작은 사람일 수록 그룹 형성에 유리하다. #알고리즘 #1. X를 올림차순으로 정렬한다. #2. 한 사람씩 그룹에 넣는다. 이 때 그 사람의 X를 체크한다. #3. 그룹 사람과 X가 같아지면 그룹으로 묶어준다. #4. 이 과정을 N번만큼 반복한다. #..
[이코테][Chapter 3][문제] 4. 1이 될 때까지 [문제] 어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행하려 한다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. N에서 1을 뺀다. N을 K로 나눈다. N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성 [입력] 첫째 줄에 N(2
[이코테][Chapter 3][문제] 3. 숫자 카드 게임 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. [문제] 카드들이 N X M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만..