하미의 기술 블로그

Startup Coding Festival - 스코페 2021 최고의 스타트업 개최 대한민국 개발자 1만명을 위한 scofe2021 ~3/17(수)까지 신청 접수! 대한민국 개발자 1만명을 대상으로 진행되는 스코페2021은, 분야별 최고의 스타트업들이 모여 개발자들만의 www.wanted.co.kr 내 생애 첫 코딩 테스트(?)였던 스코페 2021 후기를 이제야 기록해보려 한다. 일시: 2021년 3월 20일 (토) 14시~18시 제한 시간: 4시간 문제 수: 6문제 문제 1 - 대여 시간을 추천해드립니다 public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedRe..

💡 '서로 다른 개체가 연결되어 있다' or '여러 개의 도시가 연결되어 있다' ⇒ 그래프 알고리즘 그래프와 트리 속성 그래프 트리 방향성 방향 그래프 or 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 X O 노드간 관계성 부모와 자식 관계 X 부모와 자식 관계 O 모델의 종류 네트워크 모델 계층 모델 서로소 집합 union: 하나의 집합으로 합치는 연산 find: 특정한 원소가 속한 집합을 알려주는 연산 서로소 집합 알고리즘 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b):..

다익스트라 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 음의 간선이 없을 때 ex) GPS 그리디 알고리즘 매번 '가장 비용이 적은 노드'를 선택하기 때문 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산 → 최단 거리 테이블 갱신 5. 위 과정에서 3,4번 반복 방법1: 간단한 다익스트라 시간복잡도: O(V^2) import sys input = sys.stdin.readline INF = int(1e9) # 10억 n, m = map(int, input().split()) # 노드 개수, 간선 개수 start = int(input()) # 시작..

DP 사용 조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 탑다운(Top-Down) 방식 # 피보나치 수열 with 재귀 함수 d = [0] * 100 def pibo(x): if x == 1 or x == 2: return 1 if d[x] != 0: return d[x] d[x] = pibo(x-1) + pibo(x-2) return d[x] 보텀업(Bottom-Up) 방식 # 피보나치 수열 with 반복문 d = [0] * 100 d[1] = 1 d[2] = 1 for i in range(3, 99): d[i] = d[i-1] + d[i-2] 파이썬 재귀 제한 완화 import sys sys.setrecursionlimit(10**6)..

순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 시간복잡도:O(N) 이진 탐색 배열 내부 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하는 방법 시간복잡도:O(logN) 재귀 함수로 구현한 이진 탐색 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 if array[mid] == target: return mid elif array[mid] > target: return binary_search(array, target, start, mid - 1) els..

정렬이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택 정렬 매번 가장 작은 것을 선택하여 맨 앞과 교체하는 방법 시간 복잡도: O(N^2) for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] 삽입 정렬 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 방법 시간 복잡도: O(N^2), 데이터가 정렬되어 있는 경우 O(N) for i in range(1, len(array)): for j in range(i, 0, -1..

탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조란? 데이터를 표현하고 관리하고 처리하기 위한 구조 스택 (Stack) 선입후출 (First In Last Out) / 후입선출 (Last In First Out) 파이썬에서는 list 자료형을 스택으로 사용할 수 있다. stack = [] stack.append(5) stack.pop() 큐 (Queue) 선입선출 (First In First Out) 파이썬에서는 deque을 사용해 큐를 구현하는 것이 가장 빠른 방법이다. from collections import deque queue = deque() queue.append(5) queue.popleft() 재귀 함수란? 자기 자신을 다시 호출하는 함수 파이썬 인터프리터는 호출 횟..

내장 함수 sum result = sum([1,2,3,4,5])# 15 min result = min(7,3,5,2)# 2 max result = max(7,3,5,2)# 7 eval result = eval("(3+5) * 7")# 56 sorted result = sorted([9,1,8,5,4])# [1,4,5,8,9] result = sorted([9,1,8,5,4], reverse=True)# [9,8,5,4,1] result = sorted([('홍길동', 35), ('이순신', 75), ('아무개', 50)], key=lambda x: x[1], reverse=True)# [('이순신', 75), ('아무개', 50), ('홍길동', 35)] sort - 내부 값이 바로 변경됨 data = ..

hammii (HaYeong Jang) - velog 기수 정렬 (Radix Sort) 낮은 자리수부터 비교하여 정렬하는 알고리즘ex) 200, 152, 2, 0, 32, 45, 99, 87 있다고 할 때,Queue이기 때문에 선입선출이다. 200, 0, 152, 2, 32, 45, 87, 99 로 정렬된다.십의 자리가 없는 velog.io 올해 초부터 Velog에 알고리즘 정리를 시작하면서 블로그 활동을 시작했습니다. 그때 당시, 1. Velog 2. Tistory 3. Github 블로그 세 가지 중에 고민하다 예쁘고 심플한 Velog를 선택하여 사용해 왔는데요. Tistory를 보며 방문자, 인기게시물 기능이 너무 부럽더라구요. 그래서 계속 고민만 하다, 결국 옮기게 되었습니다! Velog의 장/단..