투투

programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 접근 최소로 가기위해서는 웅덩이를 피해 오른쪽 또는 아래로만 이동해야한다. 따라서 각 지점으로 올 수 있는 경우의 수를 메모를 해둔다. 즉, 왼쪽과 위의 경로에 대한 경우의 수를 더해주도록 한다. 구현 시작점부터 도착지점까지 경로에 대한 경우의 수를 구한다. 만약 현재 위치가 puddles에 포함되어있다면 continue하고, 그렇지 않다면 현재 경우의 수를 왼쪽 ..

programmers.co.kr/learn/courses/30/lessons/12927?language=python3 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 접근 초기에 접근했던 방법은 n시간만큼 works에서 최댓값을 찾아서 -1씩 해주는 것이었으며 효율성테스트에서 시간초과가 발생했다. 이후 시간이 많이 남았는데 works는 모두 0일 때 계속 검사를 하게되기 때문에 합이 0일 때는 break를 했지만 시간초과가 발생했다. 따라서 어떤 부분에서 최적화를 진행해야할지 생각을 하게되었고,..

programmers.co.kr/learn/courses/30/lessons/49191# 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 접근 이 문제를 풀면서 플로이드-와샬 알고리즘을 알게되었다. 플로이드-와샬은 모든 정점에서 모든 정점으로 이동할 때의 최소비용을 구할 때 사용할 수 있다. 예를 들어, i -> j로 이동할 때의 최소비용을 구하기위해 중간노드를 거쳐서 가는 비용으로 비교를 한다. i -> k, k->j 로 이동할 때의 비용을 통해 최솟값 비교를 진행한다. 해당 개념을 이 문제에 어떻게 적용시킬 수 있을까? 5명의 사람들이 있고 2차원 리스트에 승부결과를 넣는다면 빈 공간은 아직 승부결과를 모른다는 ..

programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 접근 딕셔너리를 활용해서 풀 수 있겠지만 단순히 경우의 수를 구해서 풀 수 있을 것 같았다. 하지만 경우의 수를 구할 줄 몰랐고 한번 찾아봤다. 먼저 입어야하는 옷을 카테고리 별로 구분을 했을 때, 카테고리 별 옷의 개수를 각각 곱해준다면 모든 옷을 선택해서 입을 수 있는 경우의 수가 된다. 하지만 문제에서는 하나 이상을 무조건 입어야한다고 했고 이 말은 카테고리 별로 다입지 않고 하나만 입어도 된다는 뜻이다. 이것의 경우의 수를 구한다면 카테고리 별의 옷의 개수에 +1을 해주고 모두 곱해준다. +1을 해주는 것은 옷을 입지 않았을 때의 경우를 추가한 것이다. ..

programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 접근 이분탐색이 무엇인지는 알았지만 비슷한 유형의 문제만 풀어서 아직 완벽하게 이해하지 못했다. 이 문제는 고득점kit에 이분 탐색으로 분류되어 있다. 그래서 문제를 읽고 이분탐색으로 접근을 하려고했는데 도대체 어떻게 접근을 해야할지 감이 잡히지 않았다. 감이 잡히지 않은 이유 첫 번째는 이분 탐색을 완벽히 이해하지 못해서다. 왜 left와 right값을 주고 mid값을 통해 ..

programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 접근 문제에서 주어진대로 구현하는데에 중점을 두었다. 구현 먼저 num이라는 변수에 입력된 이진수를 대입한다. 그리고 while문으로 반복을 진행하게 된다. num을 탐색하면서 1이면 copy_num에 넣고 아니라면 answer의 1번 인덱스의 수를 증가시킨다. 탐색이 종료되었다면 copy_num의 길이를 다시 이진수로 변환하여 num에 대입한다. 위의 과정을 num이 1일 될 때까지 반복한다. def solution(s): answer = [0, 0] num = s while True: copy_num = '' for i in range(len(..

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

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