본문 바로가기

Algorithm

 (77)
[프로그래머스] 코딩테스트 연습 - 가장 큰 수 (Python) 코딩테스트 연습 - 가장 큰 수 [Sort] 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 주어진 입출력 예의 두 번째 예제를 어떻게 풀까 고민하다가 해결했네요ㅎㅎ 풀이 먼저 제 풀이를 간단하게 설명하면 다음과 같습니다. 1. 모든 원소를 str으로 변환 2. (str원소*4)의 가장 앞 4자리를 기준으로 정렬 2번은 두 번째 예제 [3, 30, 34, 5, 9]를 예로 들어 설명해보겠습니다. 문제에서도 그렇고 해당 예제에서 중요한 점은 3, ..
[프로그래머스] 코딩테스트 연습 - 110 옮기기 (Python) 코딩 테스트 연습 - 110 옮기기 [월간 코드 챌린지 시즌2] 코딩테스트 연습 - 110 옮기기 0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다. x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를 programmers.co.kr 문제를 이해하는 것부터 쉽지 않았는데 시간 초과를 해결하는 것도 쉽지만은 않았네요ㅎㅎ.. 풀이 문제를 해결한 방법을 간단하게 말하면 아래와 같습니다. 1. 110을 모두 찾아서 가장 왼쪽에 있는 111 앞에 넣습니다. 문제의 목표는 110을 뽑고 임의의 위치에 삽입해서 사전 순으로 가장 앞에 오도록 하는 것입니다. 사전 순으로는 0이 1보다 먼저 검색되므로 110보다 사전 순..
[프로그래머스] 코딩테스트 연습 - 모두 0으로 만들기 (Python) 코딩테스트 연습 - 모두 0으로 만들기 [월간 코드 챌린지 시즌2] 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr Stack를 이용한 DFS를 사용해서 문제를 해결하기가 까다로운 문제였습니다.. 풀이 먼저 문제의 해결방법은 "LeafNode부터 ParentNode의 값과 합하며 Root로 이동"입니다. 해당 방법이 가능한 이유는 아래와 같습니다. 노드의 가중치를 변경하는 연산은 Tree의 전체 합에 영향을 주지 않습니다. 모든 가중치를 0으로 만드는 +,- 연산들은 교환 법칙이 성립합니다...
[프로그래머스] 코딩테스트 연습 - 스타 수열 (Python) 코딩테스트 연습 - 스타 수열 [월간 코드 챌린지 시즌1] 코딩테스트 연습 - 스타 수열 programmers.co.kr 참... 문제를 꼼꼼히 읽지 않아서 한참을 어렵게 생각했네요... 풀이 제가 해결한 풀이를 간단하게 적어보면 다음과 같습니다. 1. 3번 이상 연속되는 같은 수를 2개의 같은 수로 변경합니다. 2. 가장 빈도가 높은 수를 골라 스타 수열을 만듭니다. 먼저 스타수열을 만들기 위한 조건은 3가지가 있었죠. 본래 수열의 순서를 유지 스타 수열의 길이가 짝수 차례대로 2개씩 묶었을 때 공통된 원소가 최소 하나 이상 간단하게 생각할 수 있는 방법은 가장 높은 빈도의 숫자를 골라 스타 수열을 만드는 방법입니다. [5, 2, 3, 3, 5, 3]를 예로 들어보면 가장 높은 빈도의 숫자 3을 골라 ..
[프로그래머스] 코딩테스트 연습 - 카드 짝 맞추기 (Python) 코딩테스트 연습 - 카드 짝 맞추기 [2021 KAKAO BLIND RECRUITMENT] 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 처음 생각보다 쉽지 않은 문제였던 것 같습니다. 물론 제가 생각이 짧아 헤맨 시간이 대부분이지만ㅎㅎ.. 역시 문제를 빠르게 읽고 풀이를 시작하는 것보다 문제를 꼼꼼히 읽고 한 번에 푸는 것이 더욱 좋다는 것을 다시 한번 느끼네요.. 풀이 먼저 간단하게 제가 풀이한 방법을 적어보자면 아래와 같습니다. 1. Permutation을 사용하여 선택할 카드의 순서를 정합니다. 2. 모..
[프로그래머스] 코딩테스트 연습 - 스티커 모으기(2) (Python) 코딩테스트 연습 - 스티커 모으기(2) [Summer/Winter Coding(~2018)] 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 문제를 처음 봤을 땐 홀수번째 수의 합과 짝수번째 수의 합 중에서 큰 것만 반환하면 되는 줄 알았네요... 당연하게 문제를 틀리고 문제 설명을 천천히 다시 읽어보며 생각해보니 풀이 방향이 조금 생각났습니다ㅎㅎ 풀이 문제에서 필요한 알고리즘 풀이 방법은 DP입니다. 반복문을 통해 스티커들의 수를 차례대로 확인한다고 했을 때, 어떤 수를 추가해야 최댓값이 될..
[프로그래머스] 코딩테스트 연습 - 기지국 설치 (Python) 코딩테스트 연습 - 기지국 설치 [Summer/Winter Coding(~2018)] 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 N의 크기가 200,000,000으로 굉장히 크기 때문에 N의 범위만큼 반복하는 것은 옳은 방법이 아니겠죠. 결국 \( logN \)으로 변경하거나 단순하게 숫자를 이용해서 풀이를 하는 것이 시간 초과를 피하는 방법일 것입니다. 그래서 저는 station들의 간격에 집중을 해서 풀이를 했습니다. 먼저 전파가 도달하지 않는 7의 범위가 있고 기지국의 전파..
[프로그래머스] 코딩테스트 연습 - 풍선 터트리기 (Python) 코딩테스트 연습 - 풍선 터트리기 [월간 코드 챌린지 시즌1] 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 풀이 풍선을 터트리는 조건은 임의의 인접한 두 개의 풍선을 골라 큰 수의 풍선을 터트리는 것이고 단 한번 작은 수의 풍선을 터트릴 수 있습니다. 그렇다면 큰 수의 풍선만을 터트린다고 가정하면 특정 범위에서 살아남는 풍선은 해당 범위에서 가장 작은 수의 풍선이 될 것입니다. 가장 작은 수의 풍선은 범위 내의 어떠한 풍선과 만나도 터트리지 않게 될 테니까요. 그렇다면 임의의 풍선 하나를 남기기 위해서는 어떻게 해야 될까요? 1. 먼저 임의의 풍선 하나를 기준으로 왼쪽 풍선들의 최솟값 left와 오른쪽 풍선들의 ..

티스토리툴바