알고리즘
1.[알고리즘] 1일차 (시간 복잡도, 데이터 크기) #백준2750번
알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 파이썬은 2000만 번~1억 번의 연산을 1초의 수행 시간으로 예측할 수 있다.시간 복잡도의 3가지 유형은 아래와 같다.• 빅-오메가: 최선일 때(best case)의 연산 횟수를
2.[알고리즘] 2일차 (숫자의 합, 평균, 구간 합) #백준11720번 #백준1546번 #백준11659번 #백준11660번
• 인덱스를 사용하여 값에 바로 접근할 수 있다.• 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.• 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크
3.[알고리즘] 3일차 (나머지 합, 연속된 자연수의 합) #백준10986번 #백준2018번
📌 문제 005) 나머지 합 구하기 시간 제한 1초, 골드 III, 백준 10986번 > 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + A
4.[알고리즘] 4일차 (주몽의 명령, '좋은 수' 구하기) #백준1940번 #백준1253번
📌 문제 007) 주몽의 명령 시간 제한 2초, 실버 IV, 백준 1940번 > 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을
5.[알고리즘] 5일차 (DNA 비밀번호, 최솟값 찾기 1) #백준12891번 #백준11003번
03-4 슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 이동하며 문제를 해결한다. 투 포인터 알고리즘과 매우 비슷하고 원리도 간단하므로 설명 없이 바로 실전 문제를 풀며 슬라이딩 윈도우 알고리즘 개념과 원리를 공부해
6.[알고리즘] 6일차 (스택으로 수열 만들기, 오큰수 구하기) #백준1874번 #백준17298번
03-5 스택과 큐 스택과 큐는 리스트에서 조금 더 발전한 형태의 자료구조이다. 스택과 큐는 구조는 비슷하지만 처리 방식이 다르다. [스택 핵심 이론] 스택은 삽입과 삭제 연산이 후입선출 LIFO로 이뤄지는 자료구조이다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는
7.[알고리즘] 7일차 (카드 게임, 절댓값 힙 구현하기) #백준2164번 #백준11286번
📌 문제 013) 카드 게임 시간 제한 2초, 실버 IV, 백준 2164번 > N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작
8.[알고리즘] 8일차 (수 정렬하기 1, 버블 정렬 프로그램 1, 내림차순으로 자릿수 정렬하기) #백준2750번 #백준1377번 #백준1427번
정렬 - 버블 정렬 - 데이터의 인접 요소끼리 비교, swap 연산 수행하며 정렬 - 선택 정렬 - 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하며 정렬 - 삽입 정렬 - 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾
9.[알고리즘] 9일차 (ATM 인출 시간 계산하기, K번째 수 구하기) #백준11399번 #백준11004번
04-3 삽입 정렬 삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다. 시간 복잡도는 O(n^2)로 느린 편이지만 구현하기가 쉽다. [삽입 정렬 과정] 현재 index에 있는 데이터 값을 선택한다. 현재 선택한 데
10.[알고리즘] 10일차 (수 정렬하기 2, 버블 정렬 프로그램 2, 수 정렬하기 3) #백준2751번 #백준1517번 #백준10989번
04-5 병합 정렬 병합 정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다. 시간 복잡도는 O(nlogn)이다. 코딩 테스트의 정렬 관련 문제에 자주 등장한다. 2개의 그룹을 병합하는 원리는 꼭 숙지해두자. [2개의 그룹을
11.[알고리즘] 11일차 (연결 요소의 개수 구하기, 신기한 소수 찾기, 친구 관계 파악하기) #백준11724번 #백준2023번 #백준13023번
탐색 탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘이다. 주어진 데이터의 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하다. 실제 코딩 테스트 문제의 기본이 되는 알고리즘이므로 직접 구현해 원리를
12.[알고리즘] 12일차 (DFS와 BFS 프로그램, 미로 탐색하기, 트리의 지름 구하기) #백준1260번 #백준2178번 #백준1167번
05-2 너비 우선 탐색 너비 우선 탐색 BFS도 그래프를 완전 탐색하는 방법이다. 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. 기능: 그래프 완전 탐색 특징: FIFO 탐색, Queue 자료구조 이용 시간 복
13.[알고리즘] 13일차 (원하는 정수 찾기, 블루레이 만들기, 배열에서 K번째 수 찾기) #백준1920번 #백준2343번 #백준1300번
05-3 이진 탐색 📌 문제 029) 원하는 정수 찾기 시간 제한 2초, 실버 IV, 백준 1920번 > N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 > 첫째 줄에 자연수
14.[알고리즘] 14일차 (동전 개수의 최솟값 구하기, 카드 정렬하기, 수를 묶어서 최댓값 만들기) #백준11047번 #백준1715번 #백준1744번
그리디 06-1 그리디 알고리즘 📌 문제 032) 동전 개수의 최솟값 구하기 시간 제한 1초, 실버 III, 백준 11047번 > 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고
15.[알고리즘] 15일차 (회의실 배정하기, 최솟값을 만드는 괄호 배치 찾기) #백준1931번 #백준1541번
📌 문제 035) 회의실 배정하기 시간 제한 2초, 실버 I, 백준 1931번 > 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하
16.[알고리즘] 16일차 (소수 구하기, 거의 소수 구하기) #백준1929번 #백준1456번
정수론 07-1 소수 구하기 [소수 구하기의 핵심 이론] 📌 문제 037) 소수 구하기 시간 제한 2초, 실버 III, 백준 1929번 > M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 > 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진
17.[알고리즘] 17일차 (소수 & 팰린드롬 수 중에서 최솟값 찾기, 제곱이 아닌 수 찾기) #백준1747번 #백준1016번
시간 제한 2초, 골드 V, 백준 1747번어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79197과 324423 등이 팰린드롬 수이다.어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소
18.[알고리즘] 18일차 (오일러 피 함수 구현하기, 최소 공배수 구하기) #백준11689번 #백준1934번
07-2 오일러 피 [오일러 피의 핵심 이론] 📌 문제 041) 오일러 피 함수 구현하기 시간 제한 1초, 골드 I, 백준 11689번 > 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.
19.[알고리즘] 19일차 (최대 공약수 구하기, 칵테일 만들기) #백준1850번 #백준1033번
시간 제한 2초, 실버 II, 백준 1850번모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이
20.[알고리즘] 20일차 (Ax+By=C) #백준21568번
07-4 확장 유클리드 호제법 📌 문제 045) Ax+By=C 시간 제한 1초, 골드 I, 백준 21568번 > A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 -1,000,000,00
21.[알고리즘] 21일차 (그래프의 표현)
## 08-1 그래프의 표현 - 그래프를 구현하는 3가지 방법에 대해 알아보자. **[2차원 리스트 생성]** - 0으로 초기화한 행(row) 개수 3, 열(column) 개수 4인 2차원 리스트를 생성하는 방법 - 리스트 객체 생성 방법 **추천** ``` A =
22.[알고리즘] 22일차 (특정 거리의 도시 찾기) #백준18352번
시간 제한 2초, 실버 II, 백준 18352번어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출
23.[알고리즘] 23일차 (효율적으로 해킹하기) #백준1325번
📌 문제 047) 효율적으로 해킹하기 시간 제한 5초, 실버 I, 백준 1325번 > 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴
24.[알고리즘] 24일차 (이분 그래프 판별하기) #백준1707번
시간 제한 2초, 골드 IV, 백준 1707번그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이
25.[알고리즘] 25일차 (물의 양 구하기) #백준2251번
시간 제한 1초, 골드 V, 백준 2251번각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수
26.[알고리즘] 26일차 (집합 표현하기) #백준1717번
## 08-2 유니온 파인드 - 유니온 파인드는 일반적으로 여러 노드가 있을 때, 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다. - union(a, b) =
27.[알고리즘] 27일차 (여행 계획 짜기) #백준1976번
📌 문제 051) 여행 계획 짜기 시간 제한 2초, 골드 IV, 백준 1976번 > 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가
28.[알고리즘] 28일차 (거짓말쟁이가 되긴 싫어) #백준1043번
### 📌 문제 052) 거짓말쟁이가 되긴 싫어 시간 제한 2초, 골드 IV, 백준 1043번 > 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로
29.[알고리즘] 29일차 (줄 세우기) #백준2252번
## 08-3 위상 정렬 - 위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. - 기능: 노드 간의 순서를 결정 - 특징: 사이클이 없어야 함 - 시간 복잡도(노드 수: V, 에지 수: E): O(V + E) - 위상 정렬에서는 항상 유일한 값
30.[알고리즘] 30일차 (게임 개발하기) #백준2252번
시간 제한 2초, 골드 III, 백준 1516번숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다.게임 플레이에 들어가는 시간은 상황에
31.[알고리즘] 31일차 (임계 경로 구하기) #백준1948번
시간 제한 2초, 플래티넘, 백준 1948번월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다.이 지도를
32.[알고리즘] 32일차 (최단 경로 구하기) #백준1753번
다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.기능: 출발 노드와 모든 노드 간 최단 거리 탐색특징: 에지는 모두 양수시간 복잡도(노드 수: V, 에지 수: E): O(ElogV)특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때, 다
33.[알고리즘] 33일차 (최소 비용 구하기) #백준1916번
시간 제한 0.5초, 골드 V, 백준 1916번N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드
34.[알고리즘] 34일차 (K번째 최단 경로 찾기) #백준1854번
시간 제한 2초, 플래티넘, 백준 1854번봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리
35.[알고리즘] 35일차 (타임머신으로 빨리 가기) #백준11657번
시간 제한 1초, 골드 IV, 백준 11657번N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간