꾸준히

이론그래프 복습그래프노드(Node)와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조'서로 다른 개체(객체)가 연결되어 있다' -> 그래프 알고리즘그래프 중 트리 자료구조는 다양하게 사용됨부모에서 자식으로 내려오는 계층적인 모델최소 힙, 최대 힙그래프 구현 방법2가지의 방식은 메모리와 속도 측면에서 구별됨노드의 개수가 V, 간선의 개수가 E인 그래프 인접 행렬(Adjacency Matrix): 2차원 배열을 사용하는 방식메모리: 간선 정보를 저장하기 위한 O(V^2)시간: 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있음플로이드 워셜 알고리즘최단 경로를 찾을 때, 노드의 개수가 적은 경우인접 리스트(Adjacency List): 리스트를 사용하는..

이론시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제는 컴퓨터를 활용해도 해결하기 어렵다. 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이기 때문이다. 따라서 두 요소를 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 하지만 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다! 대표적으로 다이나믹 프로그래밍(Dynimic Programming) 기법이 여기 속한다.프로그래밍에서 보통 다이나믹은 '프로그램이 실행되는 도중에'라는 의미이지만, 다이나믹 프로그래밍에서의 '다이나믹'은 이 의미가 아니다. 예시 - 피보나치 수열기존의 알고리즘으로 해결하기 어려운 문제 중에서 다이나믹 프로그래밍으로 해결할 수 있는 문..

Chap 7. 이진 탐색 이론순차 탐색리스트 내에서 데이터를 매우 빠르게 탐색하는 이진 탐색 알고리즘에 대해 알아보기 전에, 가장 기본 탐색 방법인 순차 탐색에 대한 이해가 선행되어야 한다. 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 즉, 이름 그대로 순차로 데이터를 탐색한다는 의미이며, 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 순차 탐색은 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다. 순차 탐색은 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다. 순차 탐색은 데이터의 개수가 N개일 때, 최대 N번..

이론정렬이란?데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. 프로그램에서는 데이터를 사용할 때 오름차 또는 내림차순으로 정렬해서 사용하는 경우가 많다. 정렬 알고리즘으로 이진 탐색의 전처리 과정이기도 하다, 많이 사용하는 정렬 알고리즘에는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬이 있다.아래의 카드를 정렬해보며 다양한 정렬 알고리즘에 대해 알아보자. 데이터의 개수는 N으로 표현하며, 현재 N=10이다.  선택 정렬선택 정렬(Selection Sort)은 무작위로 여러 개 있는 데이터 중 가장 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하는 것이다. 매번 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라고 한..

Q15 | 특정 거리의 도시 찾기 ✅ Q16 | 연구소[백준|골드4] 연구소 - Python(파이썬) [백준|골드4] 연구소 - Python(파이썬)문제https://www.acmicpc.net/problem/14502인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에ghi512.tistory.com Q17 | 경쟁적 전염[백준|골드5] 18405번 경쟁적 전역 - Python(파이썬) [백준|골드5] 18405번 경쟁적 전역 - Python(파이썬)문제NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이..

기초 지식탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 대표적인 탐색 알고리즘에는 DFS와 BFS가 있다. 두 알고리즘의 원리에는 스택, 큐와 같은 기본 자료구조 그리고 재귀 함수가 사용되기 때문에 이에 대한 이해가 전제되어야 한다. 이때 자료구조는 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 스택스택(Stack)은 박스 쌓기와 유사한 구조로, 후입선출(LIFO) 이다.파이썬에서 스택을 이용할 때엔 기본 리스트의 메서드를 이용하면 된다. ✓ append() : 리스트의 가장 뒤쪽에 데이터 삽입✓ pop() : 리스트의 가장 뒤쪽에서 데이터 꺼냄stack = []stack.append(1) # [1]stack.append(2) # [1, 2]stack.append(3) #..

08. 문자열 재정렬arr = list(input())arr.sort()num = 0i = 0for _ in range(len(arr)): if '0'  문자열을 arr에 리스트로 입력받고 오름차순 정렬을 한다.num은 숫자를 더하기 위한 변수, i는 확인 인덱스를 표시하기 위한 변수이다. 문자열 arr의 길이만큼 반복을 진행한다.i번째 문자가 숫자이면 (0과 9 사이이면) 숫자 합을 구하는 변수 num에 해당 수를 더하고, i번째 문자는 pop한다. 해당 원소를 pop하며 리스트에서 제외했으므로 인덱스 i는 변경하지 않는다.숫자가 아니면 다음 인덱스의 확인을 진행한다. 모든 원소의 확인이 끝나면 숫자가 아닌 남은 문자 arr를 join으로 합치고 num을 문자열로 변환하여 합친다.

이론구현이란?구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제든 소스코드를 작성해야 하므로 모든 범위의 코딩 테스트 문제 유형은 구현을 포함한다.하지만 그중에서도 특히 구현 유형이라 부르는 문제들은'풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 다음의 두 문제 유형은 '구현'이 핵심이 되는 경우가 많다.1) 완전 탐색(브루트포스): 모든 경우의 수를 주저 없이 다 계산하는 해결 방법2) 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 구현하기 어려운 문제- 알고리즘은 간단한데 코드가 지나치게 길어지는 문제- 특정 소수점 자리까지 출력해야 하는 문제- 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 (파싱..

정의현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘탐욕적이다 == 현 상황에서 지금 당장 좋은 것만 고른다.현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.코테 팁그리디 알고리즘 유형의 문제는 매우 다양하다.단순 암기로 모든 유형의 문제를 풀 수는 없다.그리디 알고리즘 유형의 문제는 창의력을 요구한다.특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만 선택해도 문제를 풀 수 있는지 파악할 수 있어야 한다.기준에 따라 좋은 것을 선택하는 알고리즘으로 아래와 같은 기준을 제시해주기도 한다.가장 큰 순서대로가장 작은 순서대로예제 3-2. 큰 수의 법칙문제시간 제한 : 1초메모리 제한 : 128MB'큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본..