Archive

집합 순서와 중복이 없는 원소들을 갖는 자료구조  상호배타적 집합 : 교집합이 없는 집합 관계그래프 알고리즘에서 많이 활용된다.활용 분야이미지 분할 / 도로 네트워크 구성 / 최소 신장 트리 알고리즘 구현 / 게임 개발 / 클러스터링 작업 앞으로 글의 내용에서 집합을 상호배타적 집합이라 가정한다. 집합의 연산집합의 표현 방법 : 배열을 활용한 트리로 구현집합의 대표적인 연산합치기 (유니온)탐색 (파인드)배열을 활용하여 트리로 집합 표현각 집합 에는 대표 원소가 있어야 한다.집합의 원소 중 집합을 대표하는 역할집합의 형태를 트리로 표현할 것이므로 대표 원소를 루트 노드라 가정한다.하나의 배열로 상호배타적 관계를 가지는 집합을 모두 표현한다.배열의 인덱스는 자신을, 배열값은 부모 노드를 의미한다.disjoi..

큐뜻 줄을 서다자료구조 먼저 들어간 데이터가 먼저 나오는 자료구조 (FIFO, 선입선출)ADT연산 isFull 큐에 들어 있는 데이터가 maxsize인지 확인isEmpty 큐에 들어있는 데이터가 하나도 없는지 확인해 boolean 값을 반환front === rear인 경우push 큐에 데이터를 푸시pop 큐에서 처음에 푸시한 데이터를 팝하고, 그 데이터를 반환상태front 큐에서 가장 처음에 팝한 위치를 기록rear 큐에서 최근에 푸시한 데이터의 위치를 기록data[maxsize] 큐의 데이터 배열 구현1. shift 메서드 이용const queue = [];queue.push(1); // 큐에 데이터 추가let firstItem = queue.shift(); // 큐의 맨 앞 데이터 제거2. 배열 이용..

1. 스택 개념스택 : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조LIFO (Last In First Out) : 먼저 들어간 것이 마지막에 나오는 규칙push : 스택에 삽입하는 연산pop : 스택에서 꺼내는 연산최근에 삽입한 데이터를 대상으로 연산해야 한다면 스택을 떠올리는 것이 좋음 2. 스택의 정의스택의 ADTADT란 ?Abstract Data Type의 약자추상 자료형 (인터페이스만 있고 실제로 구현은 되지 않는 자료형)일종의 자료형의 설계도정의해야 할 연산 : push , pop ,  isFull , isEmpty 정의해야 할 상태 : top , data[maxsize]  데이터가 없으면 top = -1 스택 세부 동작1. push(3) 호출2. isFull()을 수행하여 data..

문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... n을 d(n)의 생성자라..

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 내 풀이 n = int(input()) fa = set(list(map(int, input().split(" ")))) m = int(inp..

문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM 앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2인 경우를 생각해보자. [1,2,3,4,5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 3 + 1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람들이 돈을 뽑을 때까지 기다려야 하기 때문에, 3 + 1 + 4 = 8분이 필요하게 된다. ..

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정ㄴ 대표적인 탐색 알고리즘: DFS & BFS자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조ㄴ 스택과 큐 : 자료구조의 기초 개념ㅤ> 삽입 (Push) & 삭제 (Pop)을 핵심으로 하여 구성됨ㅤ> 오버플로 (특정한 자료구조가 수요할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생) & 언더플로 (특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행)도 고민해야 함 스택스택 = 박스 쌓기 = 아래에서부터 위로 쌓임 = 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야 함 = 선입후출 구조 (First In Last Out) = 후입선출 구조 (Last in First O..

문제 유진수는 어떤 수를 10진수로 표현한 뒤 그 수를 두 부분으로 나눴을 때, 앞부분 자리수의 곱과 뒷부분 자리수의 곱이 같을 때를 말한다. 예를 들어, 1221은 유진수이다. 12와 21로 나눴을 때, 앞부분 자리수의 곱 1*2는 뒷부분 자리수의 곱 2*1과 같기 때문이다. 1236도 마찬가지로 유진수이다. 하지만, 1234는 아니다. 수를 나눌 때 항상 연속된 자리수를 나눠야하고, 각 부분에 적어도 한자리는 있어야 한다. 예를 들어, 12345는 총 4가지 방법으로 나눌 수 있다. 1-2345, 12-345, 123-45, 1234-5 어떤 수 N이 주어질 때, 이 수가 유진수인지 아닌지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수 N이 주어진다. 이 수는 2,147,483,647보다 작거나 ..

문제 오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. 그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다. 그래서 오민식 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다. 예를 들어 학생 수가 5명일 때의 표를 살펴보자. 위 경우에 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며, 2번 학생과는 4학년 때 같은 반이었음을 알 수 있다. 그러므로 이 학급에서 4번 학생과 한번이라도 같은 반..

문제 동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다. 이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다. 하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자. 입력 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. 출력 첫 줄에 구간에 속하는 숫자의 합을 출력한다. 내 풀이 n, m = map(int, input().split(" ")) k = 1 ..