야호야허

알고리즘이란? 알고리즘 - 어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합. 여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다. [표준국어대사전] 어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임 시간 복잡도 판단하기 시간 복잡도 - 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계 최댓값 찾기 알고리즘의 시간 복잡도 판단해보기 첫 번째 방법 input = [3, 5, 6, 1, 2, 4] def find_max_num(array): for num in array: for compare_num in array: if num < compare_num: break else: return num resul..

https://youtu.be/uyd6OLyhPJo Sammy was low, just watching the show Over and over again Knew it was time, he'd made up his mind To leave his dead life behind His boss said to him, "Boy, you'd better begin To get those crazy notions right out of your head Sammy, who do you think that you are? You should've been sweeping up the Emerald Bar" Spread your wings and fly away Fly away, far away Spread y..

오늘의 한 일 자료구조, 알고리즘 강의 - 4~5주차 백준 알고리즘 문제 풀이 및 정리 - 정렬 자료구조, 알고리즘 강의 4주차, 5주차 ** 트리 - 이진 트리, 완전 이진 트리 ** 힙 (heapq 모듈 사용) ** DFS (Depth First Search), 깊이 우선 탐색 - 스택 사용 / BFS (Breadth-First Search), 너비 우선 탐색 - 큐 사용 ** 동적 계획법 (Dynamic Programming) - 피보나치 수열 활용 python 백준 알고리즘 10870번: 피보나치 수 5 - 동적 프로그래밍 활용해보기 https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, ..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표 압축 - 수의 범위가 매우 큰 상황에서 수의 값과 상관없이 좌표들 사이의 대소만 구별할 때 사용 1. 좌표 압축을 할 배열을 임시의 배열에 중복이 없고(set) 정렬된(sort) 상태로 만들어 둔다. 2. 압축할 배열의 각 수들이 임시 배열의 몇 번째 인덱스에 해당하는 수인지 찾는 것으로 대소를 구별한다. 임시 배열은 정렬된 상태이기 때문에 ..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 띄어쓰기를 기점으로 두 정보를 받아서 리스트 형식으로 리스트에 저장 나이순 정렬 (key = lambda x: int(x[0]) 나이[0], 이름[1] 출력 내 제출 import sys n = int(sys.stdin.readline()) member_list = [] for i in range(n): member_list.append(list(sys.stdin.readline().split())) m..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 중복 제거 - set 자료형 / if (변수) not in: 문자열을 길이순으로 정렬 - sort(key = len) 두 가지만 신경써주면 계속 쓰던거 쓰는 문제. 내 제출 import sys n = int(sys.stdin.readline()) set_list = set() # 중복제거 for i in range(n): set_list.add(sys.stdin.readline().st..

https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 11650번과 비슷한 문제이지만 이번에는 기준점이 y점이다. 단순하게 y와 x의 배열을 바꾼것으로 해결 내 제출 import sys n = int(sys.stdin.readline()) array = [] for i in range(n): [x, y] = map(int, sys.stdin.readline().split()) array.app..

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 배열 안에 N개만큼 좌표를 저장 정렬 for 반복문으로 배열[i][0] (x좌표) 배열[i][1] (y좌표) 출력 내 제출 import sys n = int(sys.stdin.readline()) array = [] for i in range(n): [x, y] = map(int, sys.stdin.readline().split()) array..

https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net N을 string으로 변환해 한 글자씩 분리해서 리스트에 저장해둔다 리스트 내림차순으로 정렬 반복문을 이용해 첫글자부터 출력 내 제출 import sys n = int(sys.stdin.readline()) num_list = [] for i in str(n): num_list.append(int(i)) num_list.sort(reverse = True) for i in num_list: print(i, end = '')

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 산술평균 - round(sum(nums) / n) 중앙값 - sort 혹은 sorted 정렬 후, 정중앙 수 nums[int((n - 1) / 2)] ** 최빈값 첫 구상 - 딕셔너리 생성 후 정수들 append 해서 가장 많은 밸류 찾기 구글링을 했더니 collection 모듈의 Counter 함수를 사용해 빈도수를 구하는 방법이 있었다. 출력 조건중 최빈값이 여러 개 있을 때에는 그중 두 번째로 작은 값을 ..