Computer Science

[Python] 최단 경로 알고리즘

가장 빠른 길 찾기 최단경로 : 가장 짧은 경로를 찾는 알고리즘 → 길 찾기 문제 각 지점 = 노드 지점간 연결된 도로 = 간선 다익스트라 최단 경로 알고리즘(Dijkstra) : 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각 최단 경로를 구해주는 알고리즘 음의 간선(0보다 작은 값을 가지는 간선)이 없을 때 정상적으로 동작함 출발 노드를 설정한다 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 위 과정에서 3과 4번을 반복한다. → 그리디 알고리즘의 성격을 가지고 있음

[Python] 이진탐색

범위를 좁혀나가는 탐색 순차탐색(Sequential Search) : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 → 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 이진탐색(Binary Search) : 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 → 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정 # 이진 탐색 소스코드 구현(반복문) def binary_search(array, target, start, end..

[Python] 정렬

정렬(Sorting) : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 → 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(binary Search)가 가능 선택 정렬(Selection Sort) : 가장 원시적인 방법으로 가장 작은 것을 선택; 오름차순 기준으로 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복 → 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 데이터를 선택하여 앞에서 두 번째 데이터와 바꾸는 과정을 반복 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)): i..

[Python] DFS(깊이우선탐색)/BFS(너비우선탐색)

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 삽입(Push): 데이터를 삽입한다. 삭제(Pop): 데이터를 삭제한다. 오버플로(Overflow): 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생 언더플로(Underflow): 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생 스택(Stack) 선입후출(First In Last Out) 파이썬에서 Stack을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작 append() 메서드: 리스트의 가장 ..

[Python] 그리디

그리디(탐욕) 알고리즘; Greedy Algorithm "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만, 전체 옵션에서 최적이라는 보장은 없다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 특정 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준 제시하는 경우가 많다. → 그리디 알고리즘은 높은 빈도로 정렬 알고리즘과 함께 출제 큰 수의 법칙 입력조건 첫째 줄에 N(2

[Python] for문을 명시하지 않고, 문자 결합을 생성할 수 있는 방법 - itertools

itertools: 효율적인 looping을 위한 iterator를 만드는 함수 import itertools [ 문자열에서 필요에 맞는 결합을 생성하는 방법 ] pairwise() pairwise('ABCDEFG') #result: AB BC CD DE EF FG​ product() from itertools import product as pd product('ABCD', repeat=2) #result: AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD permutations() from itertools as permutation as pm permutations('ABCD', 2) #result: AB AC AD BA BC BD CA CB CD DA DB DC..

What is SQL?

RDBMS(Relational Database Management System); 관계형 데이터베이스 What is Database? A database is a set of data stored in a computer.(컴퓨터에 저장된 데이터의 집합) This data is usually structured in a way that makes the data easily accessible.(데이터에 접근하기 쉬운 상태로 저장된다) What is Relational Database? It uses a structure that allows us to identify and access data in relation to another piece of data in the database. Often,..

SQL - Multiple Tables

Join(테이블 결합) • JOIN will combine rows from different tables if the join condition is true. SELECT * FROM orders JOIN subscriptions ON orders.subscription_id = subscriptions.subscription_id WHERE subscriptions.description = 'Fashion Magazine'; Inner Join SELECT COUNT(*) FROM newspaper JOIN online ON newspaper.id = online.id; Left Join A left join will keep all rows from the first table, regardles..

SQL - Aggregate Functions

Calculations performed on multiple rows of a table are called aggregates. Count The fastest way to calculate how many rows are in a table is to use the COUNT() function. SELECT COUNT(*) FROM fake_apps WHERE price = 0; Sum SUM() is a function that takes the name of a column as an argument and returns the sum of all the values in that column. SELECT SUM(downloads) FROM fake_apps; Max / Min The MAX..

SQL - Queries

Queries allow us to communicate with the database by asking questions and returning a result set with data relevant to the question. SELECT SELECT name, genre, year FROM movies; AS AS is a keyword in SQL that allows you to rename a column or table using an alias. SELECT name AS 'Titles' FROM movies; DISTINCT(중복 제거) DISTINCT is used to return unique values in the output. It filters out all duplic..