본문 바로가기
반응형

개발/Algorithm

 (98)
[프로그래머스] 가장 큰 수(python) Programmers, 가장 큰 수 TL;DR 정렬(sort) 문제 요약 1. 주어진 0 또는 양의 정수들을 이어 붙여서 만들 수 있는 수 중 가장 큰 수를 반환한다. - 입력으로 주어진 수들을 순서를 다르게 배치하여 여러 다른 수를 만들 수 있다. - 만들 수 있는 수 중 가장 큰 수를 문자열 타입으로 반환하면 된다. 입출력 형태 예시 1 :: 6, 10, 2로 만들 수 있는 수 중 가장 큰 수는 6210이다. 따라서 이를 반환하면 된다. - 6, 10, 2로 만들 수 있는 수는 6102, 6210, 1062, 1026, 2610, 2106 이렇게 6가지를 만들 수 있다. 이 중 가장 큰 수는 6210이기 때문에 6210을 반환하도록 작성하면 된다. 풀이 def solution(numbers): # 주..
[프로그래머스] 소수 찾기(python) Programmers, 소수 찾기 TL;DR DFS(깊이 우선 탐색) 문제 요약 1. 한 자리 숫자가 적힌 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내는 함수를 작성하라. - 주어진 숫자들로 만들 수 있는 모든 경우의 숫자들 중에서 소수의 개수를 반환하는 프로그램을 찾으면 된다. - 깊이 우선 탐색(DFS)을 사용해서 만들 수 있는 숫자들의 조합을 찾으면 문제를 해결할 수 있다. 입출력 형태 풀이 import math def solution(numbers): answer = 0 permutations = set() prev_elements = [] def dfs(elements): if ''.join(prev_elements) != '': permutations.add(int(''.join(p..
[프로그래머스] 더 맵게(python) Programmers, 더 맵게 TL;DR 힙(heap) 문제 요약 1. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 갖고 있는 음식을 섞어서 스코빌 지수를 늘리려고 한다. 2. 갖고 있는 음식 중 스코빌 지수를 가장 낮은 두 개의 음식을 아래와 같은 방법으로 섞어 새로운 음식을 만든다. `섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째 맵지 않은 음식의 스코빌 지수 * 2)` 3. 갖고 있는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다. - 보유 하고 있는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 스코빌 지수가 가장 낮은 2개 음식을 뽑아 주어진 공식에 맞게 섞는 것을 반복하면 된다. - 파이썬에서는 힙(heap)이 최소 힙(min hea..
[리트코드] Kth Largest Element in an Array(python) 리트코드, K-th Largest Element in an Array_k번째 큰 원소 TL;DR 힙(heap) 문제 요약 1. 주어진 숫자 배열 nums와 k에 대해서 배열에서 k번째로 큰 원소를 반환한다. 2. k번째 큰 원소는 k번째 개별 원소가 아닌 정렬된 상태에서 k번째로 큰 원소를 의미한다. 입출력 형태 - 예시 1의 경우, 내림차순으로 정렬하면 [6, 5, 4, 3, 2, 1]이 된다. 이 중 2번째로 큰 수는 5이다. - 예시 2의 경우, 내림차순으로 정렬하면 [6, 5, 5, 4, 3, 3, 2, 2, 1]이 된다. 이 중 4번째로 큰 수는 4이다. 풀이 우선, 단순 리스트를 정렬한 후 해당하는 원소를 조회하는 방법으로 해결할 수 있다. class Solution: def findKthLa..
[리트코드] Balanced Binary Tree(python) 리트코드, Balanced Binary Tree_균형 이진 트리 TL;DR 트리(Tree) 깊이 우선 탐색(DFS) 문제 요약 1. 주어진 이진 트리가 높이 균형이 맞는지 아닌지를 판별하는 프로그램을 작성하라. 2. 높이 균형이 맞는 이진 트리는 모든 노드들의 왼쪽 및 오른쪽 서브 트리의 높이 차이가 1을 초과하지 않는 트리를 의미한다. - 형제 노드 간의 차이가 1을 초과하지 않을 때는 True를, 그렇지 않은 경우에는 False를 반환하면 된다. 입출력 형태 - 예시 1의 경우 모든 서브트리에서 높이 차이가 최대 1이다. 그렇기 때문에 True를 반환하였다. - 예시 2의 경우 가장 하위에 있는 서브트리와([3, 4, 4])가 루트의 서브트리([1, 2, 2])와 높이 차이가 1을 초과하기 때문에 f..
[리트코드] Serialize and Deserialize Binary Tree(python) 리트코드, Serialize and Deserialize Binary Tree(이진 트리 직렬화와 역직렬화) TL;DR 트리(Tree) 문제 요약 1. 주어진 트리를 컴퓨터에서 다루기 쉬운 형태로 변형하는 직렬화(Serialize)하는 코드를 작성하라. 2. 직렬화된 트리를 다시 원래의 형태로 되돌리는 역직렬화(Deserialize)하는 코드를 작성하라. 3. 이진 트리를 입력받아 문자열 형태로 직렬화 해야 하고, 직렬화된 문자열을 다시 이진 트리로 역직렬화할 수 있어야 한다. - 트리와 같이 논리적인 데이터 구조를 갖고 있는 자료 구조를 컴퓨터 내부에 저장하기 위해서는 물리적인 구조로 바꾸어주어야 할 필요가 있다. 이 때, 논리적인 데이터 구조에서 물리적인 데이터 구조로 변경하는 작업을 직렬화(Seri..
[프로그래머스] 위클리 챌린지 2주차(python) 프로그래머스 위클리 챌린지 2주차 TL;DR 배열(리스트, List) 구현(Implementation) 문제 요약 1. 학교의 과제에서 각 학생들이 받은 점수의 평균을 사용해서 각 학생이 받은 학점을 반환하는 함수를 작성한다. 2. 각 학생들은 자기 자신과 다른 학생들의 점수를 준다. 3. 각 학생들의 점수에서 자기 자신이 준 점수가 받은 점수 중 유일한 최고점이거나 최저점일 경우 해당 점수를 제외하고 평균을 계산한다. 4. 평균이 90점 이상인 학생은 A, 80점 이상 90점 미만인 학생은 B, 70점 이상 80점 미만인 학생은 C, 50점 이상 70점 미만인 학생은 D, 50점 미만인 학생은 F를 부여한다. - 학생들은 자기 자신 및 다른 학생들에게 점수를 부여한다. - 한 학생이 받은 점수 중 자기..
[백준] 그대, 그머가 되어(python) 백준, 그대, 그머가 되어 TL;DR 너비 우선 탐색(BFS) 다익스트라 알고리즘(Dijkstra Algorithm) 문제 요약 1. 바꿀 수 있는 문자 간의 관계가 표현되어 있는 그래프에서 주어진 문자를 바꿀 수 있는 최소 횟수를 반환하라. 2. 문자를 바꿀 수 없는 경우에는 -1을 출력한다. - 문자를 다른 문자로 바꿀 수 있는 관계가 주어진다. - 이 관계들에서 바꾸기를 원하는 문자를 바꿀 문자로 바꾸는데 걸리는 과정의 최소 횟수를 반환하는 프로그램을 작성하면 된다. - 각 문자들을 노드로, 바꿀 수 있는 노드들 사이의 관계를 간선의 형태로 그래프로 표현할 수 있다. 이 때, 그래프는 방향성이 없는 무향 그래프이다. - 노드 사이의 관계를 표현할 때 꺽쇠''가 아닌 괄호'()'를 사용하여 표현한 것..

티스토리툴바