Hello World!

https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from collections import deque def solution(maps): queue=deque([(0,0)]) d=[(1,0), (-1,0), (0,-1), (0,1)] n, m=len(maps), len(maps[0]) visited=[[False]*m for _ in range(n)] while queue: x, y=queue.popleft() if (x, y)==(n-1, m-..

알고리즘의 성능을 나타내는 척도 시간복잡도와 공간복잡도 시간 복잡도 : 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지 공간 복잡도 : 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지 trade-off 관계 시간 복잡도 빅오 표기법 - 함수의 상한만을 나타냄 가장 빠르게 증가하는 항만을 고려하는 표기법 공간 복잡도 일반적인 메모리 사용량 기준은 MB 단위로 제시됨

서로 다른 개체가 연결되어 있다 --> 그래프 알고리즘 떠올릴 것 최소 힙 : 트리 자료구조에 속함. 계층적인 모델 서로소 집합 Disjoint Sets - 서로소 집합 자료구조 --> union-fine 자료구조라고 불리기도 함 - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - 트리 자료구조를 이용해서 집합을 표현 - union과 find 2개의 연산으로 조작 가능 union 2개의 원소가 포함된 집합을 하나의 집합으로 합침 find 특정한 원소가 속한 집합이 어떤 집합인지 알려줌 트리 자료구조를 이용해서 집합 표현하는 서로소 집합 계산 알고리즘 1. union을 확인해서 서로 연결된 두 노드 A, B를 확인 1) A와 B의 루트 노드 A', B'를 각각 찾음 2) A'를 ..

최단 경로 Shortest Path 보통 그래프를 이용해서 표현 지점은 노드, 도로는 간선 e.g. 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 다익스트라 최단 경로 알고리즘 Diikstra 특정 노드에서 출발해서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것 음의 간선이 없을 때 정상적으로 작동 GPS 소프트웨어의 기본 알고리즘으로 주로 채택 그리디 알고리즘 인접 리스트 이용 -> 노드와 연결된 모든 간선에 대한 정보를 리스트에 저장 알고리즘 원리 1) 출발 노드 설정 2) 최단 거리 테이블 초기화(무한) 3) 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 4) 해당 노드 거쳐 다른 노드로 가는 비용 ..

다이나믹 프로그래밍 Dynamic programming, 동적 계획법 조건) 1. 큰 문제를 작은 문제로 나눌 수 있음 2. 작은 문제에서 구한 정답은 그걸 포함하는 큰 문제에서도 동일 -> 큰 문제를 작게 나눠서 같은 문제는 한 번씩만 풀어서 문제를 효율적으로 해결하는 알고리즘 메모이제이션 Memoization 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져옴 탑다운 방식 Top-down 재귀 함수를 이용해서 다이내믹 프로그래밍 소스코드를 작성하는 방법 바텀업 방식 Bottom-up 반복문을 이용해서 소스코드를 작성하는 방식

이진 탐색 알고리즘 : 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘 순차 탐색 Sequential Search 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 정렬되지 않은 리스트에서 데이터 찾을 때 사용 이진 탐색 Binary Search 배열 내부의 데이터가 정렬되어있어야만 사용 가능함 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것 입력 데이터가 많거나 탐색 범위가 넒음 확인하는 원소의 개수가 절반씩 줄어들기 때문에 시간 복잡도 O(logN) # 반복문 def binary_search(array, target, start, end): while start target: end = mid-1 else: ..

정렬 Sorting 데이터를 특정한 기준에 따라 순서대로 나열하는 것 데이터 정렬은 이진 탐색의 전처리 과정 선택 정렬 Selection Sort 데이터 정렬 시 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정의 반복 -> 매번 가장 작은 것을 선택한다는 선택 정렬 알고리즘 : 시간 복잡도 -> O(N^2) 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코테에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있음 array = [7,9,8,6,5,2,3,4,1,0] for i in range(len(array)): min_index=i for j in range(i+1, len(array)): if array[j] O(N..

그래프 탐색 그래프 Graph는 노드 Node와 간선 Edge로 표현됨 그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것 두 노드가 간선으로 연결되어 있으면 두 노드는 인접하다(adjacent)라고 표현 * 인접 행렬 Adjacency Matrix : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 * 인접 리스트 Adjacency List : 리스트로 그래프의 연결 관계를 표현하는 방식 인접 행렬 Adjacency Matrix 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 그래프를 인접 행렬로 표현 시 파이썬에서는 2차원 리스트로 구현 가능 연결되어있지 않은 노드끼리는 infinity의 비용으로 작성 -> 실제 코드에서는 987654321과 같은 값으로 초기화함 0 1 2 0 0..

그래프를 탐색하기 위한 대표적인 2가지 알고리즘 탐색 Search 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 e.g. DFS, BFS 자료구조 Data Structure - 데이터를 표현하고 관리하고 처리하기 위한 구조 - 스택과 큐는 자료구조의 기초 개념 - push, pop으로 구성됨 * 삽입 Push 삭제 Pop 오버플로우 Overflow 특정 자료구조가 수용할 수 있는 데이터의 크기를 가득 찬 상태에서 삽입 연산 수행 시 발생 (저장 공간 벗어나 데이터가 넘쳐흐를 때) 언더플로우 Underflow 특정 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산 수행 시 발생 스택 Stack 박스 쌓기 선입후출 First In Last Out 후입선출 Last In First Out 파이썬..

완전 탐색 유형 : 가능한 경우의 수를 모두 검사해보는 탐색 방법 -> 비효율적인 시간 복잡도를 가지고 있어 데이터 개수가 큰 경우 정상적으로 동작하지 않을 수도