본문 바로가기

알고리즘

 (138)
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 파괴되지 않은 건물 문제를 정리해보자. N x M 크기의 행렬 모양의 게임 맵이 있다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있다. 1. 건물은 적의 공격을 받으면 내구도가 감소한다. 2. 건물은 내구도가 0이하가 되면 파괴된다. 3. 건물은 아군의 회복 스킬을 받으면 내구도가 증가한다. 4. 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 된다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수는 몇 개인가? 아래는 프로그래머스에 나온 예이다. 풀이를 생각해보자. 방법 1) 매번 적의 공격 혹은 아군의 회복 스킬을 기본 게임 맵의 내구도에 적용시킨다. 이 방법은 효율성 테스트에서 통과할 수 없다. skill의 행의 길이는 최대 250,000이다. b..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] k진수에서 소수 개수 구하기 문제를 정리해보자. 양의 정수 n이 주어진다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 조건에 맞는 소수가 몇 개인지 찾으면 된다. 조건은 아래와 같다. ( P는 소수[Prime Number]를 의미한다.) 1. 소수 양쪽에 0이 있는 경우 : 0P0 2. 소수 오른쪽에만 0이 있는 경우 : P0 3. 소수 왼쪽에만 0이 있는 경우 : 0P 4. 소수 양쪽에 아무것도 없는 경우 : P 단, P는 각 자릿수에 0을 포함하지 않는 소수이다. 예를 들어, 101은 P가 될 수 없다. 풀이를 생각해보자. 예를 들어, 437674을 3진수로 바꾸면 211020101011이다.먼저, 211020101011안에서 조건에 맞는지 확인할 수를 찾자. ( N는 수[Number]를 의미한다.) 0을 기준으로 좌우를 ..
[정렬] 각 정렬의 장단점 및 시간 복잡도 장단점 시간 복잡도 출처
[정렬] 삽입 정렬 [Insertion Sort] 삽입 정렬에 대해 알아보자. 사진 출처 개념 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬한다. 특징 버블/선택 정렬은 내부에서 정렬이 거듭될수록 탐색 범위가 줄어든다. 하지만 삽입 정렬은 오히려 정렬 범위가 늘어난다. 복잡도 버블, 선택 정렬과 마찬가지로 별도의 추가 공간을 사용하지 않는다. 주어진 배열 내에서 값들이 위치를 변경하기 때문에 공간 복잡도는 O(1)이다. 모든 데이터가 현재 데이터가 되어야 하므로 O(N)이 필요하다. 현재 데이터는 정렬된 데이터들과 비교하기 위해 O(N)이 필요하다. 따라서 시간복잡도는 O(N^2)이다. 구현 def insertion_sort(li): for end in range(1, len(li)): for i in range(en..
[정렬] 선택 정렬 [Selection Sort] 선택 정렬에 대해 알아보자. 사진 출처 개념 정렬되지 않은 부분에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환한다. 이를 모두 정렬될 때까지 반복한다. 복잡도 버블 정렬과 마찬가지로 별도의 추가 공간을 사용하지 않는다. 주어진 배열 내에서 값들이 위치를 변경하기 때문에 공간 복잡도는 O(1)이다. 가장 작은 원소를 앞에 계속 쌓아주기 위해 O(N)이 필요하고, 가장 작은 원소를 찾기 위해 O(N)이 필요하다. 따라서 시간복잡도는 O(N^2)이다. 구현 def selection_sort(li): l = len(li) for i in range(l - 1): min_idx = i for j in range(i + 1, l): if li[j] < li[min_idx]: min_idx = j li[i],..
[정렬] 버블 정렬 [Bubble Sort] 버블 정렬에 대해 알아보자. 사진 출처 개념 오름차순으로 정렬할 경우, 서로 이웃한 데이터들을 비교하여 더 큰 데이터를 뒤로 보낸다. 1회 정렬 후에는 가장 큰 데이터가 가장 뒤에 위치하게 된다. 이것을 반복해서 오름차순으로 정렬시킨다. 복잡도 별로의 추가 공간을 사용하지 않는다. 주어진 배열 내에서 값들이 위치를 변경하기 때문에 공간 복잡도는 O(1)이다. 가장 큰 데이터를 계속해서 가장 뒤에 위치시켜야 하므로 O(N), 서로 이웃한 데이터들의 비교를 위해서 O(N)이 필요하다. 따라서 시간복잡도는 O(N^2)이다. 구현 # 기본 def bubble_sort(li): for i in range(len(li) - 1, 0, -1): for j in range(i): if li[j] > li[j + 1]:..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 양과 늑대 문제를 정리해보자. 1. 이진 트리 모양의 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있다. 2. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 한다. 3. 각 노드를 방문할 때마다 해당 노드에 있던 양과 늑대가 나를 따라온다. 4. 이때, 양의 수보다 늑대의 수가 많아지면 모든 양은 잡아 먹힌다. 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아보자. 풀이를 생각해보자. 0번 - 2번 - 5번 - 1번 - 4번 - 8번 - 3번 - 7번 노드 순으로 이동하면 양 5마리, 늑대 3마리가 된다. 여기서 6번, 9번 노드로 이동하면 양 5마리, 늑대 5마리로 양이 모두 잡아 먹힌다. 따라서 늑대에게 잡아먹히지 않도록 하면서 최대로 모을 수 있는 양은 5마리이..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 주차 요금 계산 문제를 정리해보자. 주차장의 요금표와 차량의 입/출자 기록이 있다. 차량별로 주차요금을 계산하자. 기본시간 이하로 이용했다면, 기본요금만 지불한다. 기본시간을 초과했다면, 기본요금 + 추가요금을 지불한다. 기본시간(분) : 180분 기본요금(원) : 5000원 단위시간(분) : 10분 단위요금(원) : 600원 예) 5961 입차 : 5시 34분 (334) 출차 : 7시 59분 (479) = 145분 입차 : 22시 59분 (1379) 출차 : 23시 (1380) = 1분 5961 결과 146분 (기본시간 이하) : 5000원 예) 0000 입차 : 6시 00분 (360분) 출차 : 6시 34분 (394분) = 34분 입차 : 18시 59분 (1139분) 출차 : 23시 59분 (강제, 1439분) = ..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 신고 결과 받기 문제를 정리해보자. 게시판 불량 이용자[용의자]를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발했다. 규칙은 다음과 같다. 1. 각 유저는 한 번에 한 명의 유저만 신고할 수 있다. 1-1) 신고 횟수에 제한이 없다. 1-2) 서로 다른 유저를 계속해서 신고할 수 있다. 1-3) 한 유저를 여러 번 신고할 수 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리된다. 2. k번 이상 신고된 유저는 게시판 이용이 정지된다. 2-1) 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 보낸다. 2-2) 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송한다. 3. 자기 자신을 신고하는 경우는 없다. 위 규칙을 바탕으로, 유저별로 처리 결과 메일을 받은 ..
[프로그래머스][Python] 가장 먼 노드 문제를 정리해보자. n개의 노드가 있는 그래프가 있다. 각 노드는 1부터 n까지 번호가 적혀있다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하자. 가장 멀리 떨어진 노드란? 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드이다. 풀이를 생각해보자. 간선에 가중치가 없다. 따라서 N번 노드와 1번 노드의 최단 경로는 간선이 가장 적은 경로이다. 예를 들어, 5번 노드와 1번 노드의 최단 경로는 1 -> 2 -> 5이다. BFS로 최단 경로를 구할 수 있다. 구현해보자. from collections import deque def solution(n, edge): graph = [[] for _ in range(n + 1)] for node in edge: A, B = node[0], node[..

티스토리툴바