후회가 없도록

문제 출처: https://www.acmicpc.net/problem/2667 1. 결과 1) BFS 이용: 메모리 32108KB, 시간 96ms 2) DFS 이용: 메모리 29304KB, 시간 76ms 2. 풀이 이 문제는 전형적인 그래프 탐색 문제이다. 그래프 탐색은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 두 가지가 있는데, 비교적 간단한 문제는 두 방법 모두 가능하다. 여기서 잠깐 둘의 차이를 짚고 가면, BFS는 최적, 최단과 같은 요소를 구할 때 유용하고, DFS는 특정 경로나 요소에 대해 끝까지 경우를 끝까지 탐색해볼 때 유용하다. 그런 부분에서 이 문제는 DFS가 더 적합하다고 볼 수 있다. 특정 영역에 대해 끝까지 탐색한 넓이를 구하는 것이기 때문이다. 위의 결과에서도 알 수 ..

문제 출처: https://www.acmicpc.net/problem/5430 1. 결과 메모리 46428KB, 시간 336ms 2. 풀이 이 문제는 우선 입력과 출력 예시를 통해 확인할 수 있겠지만, 예시처럼 입력을 받아서 원하는 형태의 숫자로 변환하는 것, 출력을 원하는 형식대로 출력하는 것이 생각보다 고민이 됐다. 그래서 아래 코드처럼 입력과 출력이 조금은 더 길다. 본격적인 문제의 아이디어는 결국 뒤집든 안 뒤집든 한쪽 끝에서 숫자를 제거한다는 점에서 떠올렸다. 만약 스택의 형태로 풀었다면, D일 때는 [1:]로 슬라이싱을, R일 때는 reverse 정렬을 하게 되는데, 이는 슬라이싱을 할 때마다 남은 길이만큼 연산(한 칸씩 앞으로 당기는 것)이 발생하고, R이 있을 때마다 정렬이 발생한다는 뜻이..

SQL에도 데이터나 행의 그룹의 값을 계산하거나, 조작하는 함수가 존재하는데, 이 글에는 아주 기초적인 SQL 내장 함수를 코드 작성 방법만 간단하게 정리했다. COUNT 검색한 결과의 데이터 개수를 가져오는 내장 함수 SELECT COUNT(COL) FROM myData; -- 특정 컬럼 COL의 레코드 개수 SELECT COUNT(*) FROM myData; -- 모든 컬럼의 데이터 개수. 즉 데이터의 전체 크기를 파악 SUM 지정한 컬럼의 값을 모두 더하여 총합을 구하는 내장 함수 SELECT SUM(COL) FROM myData; -- 컬럼 COL에 대한 합계 AVG 지정한 컬럼의 값의 평균값을 구하는 내장 함수 SELECT AVG(COL1), AVG(COL2), AVG(COL3) FROM myD..

DML이란 Data Manipulation Language(데이터 조작어)로써, 말 그대로 데이터를 조작(검색, 삽입, 수정, 삭제 등)하는 데 사용되는 명령어를 의미한다. LIKE - 유사한 데이터 검색 특정 문자가 포함된 문자열을 찾고 싶을 때 사용하는 명령어이다. 대소문자를 우선 순위로 구분하는데, 예를 들어 AB, Ab, aB, ab가 있는 테이블에서 ab로 검색을 한다면 ab, aB, Ab, AB 순으로 정렬되어 검색된다. LIKE는 주로 WHERE과 함께 사용되며, 아래 예시와 같이 사용되는 퍼센트 기호(%)는 '와일드 카드'라고 부른다. SELECT (컬럼명) FROM (테이블명) WHERE (컬럼명) LIKE (찾으려는 레코드의 일부 또는 전체); -- 와일드 카드(%) 이용 예시 WHER..

1. 테이블(Table) 데이터베이스에서 테이블이란 컬럼(Column)과 레코드(Record)로 구성된 표를 말하는데, 사실상 우리가 평소에도 알고 있는 표를 떠올리면 된다. 여기서 컬럼은 각 자료의 영역, 속성을 의미하는 열, 레코드는 각 열에 따른 데이터 값을 지닌 행이다. 데이터베이스에서 테이블은 각각의 고유한 이름으로 구분되어야 하며, 컬럼과 레코드도 각 단어의 의미를 알고 구분해야 한다. 2. 데이터 검색 및 조회하기 주어진 테이블에서 데이터를 검색하고 가져올 때, 출력할 때 사용하는 대표적인 명령어는 아래와 같다. SQL은 한 문장의 명령어 끝에 세미콜론(;)을 작성함으로써 다른 명령어와 구분을 해야 하고, 세미콜론 없이 엔터로만 구분되어 있다면, 하나의 명령어로 인식한다. 또, 명령어 자체는..

탄생 이후 40년이 지나도 건재한 데이터베이스 조작 언어 1. 기원 1) 누가 도널드 D. 챔벌린, 레이먼드 F. 보이스 2) 언제 1976년 3) 어디서 IBM San Jose 연구소 4) 어떻게 관계형 모델과 그것의 튜플적 해석이라는 이론적 기초로부터 파생되어 설계되었다. 5) 왜 SQL의 시작인 SEQUEL은 IBM의 준 관계형 데이터베이스 관리 시스템 R에 저장된 데이터를 조작하고 수신하기 위해 고안되었다. 입력 릴레이션(테이블)으로부터 원하는 출력 릴레이션을 사상(mapping)시키는 언어로써, 1973년에 SQUARE(Structured Queries as Relational Expressions)이라는 언어가 발표되었다. 하지만 수학적인 표현이 많아서 초보자가 사용하기 어려웠는데 1974년에..

문제 출처: https://www.acmicpc.net/problem/17298 1. 결과 메모리 153484KB, 시간 1212ms 2. 풀이 처음에는 이 문제를 이중 for문을 통해 각 자리의 숫자(i번째)마다 이후의 숫자(i+1번째부터 n번째까지)를 탐색하며 큰 수가 있다면 이를 저장하며 break, 없다면 끝까지 탐색 후 -1을 추가하게 되는 방법으로 작성했다. 이 경우는 답은 도출이 되었지만 시간 복잡도가 크게(O(N^2)) 발생되었다. 다른 풀이로는 먼저 첫 숫자에 대해 나머지 숫자를 탐색하며 첫 숫자보다 큰 숫자가 있다면 해당 숫자를 스택에 저장하고, 두 번째 숫자부터 모두 해당 숫자보다 작다면 스택의 마지막 숫자를 그대로 또 추가하는 방식을 적용해봤다. 만약 스택의 마지막 숫자보다 현재 숫..

문제 출처: https://www.acmicpc.net/problem/6549 1. 결과 메모리 44580KB, 시간 3468ms 2. 풀이 우선 풀었을 때, 첫 플래티넘 문제라는 것이 신기하고 좋았다. 분할 정복법의 큰 틀에서 벗어나지 않은 형식인 것 같은데, 의외로 난이도가 있었다는 이야기 같다. 말한 대로 이 문제는 재귀를 통한 분할 정복법을 이용한다. 주어진 높이 리스트를 반을 가른 후, 그 반의 왼쪽에 있는 높이들 중에서 가장 큰 넓이, 반의 오른쪽에 있는 높이들 중 가장 큰 넓이, 그리고 가운데 선을 포함하여 가장 큰 넓이를 각각 구한다. 그리고 이 셋 중 가장 큰 넓이를 반환하면 된다. 왼쪽과 오른쪽의 높이들에는 다시 이 함수를 재귀로 적용시키면 된다. 이 문제의 등급을 플래티넘으로 올리는데..

문제 출처: https://www.acmicpc.net/problem/18258 1. 결과 메모리 92936KB, 시간 1764ms 2. 풀이 이전에 풀었던 큐 문제에서 이번엔 시간제한이 추가되었다. 문제 설명에서는 시간 복잡도가 O(1)이어야 한다고 제시했다. 연결 리스트를 통한 큐는 비교적으로 삽입, 삭제 등의 연산에서 유리하다고 생각했기 때문에 이전에 연결 리스트로 구현한 큐 코드를 그대로 제출했다. 하지만 이 코드가 시간 초과가 발생했다. 최대한 메모리와 연산을 줄여서 구현한 연결 리스트와 큐인데도 시간 초과가 발생했다. 이전에 패키지 collections에서 deque라는 자료구조가 큐를 구현한 것이고, queue 라이브러리의 Queue보다도 연산이 빠르다는 것을 들었기 때문에 이번엔 deque..

문제 출처: https://www.acmicpc.net/problem/10845 1. 결과 메모리 29200KB, 시간 80ms 2. 풀이 문제에서 제시한 연산 6개를 수행할 수 있는 기본적인 자료구조 큐를 구현해보는 문제였다. 큐는 FIFO(First In First Out), 선입선출의 특징을 갖는 자료구조로써, 말 그대로 먼저 들어온 자료가 먼저 출력되는 형태이다. 현실에서는 선착순, 은행 대기줄 등의 상황을 예시로 들 수 있다. 파이썬에서 제공하는 자료 타입인 리스트(list, 자료구조인 리스트와는 다른 것)로도 구현할 수 있는데, 기본적으로 파이썬의 리스트 타입은 자료구조 중 '배열'이고, 그중에서도 기본적으로는 스택을 구현한 형태를 갖는다. append를 하면 가장 뒤에 쌓이고, pop을 하면..