투투

문제 K개의 랜선이 있을 때 각각 같은 길이로 잘라서 N개의 랜선을 만든다. 자르고 남은 길이는 사용할 수 없고 N개보다 많이 만들어도 된다. 이때 최대 어느 길이로 잘라야 N개를 만들 수 있는지 구하라. 입력 첫째 줄에 K, N을 입력한다. (K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수) 이어서 K 줄에 걸쳐서 랜선의 길이가 주어진다. 랜선의 길이는 2^31-1보다 이하이다. 출력 N개를 만들 수 있는 랜선의 최대 길이를 출력한다. 접근 이 문제를 통해 이분탐색이 무엇인지 알았다. 이분탐색은 어떠한 범위의 값에서 특정한 값을 찾을 때 범위를 두 개로 나눠서 찾아보는 것이다. 가장 작은 값과 가장 큰 값을 더한 중간값을 찾고 중간값을 기준으로 찾아야하는 수와 비교했을..

programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 접근 길이가 1부터 입력된 문자열의 반만큼의 길이를 갖는 패턴문자를 생성하여 처음부터 탐색을 진행한다. 이 문제에서는 인덱스를 잘 설정해주는 것이 관건이다. 어디서부터 어디까지 잘라서 비교할지 신경을 써야한다. 그렇게 비교를 하다가 패턴문자와 다르다면 지금까지의 패턴의 개수와 패턴을 문자열에 추가해주고 패턴문자를 새롭게 갱신해주도록 한다. 구현 먼저 answer에는 입..

문제 L개의 알파벳 소문자로 구성되어 있는 암호가 있다. 암호는 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어야 한다. 그리고 암호는 알파벳이 증가하는 순서대로 배열되어 있다. C개의 알파벳이 주어졌을 때 L개의 알파벳을 선택하여 만들 수 있는 암호를 출력하라 입력 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. 출력 각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다. 접근 백트래킹 연습을 위해 풀었다. 알파벳을 하나 선택할 때마다 모음과 자음을 카운트한다. 그리고 L개의 알파벳을 골랐을 때 문제의 조건에 부합된다면 출력하도록 구현하였다. 구현 알..

문제 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 입력 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. 출력 첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다. 접근 백트래킹을 연습하고자 했다. 백트래킹으로 만들 수 있는 수열을 만들어 계산을 하고 최댓값을 비교한다. 구현 solve함수에서 수열을 생성한다. 현재 수를 선택하지 않았다면 선택을..

programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 접근 가능한 코스의 조합을 생성하여 딕셔너리에 넣고 카운트하는 방법으로 접근하고자 했다. 하지만 시간초과가 발생할 것 같았다. 최대 10개의 course가 들어오는데 각각의 조합을 만들 때 시간이 많이 걸릴 것 같았지만 시도를 해보았다. 먼저 course에 있는 순서대로 코스를 구성해본다. 각각의 수에 맞는 메뉴가 포함된 코스의 경우의 수를 생성하고 딕셔너리에 키로 저장한다. ..

programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 접근 첫 번째로 풀었을 때는 처음 방문한 점이 몇 개인지 출력하는 줄 알았다. (문제를 꼼꼼하게) 그래서 2차원 그래프를 그려 입력되는 명령대로 움직이며 처음 방문한 점을 카운트하였지만 역시 실패했다. 계속 실패하여 다른 사람들의 풀이를 참고하였고 그제서야 처음 방문한 길을 카운트하는 것을 알았다. 해당 길을 방문했는지 표시하기 위해 (y, x)에서 (ny, nx)를 지나갔다는 의미로 네 개의 좌표를 튜플 형태로 visited에 담는다. 이때 양방향으로 표시하기 위해 (ny, nx)에서 (y, x)로 갔다는 의미의 좌표도 visited에 담는다. 구현 먼저..

programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 접근 DP로 접근을 해보았다. 이전위치에서+1과 비교를 하는데 현재위치가 짝수일 때는 현재위치/2의 사용량과 비교를 하고 홀 수 일때는 현재위치/2 +1과 비교를 한다. 점화식을 세워보면 다음과 같다. 짝수일 때 DP[i] = DP[i-1]+1 or DP[i/2] 홀수일 때 DP[i] = DP[i-1]+1 or DP[i/2]+1 하지만 테스트케이스는 모..

programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 접근 1, 2, 4의 숫자를 활용해서 10진법의 수를 표현해야한다. 3진법을 사용해서 변환을 시도하였고 그 이후에는 어떻게 해야할지 감이 잡히지 않았다. 먼저 3진법으로 변환하는 코드에서 while문을 사용할 때 0을 초과할 때는 n을 3으로 나눈 나머지를 추가하고 n을 3으로 나누는 것을 반복한다. 하지만 124의 나라는 3진법으로 변환할 때 0, 1, 2가 아닌 1, 2, 4를 사용한다. 이때 1~10을 3진법으로 변환하면서 규칙을 찾아야한다. 나머지가 0일 때는 4, 1일 때는 1, 2일 때는 2를 최종해에 추가를 하며 나머지가 0일 때는 몫..

programmers.co.kr/learn/courses/30/lessons/12981 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0] programmers.co.kr 접근 끝말잇기를 하면서 탈락하는 조건을 그대로 구현을 하였다. 이 문제에서는 탈락한 사람과 탈락한 ..

programmers.co.kr/learn/courses/30/lessons/49993# 코딩테스트 연습 - 스킬트리 programmers.co.kr 접근 처음에 중복된 스킬은 주어지지 않는다는 것을 스킬 트리가 담겨있는 리스트 내에 중복된 스킬 트리가 없다는 것을 이해를 했다. 하지만 하나의 스킬 트리 내에 중복된 스킬이 없는 것이었다. 그래서 단순히 skill의 앞에서부터 비교하여 조건에 부합하는 스킬트리가 있는지 판단하였다. 구현 먼저 skill_trees를 탐색하면서 각각의 skill_tree를 검사한다. 스킬의 순서가 담겨있는 skill을 리스트형으로 변환하고 skill_tree를 탐색하면서 skill의 앞과 같은지 확인한다. 다르다면 break가 될 것이며 같다면 앞의 원소가 제거되어 다음 비..