굴굴이의 삶

1. 정의데크(Deque) : Double-ended-queue의 줄임말스택은 나중에 들어온 것이 먼저 나가는 LIFO, 큐는 먼저 들어온 것이 먼저 나가는 FIFO의 형태.데크는 양쪽 모두에서 삽입, 삭제 연산을 할 수 있음. 2. 특징- 양쪽 끝에서 빠른 연산 : deque는 양쪽 끝에서 O(1) 시간 복잡도로 삽입 및 삭제가 가능함. 반면, 리스트는 왼쪽 끝에서의 삽입 및 삭제가 O(n) 시간이 걸릴 수 있음.- 선형 자료구조 : 데이터를 순차적으로 저장함. 2. 데크 구현하기맨 앞에서 삽입과 삭제 연산이 일어나야 하고, 맨 뒤에서도 삽입과 삭제 연산이 일어나야 하므로 스택, 큐는 삽입과 삭제 연산을 한 번씩 구현하지만,데크에서는 삽입과 삭제 연산을 각각 두 번 구현해야 함.deque의 주요 메서드..

문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. [풀이]N과 M (1) 에서는 순열이었고, 이 문제는 조합이다.그래서 (2)에서는 N과 M (1) 코드에서 오름차순 후 같은 것을 제거하는 과정을 거쳐야 한다. ex) N과 M (1)입력이 아래와 같을 때4 2 출력으로 이렇게 나오게 된다.1 2..

백트래킹에 대해 이번 기회에 제대로 정리해보겠다.백트래킹이란?백트래킹은 모든 경우의 수를 고려하는 알고리즘을 의미.트리 형태의 상태공간이 있을 때, DFS와 같은 완전탐색 알고리즘을 사용하여 모든 지점을 탐색하게 됨.DFS는 현재 지점에서 방문할 곳이 있으면 재귀를 호출하여 계속 이동하는 특징이 있음.하지만, DFS는 모든 곳을 방문하기 때문에 비효율적인 면이 있음. 백트래킹은 DFS를 사용하여 만약 조건에 맞지 않으면 중단하고 이전으로 돌아가서 다시 확인하는 것을반복하고, 원하는 조건을 효율적으로 찾는 알고리즘.백트래킹과 DFS의 차이점?DFS는 연결되어있는 모든 노드들을 깊이 우선순위에 따라 탐색하는 알고리즘.백트래킹은 DFS를 사용하여 어떤 노드의 유망성을 점검한 후, 유망하지 않으면 가지치기하는특..

우선순위 큐의 정의우선순위 큐는 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조.우선순위 큐는 힙(Heap)을 이용하는 게 제일 효율적.(큐는 먼저 들어오는 데이터가 먼저 나가는 선입선출 (FIFO) 형식의 자료구조) Heap의 정의완전이진트리 형태의 자료구조완전이진트리 : 마지막 레벨을 제외한 모든 레벨이 모두 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있어야 함. Heap의 종류최대 힙(Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 큰 구조최소 힙(Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작은 구조 힙 자료 구조heapq 모듈은 이진트리 기반의 최소 힙 자료구조 제공함.ex) 힙에 원소 추가 및 삭제from heapq import..

문제준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 ..

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

문제대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.1, 1, 2, 3, 5, 8, ... 지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.타일의 개수 N(1 ≤ N ≤ 80)이 주어졌을..

문제좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtpzyo 같은 비밀번호를 무작위로 부여해 주기도 하지만, 사용자들은 이를 외우는데 어려움을 느끼고 심지어는 포스트잇에 적어 컴퓨터에 붙여놓는다. 가장 이상적인 해결법은 '발음이 가능한' 패스워드를 만드는 것으로 적당히 외우기 쉬우면서도 안전하게 계정을 지킬 수 있다. 회사 FnordCom은 그런 패스워드 생성기를 만들려고 계획중이다. 당신은 그 회사 품질 관리 부서의 직원으로 생성기를 테스트해보고 생성되는 패스워드의 품질을 평가하여야 한다. 높은 품질을 가진 비밀번호의 조건은 다음과 같다.모음(a,e,i,o,u) ..

문제다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다.다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다.현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마음을 모두 읽었다.다솜이는 기호 1번이다. 다솜이는 사람들의 마음을 읽어서 자신을 찍지 않으려는 사람을 돈으로 매수해서 국회의원에 당선이 되게 하려고 한다. 다른 모든 사람의 득표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선된다.예를 들어서, 마음을 읽은 결과 기호 1번이 5표, 기호 2번이 7표, 기호 3번이 7..

두 자연수의 최대 공약수를 효율적으로 찾는 알고리즘으로유클리드 호제법이 있다. 1. 나머지 연산을 사용한 반복 두 수 a, b (a > b)에 대해서, a를 b로 나누어 나머지를 구한다.나머지를 r이라 할 때,a와 b의 최대공약수는 b와 r의 최대 공약수와 같다. 2. 반복 과정 b와 r에 대해 같은 과정을 반복한다. b를 r로 나눈 나머지를 구하고,이를 새로운 r로 사용한다. 나머지가 0이 될 때까지 반복한다. 3. 최대 공약수 결정 나머지가 0이 되면, 나누는 수가 a와 b의 최대 공약수가 된다.나머지가 0이 되었다는 것은 바로 전 단계의 나누는 수가 나누어지는 수의 약수라는 것을 의미하고 이는 두 수의 공통된 약수 중 가장 큰 값이 된다. ex) 48과 2048 % 20 = 8r = 8 이라고 하면..