본문 바로가기

분류 전체보기

 (171)
[정렬] 각 정렬의 장단점 및 시간 복잡도 장단점 시간 복잡도 출처
[정렬] 삽입 정렬 [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[..
[프로그래머스][Python] 도둑질 문제를 정리해보자. 아래 그림과 같이 집이 동그랗게 배치된 마을이 있다. 도둑은 이 마을을 털 계획이다. 하지만 인접한 두 집을 털면 경보가 울리게 되어 있다. 그래서 도둑은 경보가 울리지 않게 마을을 털 것이다. 각 집에 돈이 담겨 있을 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구하자. 풀이를 생각해보자. 이 문제에서 주의해야 할 점은 2가지이다. 1. 인접한 두 집을 털면 안 된다. 2. 집이 원형 모양으로 배치되어 있다. 위 그림과 같은 마을이 있다고 하자. 첫 번째 집을 방문하면, 두 번째 집과 여섯 번째 집은 방문하지 못한다. 두 번째 집을 방문하면, 첫 번째 집과 세 번째 집은 방문하지 못한다. 다른 집도 마찬가지이다. 집을 1차원상에 두고 생각해보자. 그리고 조건 1을 보자. 두 집이 인접하..
[Django][장고걸스][ubuntu] Django Form Form을 이용하면 글을 Create, Update, Delete가 가능하다. Create와 Update를 해보자. Form 위치 blog (StartApp) └─── forms.py 1. CREATE [폼 추가하기] Form 작성 장고에서 제공해주는 Form인 ModelForm을 이용했다. blog/forms.py from django import forms from .models import Post class PostForm(forms.ModelForm): class Meta: model = Post fields = ('title', 'text',) Meta는 이 Form을 만들기 위해 어떤 model이 쓰여야 하는지 장고에 알려주는 구문이다. fields에는 보여지게 할 필드를 넣는다. (auth..

티스토리툴바