본문 바로가기

알고리즘/이코테(이것이 코딩 테스트다)

 (8)
[이코테/Python] 정렬 - 실패율 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 읽고 정리한 내용 문제 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌습니다. 그녀가 만든 프렌즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감했습니다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였습니다. 이 문제를 어떻게 할까 고민한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했습니다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았습니다. 오렐리를 위해 실패율을 구하는 코드를 완성하세요. 실패율은 다음과 같이 정의합니다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어의 수 전체 스테이지의 개수 N, 게..
[이코테/Python] DFS/BFS - 경쟁적 전염 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 읽고 정리한 내용 문제 NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다. 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에..
[이코테/Python] 구현 - 문자열 재정렬 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 읽고 정리한 내용 문제 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다. 예를 들어 K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력합니다. 입력 S -> str 출력 문자열 - 알파벳은 오름차순, 숫자는 더한 값을 이어서 출력 내 코드 - 풀고 나서 책 풀이를 보니 로직이 동일했다 string = input() alpha = [] sum = 0 for s in string: if s.isalpha(): alpha.append(s) else: sum += int(s) alpha.sort() if sum !=..
[이코테/Python] 구현 - 럭키 스트레이트 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 읽고 정리한 내용 문제 특정조건에서 사용할 수 있는 필살기인 럭키 스트레이트 기술이 있습니다. 그 특정 조건은 현재 캐릭터의 점수를 N이라고 할 때 자릿수를 기준으로 점수 N을 반으로 나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 각 자릿수의 합을 더한 값이 동일한 상황을 의미합니다. N의 자릿수는 짝수로 주어집니다. 예를 들어 점수가 123402라면 왼쪽 부분의 각 자릿수 합은 1+2+3, 오른쪽 부분의 각 자릿수 합은 4+0+2이므로 두 합이 6으로 동일해 럭키 스트레이트를 사용할 수 있습니다. 입력 N -> int : 현재 점수 출력 럭키 스트레이트를 사용할 수 있으면 "LUCKY" 사용할 수 없다면 "READY" 내 코드 num = [..
[이코테/Python] 그리디 - 볼링공 고르기 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 읽고 정리한 내용 문제 A, B 두 사람이 볼링을 치고 있다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 것으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. 예를 들어, N이 5이고, M이 3이며, 각각의 무게가 차례대로 [1, 3, 2, 3, 2] 일때 각 공의 번호가 차례대로 1번부터 5번까지 부여한다. 이 때 두 사람이 서로 다른 공을 고를 수 있는 경우의 수는 총 8가지이다. N개의 공의 무게가 각각 주어질때, 두 사람이 볼링공을 고르는 경우의 수를..
[이코테/Python] 그리디 - 문자열 뒤집기 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 읽고 정리한 내용 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때,..
[이코테/Python] 그리디 - 곱하기 혹은 더하기 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 읽고 정리한 내용 문제 각 자리가 숫자 (0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'X' 혹은 '+'연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 X를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다. 입력 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1
[이코테/Python] 그리디 - 모험가 길드 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 읽고 정리한 내용 문제 한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했는데, 공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는 지 궁금하다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오. 입력 - 첫째 줄에 모험가의 수 N이 주어진다. (1 ≤ N ≤ 100,000) - 둘째 줄에 각 ..

티스토리툴바