문제 www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 기본적으로 브루트포스에 속하지만, 백트래킹을 적용하여 풀 수 있는 문제였다. 이 문제는 다음과 같은 부분 문제로 나눠볼 수 있다. 1) 현재 상태에서 괄호를 넣는 경우와 안 넣는 경우를 모두 검사한다. 2) 괄호를 취한 식을 계산한다. 1)부터 살펴보자. 여기선 이 문제의 제약 조건 중 "중첩된 괄호는 사용할 수 없다."에 주목해야 한다. 이 말은 괄호의 위치가 고정되어 있다는 뜻이다..
일반적으로 스프레드시트를 MySQL 테이블로 옮기는 데엔 Workbench 내장 기능인 Table Data Import Wizard나 외부 응용프로그램인 MySQL for Excel이 사용된다. 오늘은 이 중 Table Data Import Wizard를 통한 CSV 파일 Import에 대해서 소개하고자 한다. 1. MySQL Workbench 실행 및 테이블 확인 먼저 데이터를 삽입하고자 하는 테이블을 확인해보자. 데이터를 넣고자 하는 categories 테이블은 category_pk(int)와 category_name(varchar) 2개의 column으로 구성되어있다. 2. Import하고자 하는 시트를 CSV로 변환 MS Excel이나 Google 스프레드시트를 이용해 Import하려는 시트를 C..
문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 로봇 청소기와 점프를 합쳐 놓은 듯한 문제였다. 문제 유형은 다이나믹 프로그래밍이면서도, 구현 능력도 요구하는 문제였다. 문제에서 고려할 중요한 조건은 다음과 같다. 1) 가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 2) 파이프가 놓여진 방향에 따라 회전 방향이 결정된다. 3) 회전 방향에 따라 특정 칸이 무조건 비어있어야 한다. dir..
그래프 순회란? 그래프 순회란 그래프 탐색(Search)라고도 일컫으며 그래프의 각 정점을 방문하는 과정을 의미하며, 크게 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search)으로 나뉜다. DFS는 주로 스택이나 재귀로 구현하며 백트래킹 알고리즘에 사용된다. 반면에 BFS는 주로 큐로 구현하며 그래프의 최단 경로를 구하는 문제 등에 사용된다. 깊이 우선 탐색(DFS) 일반적으로 DFS는 스택으로 구현하며, 재귀를 이용하면 좀 더 간단하게 구현할 수 있다. 실제로 코딩 테스트에서는 재귀를 이용한 구현이 더 선호되는 편이다. 재귀적 구조로 구현 먼저 재귀 구조로 DFS를 구현해보자. 슈도코드는 다음과 같다. RecursiveDFS(v)..
배열이란? 데이터를 연속적인 메모리 공간에 저장하고, 저장된 곳의 주소(address, reference)를 통해 매우 빠른 시간에 접근할 수 있는 가장 많이 쓰이는 기본적인 자료구조 C언어의 배열(Array) 크기가 고정되어 있으며, 한 번 생성한 배열은 크기를 변경하는 것이 불가능하다. 배열의 시작 주소, 저장된 값의 종류(바이트 개수), 몇 번째에 저장되어 있는지를 나타내는 인덱스(index) 세 가지 정보만으로 값이 저장된 곳의 주소를 계산할 수 있다. 읽기와 쓰기 연산에 O(1) 시간 소요 Python의 리스트(List) C의 배열의 셀에는 실제 값(데이터)이 저장된 형식이지만, Python 리스트의 셀에는 데이터가 아닌 데이터가 저장된 곳의 주소(address 또는 reference)가 저장된..
