문제 링크https://www.acmicpc.net/problem/1074문제입력첫째 줄에 정수 N, r, c가 주어진다.출력r행 c열을 몇 번째로 방문했는지 출력한다.제한1 ≤ N ≤ 15 0 ≤ r, c 풀이재귀함수의 문제로 먼저 규칙을 찾을 필요가 있는데 문제는 Z의 형태로 다음과 같은 규칙을 가진다.먼저 입력값 N에 대하여 배열의 크기는 2^N * 2^N 의 배열을 가지게 되는데r과 c는 배열의 중간을 기준으로 해당 배열의 어느 부분에 위치하는지 알 수 있다.이때 배열의 중간은 2^N //2 이므로 편의상 MID로 표시한다. ( MID = 2^N // 2 )r 0Z(N-1,r,c)r = MID1Z(N-1,r,c-MID)r >= MID and c 2Z(N-1,r-MID,c)r >= MID and c..

I . Deque(데크)1. Deque의 개념과 구조deque 는 Double-Ended-Queue의 줄임말로, 양방향에서 데이터를 처리할 수 있는 Queue형 자료구조이다.2. Deque의 메서드 정리from collections import dequedeq = deque(['a','b','c'])arr = ['1','2','3']deq.append('d') # deque(['a', 'b', 'c', 'd'])deq.appendleft('e') # deque(['e', 'a', 'b', 'c', 'd'])deq.pop() # deque(['e', 'a', 'b', 'c'])deq.popleft() # deque(['a', 'b', 'c'])deq.extend(arr) # deque(['a', 'b', ..

자료구조란?자료구조(Data Structure)자료 구조는 데이터를 효율적으로 저장하고 관리하는 방법을 말한다. 데이터를 표현하고 조작하는 데 필요한 것으로써 삽입 · 수정 · 삭제 · 검색 · 정렬 · 병합 및 순회와 같은 기본적인 연산을 지원한다.알고리즘(Algorithms)알고리즘은 특정 문제를 해결하기 위한 명확하고 구체적인 단계들의 집합이다. 컴퓨터 과학에서 알고리즘은 입력 데이터를 받아 원하는 결과를 출력하는 과정이며, 효율적인 알고리즘은 실행 시간과 자원 사용을 최소화한다.자료구조와 알고리즘의 관계자료구조는 메모리 공간을 효율적으로 사용하기 위해, 뿐만 아니라 실행 시간의 효율성을 위해 선택되어진다.그리고 자료구조가 선택되면 적용할 알고리즘도 같이 정해지므로 자료구조가 효율적인 알고리즘을 사..

문제 링크https://www.acmicpc.net/problem/1021문제지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려..

문제 링크https://www.acmicpc.net/problem/9012문제괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는..

문제 링크https://www.acmicpc.net/problem/17298문제크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수..

여러 문제에서 뒤집는 문제가 나오는데 어떻게 구현하는 지 공부해보았다. reverse1. reverse는 List 타입에서 제공하는 함수(메서드) 로 다른 객체에서는 사용할 수 없다.l = ['a', 'b', 'c']t = ('a', 'b', 'c')d = {'a': 1, 'b': 2, 'c': 3}s = 'abc'l.reverse() # list의 순서를 뒤집어줌t.reverse() # AttributeError: 'tuple' object has no attribute 'reverse'd.reverse() # AttributeError: 'dict' object has no attribute 'reverse's.reverse() # AttributeError: 'str' object has n..

문제 링크https://www.acmicpc.net/problem/5622문제상근이의 할머니는 아래 그림과 같이 오래된 다이얼 전화기를 사용한다.전화를 걸고 싶은 번호가 있다면, 숫자를 하나를 누른 다음에 금속 핀이 있는 곳 까지 시계방향으로 돌려야 한다. 숫자를 하나 누르면 다이얼이 처음 위치로 돌아가고, 다음 숫자를 누르려면 다이얼을 처음 위치에서 다시 돌려야 한다. 숫자 1을 걸려면 총 2초가 필요하다. 1보다 큰 수를 거는데 걸리는 시간은 이보다 더 걸리며, 한 칸 옆에 있는 숫자를 걸기 위해선 1초씩 더 걸린다. 상근이의 할머니는 전화 번호를 각 숫자에 해당하는 문자로 외운다. 즉, 어떤 단어를 걸 때, 각 알파벳에 해당하는 숫자를 걸면 된다. 예를 들어, UNUCIC는 868242와 같다. 할..

문제 링크https://www.acmicpc.net/problem/2563문제가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.입력첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 ..

문제 링크https://www.acmicpc.net/problem/9020문제1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거..