Coder/알고리즘
이코테 CHAPTER 10 그래프 이론 정리
그래프 이론 그래프 이론 복습 (추후에 추가 예정) 1. 서로소 집합 서로소 집합(Disjoint Sets) : 공통 원소가 없는 두 집합 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 두 종류의 연산을 지원 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 합치기 찾기(Union Find) 자료구조라고도 불림 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정은 다음과 같음 합집합 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 A와 B의 루트 노드 A’, B’ 를 각각 찾는다. A’를 B’의 부모 노드로 설정한다. 일반적으로 ..
이코테 CHAPTER 09 최단경로 정리
가장 빠른 길 찾기 최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 음의 간선이 없을 때 정상적으로 동작함 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음 → 사용 가능 그리디 알고리즘으로 분류됨, 또는 DP 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 다익스트라 최단 경로 알고리즘 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중에서 최단 거리가..
이코테 CHAPTER 03 그리디 실전 문제
실전문제 숫자 카드 게임 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 카드들이 N x M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오..
이코테 CHAPTER 03 그리디 정리 및 실전 문제(큰 수의 법칙)
당장 좋은 것만 선택하는 그리디 그리디 알고리즘(탐욕법) 현재 상황에서 지금 당장 좋은 것만 고르는 방법 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함 그리디 해법은 그 정당성 분석이 중요 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 예시 최적의 해를 보장하지 못함 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음 하지만 코테에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨 거스름 돈 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다. N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러..
이코테 CHAPTER 07 이진 탐색 실전 문제
실전문제 부품 찾기 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 나의 풀이 N = int(input()) all = list(map(int,input().split())) M = int(input()) find = list(map(int,input().split())) def binary_search(array, target, start, end): while start target: end = mid - 1 # ..
이코테 CHAPTER 07 이진 탐색 정리
범위를 반씩 좁혀가는 탐색 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 count() 메서드도 내부에서 순차 탐색 수행 최악의 시간 복잡도 O(N) 순차 탐색 구현 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기) print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") input_data = input().split() n = int(..
이코테 CHAPTER 06 정렬 실전 문제
실전문제 성적이 낮은 순서로 학생 출력하기 N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오. 나의 풀이 n = int(input()) name_score = [] for i in range(n): name, score = input().split() name_score.append([name,int(score)]) name_score = sorted(name_score, key = lambda x: x[1]) for i in range(n): print(name_score[i][0], end = ' ') - 처음에 성적인 것 보고 계수 정렬 쓰려고 했다가 안되는..
이코테 CHAPTER 06 정렬 + 실전 문제(위에서 아래로)
기준에 따라 데이터를 정렬 정렬 Sorting 데이터를 특정한 기준에 따라 순서대로 나열 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘을 공식처럼 사용 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 코드 구현 매번 선형 탐색 → 이중 반복문 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 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], a..
[프로그래머스] 어서와! 자료구조와 알고리즘은 처음이지? 4,5강
4강 : 재귀 알고리즘 기초 재귀함수(recursive func.) 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것 종결 조건이 반드시 필요 예시 : 이진트리(binary trees) 예시2 : 자연수의 합 구하기 #Recursive ver. def sum(n): if n=0: s+=n n-=1 return s #복잡도 O(n) #더 효율성 좋은 버전 def sum(n): return n*(n+1)//2 #복잡도 O(1) 상수시간 예시3 : n! (factorial) def what(n): if n
[프로그래머스] 어서와! 자료구조와 알고리즘은 처음이지? 1,2,3강
1강 : 어서와! 자료구조와 알고리즘을 왜 배워야 하는지 알려줄게 파이썬 기본 자료구조 : str, list, dict, tuple, set, ... 자료구조를 왜 알아야할까? 파이썬의 기본 자료구조보다 주어진 문제를 빠르게 행할 수 있는 다른 자료구조가 있기 때문 ⇒ 효율성 알고리즘이란? 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택 선택시 최적의 해법이 (응용 종류와 범위에 따라) 다르기 때문에 자료구조 이해가 필요 2강 : 선형 배열 선형 배열(Linear Arrays) List 활용 보통 array는 같은 type의 데이터만 원소로 존재 가능 (But List는 다른 type의 원소도 가능) 리스트(배열) 연산 #List의 길이와 무관한 연관/상수시간=> O(1) ...big O L..