![]()
분류: bfs, 3차원 / 문제 문제 링크 같은 내용 2차원 문제: [백준 - 7576] 토마토 - C++, Python 풀이 문제 설명 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼..
![]()
분류: deque, 파싱, 문자열 / 문제 문제 링크 문제 설명 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 ..
![]()
분류: DP / 문제 문제 링크 문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 ..
![]()
분류: DP, Memoization, 재귀, 탑다운, 바텀업 / 문제 문제 링크 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 - 하향식 방법(top-down) + DP(Memoization) import sys # n에서 1까지 가는데 필요한 연산의 수 def steps(dp, n): if dp[n] ==..
![]()
분류: 비트마스킹, 집합 / 문제 문제 링크 문제 설명 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1, 2, ..., 20} 으로 바꾼다. empty: S를 공집합으로 바꾼다. 입력 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 ..
![]()
제가 블로그에 쓴 자료구조와 알고리즘 글들을 모아 정리했습니다. 자료 구조 연결 리스트(linked list) - 단일 연결 리스트, Java 구현 스택(stack) - 단일 연결 리스트와 배열을 이용한 스택, Java 구현 큐(Queue) - 단일 연결 리스트를 이용한 Deque, Java 구현 알고리즘 시간 복잡도와 점근적 표기법 재귀 알고리즘의 시간 복잡도 계산 선택 정렬(Selection Sort) - C++, Java, Python 구현 삽입 정렬(Insertion Sort) - C++, Java, Python 구현 버블 정렬(Bubble Sort) - C++, Java, Python 구현 병합 정렬(Merge Sort) - C++, Java, Python 구현 퀵 정렬(Quick Sort) -..
![]()
스택과 비교해 보며 큐 자료 구조에 대해 알아봅시다. 이번 글에서는 java로 `양방향 큐(deque)`를 `이중 연결 리스트(doubly linked list)`로 구현합니다. 자료구조, 알고리즘 시리즈 모아보기 큐 `큐(queue)`는 이름 그대로 줄 서는 것과 같습니다.(줄 서 있는 것을 미국에서는 line이라고 하지만 영국에서는 queue라고 합니다.) 줄을 설 때를 생각해 보면 먼저 온 사람이 먼저 원하는 것을 얻습니다. 늦게 온 사람은 늦게 얻죠. 이런 구조를 `FIFO(First In First Out)`이라 합니다. - 연산 큐 또한 스택과 마찬가지로 `추상 자료 유형(Abstract Data Type)`으로 연산(행위)으로 정의됩니다. enqueue: 새로운 요소를 자료 구조에 추가 de..
![]()
스택 자료구조에 대해 알아보고 java로 구현해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 스택 `스택(stack)`은 이름 그대로 자료를 쌓아 놨다고 생각하는 `추상 자료 유형(Abstract Data Type)`입니다. 흔히 프링글스, 팬케이크로 예시를 듭니다. 가장 마지막에 프링글스 통에 넣은 프링글스 칩, 가장 마지막에 쌓은 팬케이크는 바로 먹을 수 있지만 가장 예전에 넣은(처음 넣은) 것은 꺼내기 힘듭니다. 스택은 위 예시와 같이 마지막에 넣은 것이 처음으로 나오는 `LIFO(Last In First Out)`구조로 최신 순으로 자료에 접근이 가능합니다. - 연산 스택은 추상 자료 유형으로 다음과 같은 연산(행위)으로 정의됩니다. 스택은 크게 push와 pop이라는 두 개의 연산으로 정의됩니다..
![]()
연결 리스트의 가장 기본이 되는 단일 연결 리스트로 연결 리스트를 이해해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 연결 리스트 `연결 리스트(linked list)`는 데이터와 다음 데이터의 위치를 함께 저장하여 데이터들을 체인처럼 연결하는 자료 구조입니다. 여기서 저장되는 자료의 단위(데이터와 다음 자료의 위치를 묶은 구조체)를 `노드(node)`라고 부릅니다. 다시 말하면 연결 리스트는 데이터와 다음 노드의 참조값을 갖는 노드들로 연결된 자료 구조입니다. 연결 리스트는 연결되는 방법에 따라 `단일 연결 리스트(singly linked list)`, `이중 연결 리스트(doubly linked list)`, `다중 연결 리스트(multi-linked list)`, `원형 연결 리스트(circular..
![]()
분류: 재귀, 좌표계 / 문제 문제 링크 문제 설명 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력 r행 c열을 몇 번째로 방문했는지 출력한다. 풀이 - Python import sys readline = sys.stdin.readline def..
![]()
개인 프로젝트를 진행하던 도중 데이터베이스의 쿼리 실행 시간을 비교할 필요가 생겼습니다. 쿼리 실행 시간 측정 기능을 제공하는 패키지가 당연히 있을 줄 알았지만 찾지 못했고 저와 같은 기능을 찾는 사람들이 많다는 것을 알게 되어 패키지로 제작하게 되었습니다. 패키지 제작 이유부터 중간에 했던 시행착오들을 포함한 패키지 제작과정을 기록해 볼까 합니다. ❗️이 글은 2022년 2월에 작성된 글을 블로그를 리뉴얼하며 다시 작성한 글입니다. 노드에서 MySQL 쿼리 실행 속도 측정 MySQL의 쿼리 실행속도를 노드에서 측정하는 법을 검색해 보면 아래와 같은 방법이 나옵니다. // 시작시간 var start = new Date().getTime(); // 쿼리 실행 connection.query(query, fu..
![]()
최악의 경우 $\Theta(n^2)$의 시간복잡도를 갖지만 $\Omicron(n\log n)$ 평균적으로 가장 좋은 성능을 보이고 구현이 쉬워 현업에서 가장 많이 쓰인다고 알려진 퀵 정렬을 알아보고 자바와 파이썬으로 구현해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 퀵 정렬 `퀵 정렬(quick sort)`은 병합 정렬 알고리즘과 비슷하게 입력을 나누어 각각에 대해 재귀적으로 정렬하는 알고리즘입니다. 퀵 정렬과 병합 정렬의 차이점은 크게 두 가지가 있습니다. 퀵 정렬은 병합 정렬과 달리 합치는 과정이 없고 입력을 항상 반씩 균등하게 나누지 않습니다. 퀵 정렬은 기준값정하고 기준값보다 큰 값들과 작은 값들로 입력을 분할합니다. 이때 기준값을 `피벗(pivot)`이라 합니다. - Pseudocode qui..
