서로소 집합 자료구조(Disjoint Sets) 개념 : 공통 원소가 없는 두 집합인 '서로소 부분 집합'들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 트리 자료구조를 이용하여 집합 표현 union-find 자료구조로도 불림 루트 노드를 찾기 위해서는 재귀적으로 부모 노드를 거슬러 올라가야 함 연산 1. UNION (합집합 연산) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 간접적으로 연결되어 이동할 수 있는 노드들에 대해서도, 같은 집합에 있는 것으로 이해할 수 있다. 2. FIND (찾기 연산) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 계산 알고리즘 개념 : 서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘

힙 (Heap) 개념 : 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) (** 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리) 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 (** 우선순위 큐 : 우선순위가 갖아 높은 데이터를 가장 먼저 삭제하는 자료구조) 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫번쨰 원소를 기준으로 우선순위 설정 힙의 구조 |구분|최대 힙 (Max Heap)|최소 힙(Min Heap)| |:--:|:---:|:---:| |개념|최댓값을 구하기 위한 구조|최솟값을 구하기 위한 구조| |조건|각 노드의 값은 해당 노드의 자식 노드 값보다 크거나 같다|각 노드의 값은 해당 노드의 자식 노드 값보다 작거나 같다|

순차탐색 (Sequential Search) 개념 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 알고리즘 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 데이터가 아무리 많아도 시간만 충분하면 항상 원하는 데이터를 찾을 수 있음 동작원리 소스코드 5 Apple Banana Melon Apple Cherry Orange 3 시간복잡도 : $O(N)$ 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다. 따라서 데이터의 개수가 $N$개 일 때 최대 $N$번의 비교 연산이 필요하므로 최악의 경우 시간복잡도는 $O(N)$이다.

구현 (Implementation) 개념 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 사실, 어떤 문제를 풀든 간에 소스코드 작성은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 완전탐색과 시뮬레이션 문제 또한 '구현' 문제 유형이라고 할 수 있다. 1. 완전 탐색 : 모든 경우의 수를 주저없이 다 계산하는 해결 방법 2. 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 해결 방법 문제풀이 Tip 데이터 개수에 따른 메모리 사용량 체크 테스트 환경이 Pypy3도 지원한다면, Pypy3 이용하기 (실행 속도 빠름) 기본예제 예제 1. 상하좌우 > 여행가 A는 NxN 크기의 정사각형 공간 위에 서 있다. 이 공간은 1x1 크기의 정사각형으로 나누어져 있다. 여행가 A는 상, 하,

🔎 문제 당신은 인사팀 직원으로, 각 직원의 근태를 확인하고자 한다. 당신의 회사는 자율출퇴근제를 실시하기 때문에 각 직원이 정확히 몇 시에 출근하는 것은 중요하지 않고, 총 근로 시간이 몇 분인지가 중요하다. 총 근로 시간이 법정근로시간을 초과하지 않아야 하면서, 회사와 직원 사이에 계약한 시간 이상이어야 하기 때문이다. 직원이 하루 동안 근무한 시간은 출근 시각과 퇴근 시각 사이의 시간으로 정의한다. 이 문제에서는 식사 시간 등 근무 외 시간을 근무 시간에서 제외하지 않음에 유의하라. 월요일부터 금요일까지 휴가를 쓰지 않은 직원이 매 요일 언제 출근하고 언제 퇴근했는지가 주어질 때, 이 직원이 5일 동안 총 몇 분을 근무했는지를 구하는 프로그램을 작성하라. 제약조건 직원은 밤을 새서 일하지 않았다. 즉, 출근 시각과 퇴근 시각은 00:00 이후, 24:00 이전에 이루어졌다. 출퇴근 시각은 HH:MM과 같은 형식으로 주어진다. HH는 00, 01, 02,

🔎 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되

🔎 문제 N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 출력 첫째 줄에 지나야 하는 최소의 칸 수를

🔎 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. 예제 ![](https://velog.velcdn.com/images/ybseo/post/637719ac-d684-498f-8fe5-85a7b64

탐색 (Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 '탐색'을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로, 코딩테스트에서도 자주 출제되는 유형인 DFS와 BFS에 대해 알아보고자 한다. 일단, DFS와 BFS를 이해하기 위해서는 기본 자료구조인 '스택'과 '큐' 그리고 '재귀함수'에 대해 알고 있어야 한다. 스택과 큐, 재귀함수에 대한 설명은 아래 링크에 따로 정리해두었으니 참고하도록 하자. 자료구조 - 스택 (Stack) 자료구조 - 큐 (Queue) [Python - 재귀함수 (Recursive function)] 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것 ✓ 노드 (Node) = 정점(

🔎 문제 설명 완호가 관리하는 어떤 데이터베이스의 한 테이블은 모두 정수 타입인 컬럼들로 이루어져 있습니다. 테이블은 2차원 행렬로 표현할 수 있으며 열은 컬럼을 나타내고, 행은 튜플을 나타냅니다. 첫 번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장됩니다. 완호는 이 테이블에 대한 해시 함수를 다음과 같이 정의하였습니다. 해시 함수는 col, rowbegin, rowend을 입력으로 받습니다. 테이블의 튜플을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다. 정렬된 데이터에서 S_i를 i 번째 행의 튜플에 대해 각 컬럼의 값을 i 로 나눈 나머지들의 합으로 정의합니다. rowbegin ≤ i ≤ rowend 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환합니다. 테이블의

🔎 문제설명 1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다. 이전에 등장했던 단어는 사용할 수 없습니다. 한 글자인 단어는 인정되지 않습니다. 다음은 3명이 끝말잇기를 하는 상황을 나타냅니다. tank → kick → know → wheel → land → dream → mother → robot → tank 위 끝말잇기는 다음과 같이 진행됩니다. 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다. 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다. 3번 사람이 자신의 첫 번째 차례에 know를 말합니다. 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다. (계속 진행) 끝말잇기를 계

🔎 문제설명 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다. 예를 들어, 문자열 S = baabaa 라면 b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다. ✅ 제한사항 문자열의 길이 : 1,000,000이하의 자연수 문자열은 모두 소문자로 이루어져 있습니다. > 💡 풀이 아이디어 1) stack이 비어있는 경우 : 현재 원소 x는 무조건

🔎 문제설명 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. ✅ 제한사항 n은 2 이상 100,000 이하인 자연수입니다. > 💡 풀이 아이디어 ** 우선 피보나치 수열은 DP를 사용하는 대표적인 문제이므로 Bottom-up DP를 사용하여 문제를 해결했다. 1) 제한사항에서 `n은 2이상 100,000이하인 자연

들어가기에 앞서, 🤔 컴퓨터를 활용해도 해결하기 어려운 문제? 컴퓨터를 활용해도 해결하기 어려운 문제에는 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 있다. 다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 우리는 이 방법을 '다이나믹 프로그래밍' 또는 '동적계획법'이라고 표현한다. 🤔 동적계획법의 '다이나믹' vs 동적할당의 '다이나믹' 프로그래밍에서 '다이나믹'은 프로그램이 실행되는 도중에라는 의미이다. 따라서 자료구조에서 동적할당(Dynamic Allocation)은, 프로그램이 실행되는 도중에 프로그램 실행에 필요한 메모리를 할당하는 기법을 뜻한다. 🤔 피보나치 수열 : 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열 피보나치 수열은 간단한 점화식을 사용하여 표

🔎 문제설명 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다. 1 + 2 + 3 + 4 + 5 = 15 4 + 5 + 6 = 15 7 + 8 = 15 15 = 15 자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요. ✅ 제한사항 n은 10,000 이하의 자연수 입니다. > 💡 풀이 아이디어 1) 반복문1 : i를 1부터 n까지 순회한다. 2) 반복문2 : j를 i부터 n까지 순회하면서, 연속된 자연수들의 합(s)에 i부터 1씩 큰 수를 차례로 더한다. 3) 만약 연속된 자연수들의 합(s)이 n이 되면 방법의 개수(`

🔎 문제 설명 0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다. x의 모든 0을 제거합니다. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다. 예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다. 0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요. ✅ 제한사항 s의 길이는 1 이상 150,000 이하입니다. s에는 '1'이 최소 하나 이상 포함되어 있습니다. > 💡 풀이 아이디어 1) 제거할 '0'의 개수(zero)를 세고 '0' 제거

🔎 문제 설명 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다. 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다. 예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다. 자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요. ✅ 제한사항 n은 1,000,000 이하의 자연수 입니다. > 💡 풀이 아이디어 1) 입력받은 수 num을 2진수 변환한 문자열 중 1의 개수 세기 2) num에 1씩 더해가면서 해당 수를 2진수로 변환했을 때 1의 개수가 다르면 +1 후 반복문 처음으로 돌아가기 3) 1의 개수가 같으면

파이썬 내장함수 zip()에 대해 알아보도록 하자. zip() 여러개의 순회 가능한 객체(iterable)를 인자로 받고, 각 객체가 담고있는 원소를 튜플(tuple)의 형태로 차례대로 접근할 수 있는 반복작업이 가능한 함수 * iterable 객체 : * 반복이 가능한 객체 ex) list, dict, set, str, bytes, tuple, range ** iterator 객체 : 값을 차례대로 꺼낼 수 있는 객체 iterable한 객체를 내장함수 또는 iterable 객체의 메소드로 객체를 생성할 수 있다. [1, 'a'] [2, 'b'] 위 코드를 zip() 함수를 사용하지 않고 인덱스로 각각을 접근해서 사용하면 다음과 같이 쓸 수 있다. [1, 'a'] [2, 'b'] zip() 함수 특징 zip() 함수는 가변인자를 받기 때문에 2개 이상의 인자를 받을 수

🔎 문제 설명 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.) 예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면 A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5) A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21) A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29) 즉, 이 경우가 최소가 되

1. 이분검색 > 임의의 N개의 숫자가 입력으로 주어진다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째 있는지 구하는 프로그램을 작성하시오. 단, 중복값은 존재하지 않는다. 8 32 23 87 65 12 57 32 99 81 TypeError: 'NoneType' object is not subscriptable None 타입의 값에 인덱스로 접근하려해서 발생했다. 틀린이유 : 원인은 .sort() 함수 때문이었다.array.sort()는 array라는 리스트 자체를 정렬 변경하기 때문에 사실상 반환값이 None 이다. 반면에 sorted(array)는 array 리스트를 정렬한 새로운 리스트를 생성해서 반환해준다. 따라서 array.sort()로 하던지 아니면 array = sorted(array) 로 해야한다. .sort()와 `sorted(a