투투

문제 절단기로 한 줄에 나열되어 있는 나무를 잘라서 M미터의 나무를 구하려고 한다. 절단기는 고정이 되어있고 높이를 조절하여 해당 높이만큼 나무를 자를 수 있다. N개의 나무 중 절단기로 잘라서 M미터의 나무를 가지려고 할 때 절단기의 최대 높이를 구하라. 정확히 M미터를 가져가지 못하는 경우는 없다. 입력 첫째 줄에 N과 M을 입력하고 이어서 N개의 나무를 입력한다. 출력 절단기의 최대 높이를 출력한다. 접근 이분탐색을 연습해보았다. 구하려고하는 것은 절단기의 최대높이이다. 따라서 절단기의 높이를 조절하여 M미터를 가져갈 수 있는지 탐색을 해야한다. 절단기의 높이를 나무들의 최소높이부터 최대높이까지 탐색하면서 구하기에는 오래걸린다. 따라서 절단기의 높이를 1과 나무의 최대높이의 중간값으로 시작하여 찾아..

문제 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 하지만 테스트케이스는 모..

폼을 통해 게시글을 작성할 때 제목과 내용, 작성시간, 수정시간 등을 데이터베이스의 모델과 연관된 ModelForm을 생성하여 활용하였다. ModelForm을 통해 쉽게 폼을 입력받고 데이터베이스에 저장할 수 있었다. 이처럼 폼 클래스를 사용하면 복잡한 동작도 간단하게 구현할 수 있는데 Django에서는 사용자가 로그인, 로그아웃, 회원가입 등의 기능을 할 수 있도록 폼 클래스를 제공한다. 이를 위해 어떠한 폼이 있는지 알아본다. 로그인과 로그아웃 로그인과 로그아웃을 한다는 것은 서버로부터 쿠키를 부여받고 세션이 시작되거나 종료되는 것을 의미한다. 먼저 로그인 버튼을 눌렀을 때 View에서 어떠한 동작을 하는지 알아보자. 먼저 로그인을 하는 Form을 불러와야 하며 사용자의 인증을 위한 Form은 "dj..

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일 때는 몫..