꾸준히

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

이론최단 경로 알고리즘이란?Shortest Path; 가장 짧은 경로를 찾는 알고리즘길 찾기 문제다양한 종류가 있고, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있음한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우→ 이렇듯 다양한 사례에 맞는 알고리즘을 적용하면 쉽게 문제를 풀 수 있다.표현주로 그래프를 이용해 표현함각 지점 ⇒ 노드지점 간 연결된 도로 ⇒ 간선(사진)코테에서의 최단 거리 알고리즘 유형컴공 학부 수준다익스트라 최단 경로 알고리즘플로이드 워셜 알고리즘벨만 포드 알고리즘코테에 많이 등장하는 유형다익스트라 최단 경로 알고리즘플로이드 워셜 알고리즘그리디 알고리즘과 DP 알고리즘은 최단 경로 알고리즘에 그대로 ..

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

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

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

https://www.acmicpc.net/problem/10825import sysinput = sys.stdin.readlinen = int(input())students = []for _ in range(n): temp = input().split() students.append([temp[0], int(temp[1]), int(temp[2]), int(temp[3])])students.sort(key=lambda x:x[0]) # 학생 이름 사전 순으로 정렬 (오름차)students.sort(key=lambda x:x[3], reverse=True) # 수학 감소하는 순서로 정렬students.sort(key=lambda x:x[2]) # 영어 증가하는 순서로 정렬students.sor..

문제https://www.acmicpc.net/problem/14502인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. ..

문제https://www.acmicpc.net/problem/14888N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. ✓ 1+2+3-4×5÷6✓ 1÷2+3+4-5×6✓..

문제NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다. 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 ..

문제https://school.programmers.co.kr/learn/courses/30/lessons/60058카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다. 용어의 정의'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')'..