투투

https://programmers.co.kr/learn/courses/30/lessons/12982?language=python3 코딩테스트 연습 - 예산 S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 programmers.co.kr 접근 예산 내에서 최대한 많은 부서의 물품을 지원해주어야 한다. 이를 위해 그리디로 접근을 하였다. 먼저 신청금액을 오름차순으로 정렬하고 신청금액이 작은 순서부터 탐색하여 예산에서 빼준다. 빼준 값이 0이상일 때 최종해를 증가시켰다. 구현 - 먼저 부서들이 신청한 금액이 들어있는 d를 오름차순으로 정렬한다. - 이제 d의 원소를 하나씩..

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 접근 1번 마을에서 다른 마을로 배달을 갈 때 K시간 이하가 걸리는 마을의 개수를 구해야 한다. 따라서 하나의 노드에서 다른 모든 노드까지의 최단 거리를 구하는 다익스트라 알고리즘을 이용하여 풀었다. 먼저 마을과 마을 간의 연결 정보가 담긴 road를 통해 그래프를 그려주었다. 이후 다익스트라 알고리즘을 통해 1번 마을에서 시작해서 다른..

https://programmers.co.kr/learn/courses/30/lessons/12949 코딩테스트 연습 - 행렬의 곱셈 [[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]] programmers.co.kr 접근 행렬을 곱하기 위해서는 행렬 A와 B가 있을 때 행렬 A의 열 개수와 행렬 B의 행 개수가 같아야 한다. 그리고 행렬의 곱을 그대로 코드로 구현하였다. 구현 - arr2의 행과 열의 개수를 N과 M에 저장했다. - 이제 arr1에서 하나의 리스트를 꺼낸다. - arr2를 탐색하면서 arr1에서 꺼낸 리스트의 숫자들을 행렬 곱을 해주고 이를 ..

https://programmers.co.kr/learn/courses/30/lessons/77885 코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 접근 이런 문제를 규칙을 잘 찾아야할 필요가 있다. 규칙은 다음과 같다. 짝수일 때는 맨 뒤에 있는 0을 1로 변경한다. 홀수일 때는 맨 뒤에 있는 0을 1로 변경하고 그 다음을 0으로 변경한다. 이를 통해 해를 구할 수 있다. 구현 - 7을 bin으로 변경하면 0b111이 되어 0을 찾을 수 없다. 따라서 이러한 경우를 대비하여 미리 앞에 0을 추가한다. - 이어서 문자열로 변경하고 rfind()를 사용하여 '0'의 위치를 idx에 넣는다. - 이후 number가 홀수일 때는 idx+1을 0으로 변경한다. - 위의 과정이 모두 ..

https://programmers.co.kr/learn/courses/30/lessons/17684?language=python3 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 접근 딕셔너리에 A ~ Z 까지를 Key로 각각 1 ~ 26까지의 Value를 짝지어서 저장하여 활용한다. msg를 탐색하면서 각각의 문자를 연결해 새로운 문자를 만들어내고 해당 문자가 딕셔너리에 존재하면 다음 문자도 이어붙인다. 하지만 딕셔너리에 존재하지 않는다면 현재 문자 중에 마지막 문자를 제외한 것을 딕셔너리에 찾아 해당 값을 answer에 저장하..

https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 접근 쿼드 트리를 구현해보았다. 만약 행과 열의 개수가 같은 2차원 리스트에서 행의 개수가 4라고 가정해보자. (0, 0)부터 시작해서 4x4를 모두 탐색했을 때 같은 숫자로..

https://programmers.co.kr/learn/courses/30/lessons/17687 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 접근 먼저 10진수로 진행했을 때 가장 마지막에 말해야하는 숫자까지 n진수로 변환하여 특정 문자열에 저장한다. 이후 n진수로 게임을 진행했을 때 말해야하는 범위까지 입력된 사용자의 차례의 수를 최종해에 대입한다. 구현 - 아래의 함수는 10진수를 n진수로 변환하는 함수이다. - s에 아래와 같이 초기화를 시킨 후에 number를 n으로 나눈 나머..

https://programmers.co.kr/learn/courses/30/lessons/12987 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 접근 A와 B를 모두 오름차순으로 정렬한다. 그리고 A를 탐색하면서 해당 숫자보다 큰 것을 B에서 찾는다. 이때 idx를 사용하여 B를 탐색할 때 사용한다. 만약 A의 첫 번째 숫자보다 큰 것을 찾았다면 B를 처음부터 탐색하는 것이 아니라 큰 것을 찾은 다음 숫자부터 탐색하여 시간을 줄인다. 구현 - A와 B를 오름차순으로 정렬한다. - A의 숫자..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 접근 dfs를 통해 현재 단어에서 1개의 글자만 다를 때 해당 단어로 다음 탐색을 진행한다. 진행하다가 target 단어가 되었을 때 지금까지의 depth가 답이된다. 구현 - 먼저 answer에는 words의 길이에 + 1로 하여 찾지 못했을 때 0을 출력하도록 한다. - picked에 지금까지 선택한 단어들을 추가한..

https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 접근 먼저 각각의 banned_id가 될 수 있는 아이디를 찾는다. 이후 불량 사용자가 될 수 있는 조합을 찾는다. 구현 - names 배열에 해당 banned_id가 될 수 있는 아이디를 담는다. - banned_id를 순차적으로 탐색하여 아이디를 찾는데 길이가 같을 때에 아이디를 비교한다. - 별표(*)가 있을 때는 아무 문자나 올 수 있기 때문에 conti..