코딩테스트
구현_심화9) 문자열 압축
링크 https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 "어피치"틑 문자열 압축하는 알고리즘을 공부하고 있다. 예를 들어 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않는 경우 1은 생략) 와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단..
구현_심화8) 문자열 재정렬
문제 알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다. 예를 들어 K1KA5CB7 이라는 값이 들어오면 ABCKK13을 출력합니다. 입력 첫째 줄에 하나의 문자열 S가 주어집니다. (1
2주차 - 구현
Implementation 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 과정을 구현이라고 합니다. 대체적으로 풀이를 떠올리는 것은 쉽지만 구현 과정이 까다로운 문제들을 구현 문제라고 칭합니다. 동일한 알고리즘이라면 더 간결하고 효율적으로 작성한 코드가 잘 작성된 코드이므로, 문제 해결 아이디어를 떠올리는 것과 별개로 구현 능력은 코딩 테스트 뿐만 아니라 실무에서도 매우 중요합니다. 💡 구현 능력이 요구되는 대표적인 알고리즘 유형 완전 탐색 모든 경우의 수를 빠짐없이 계산하는 해결 방법 문제에 주어진 입력 조건들을 잘 파악해서 제한 시간안에 작성한 코드가 돌아갈 수 있는지를 파악할 줄 알아야합니다 시뮬레이션 문제에서 제시하는 논리나 동작 과정을 그대로 코드로 옮겨야 하는 유형 dx, dy..
그리디 1-4) 1이 될 때까지
문제 어떠한 수 N이 1이 될 때까지 아래 두 과정중 하나를 반복적으로 수행한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. N에서 1을 뺀다. N을 K로 나눈다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오. 입력조건 첫째 줄에 N과 K가 공백으로 구분되며 각각 자연수로 주어진다. 이 때 입력으로 주어지는 N은 항상 K보다 크거나 같다. 출력조건 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 횟수의 최솟값을 출력한다. 문제해설 주어진 N에 대하여 '최대한 많이 나누기'를 수행하면 된다. 왜냐하면 어떠한 수가 있을 때, '2 이상의 수로 나누는 것'이 '1을 빼는 것'보다 숫자를 ..
그리디 1-3) 숫자 카드 게임
문제 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 입력 조건 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1이..
그리디 1-2) 큰 수의 법칙
실전 1. 큰수의 법칙 문제 해설 이 문제를 해결하려면 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다. # 큰수의 법칙 def maxNum(n, m, k, listNum): result = 0 listNum.sort() max1 = listNum[-1] max2 = listNum[-2] q = 1 while True: if m == 0: break maxN = max(listNum) for t in range(k): if m == 0: break print(max1) result += max1 m -= 1 print(max2) result += max2 m -= 1 return result print(maxNum(5,8,3,[2,4,5,4,6])) 이 문제는 반복되는 수열에 대해서 ..