분류 전체보기

[백준] 12100 - 2048 (Easy) (자바/Java)

문제 링크 성능 요약 메모리: 24332 KB, 시간: 348 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 구현(implementation), 시뮬레이션(simulation) 문제 설명 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) ..

[SWEA] 4008 - 숫자 만들기 (자바/Java)

dfs를 통해 가능한 연산 결과를 완전 탐색하며 최대, 최소값을 저장하였다. 연산을 N-1번 수행하니까 idx가 N-1이 될 때 연산이 끝난 것이므로 함수를 return 한다. 연산자 배열에서 각 인덱스의 값이 0이 아니면 그 연산자로 계산할 수 있는 것이니까 계산 값을 재귀적으로 함수에 넣어준다. static void dfs(int idx, int res) { if (idx == N - 1) { min = Math.min(res, min); max = Math.max(res, max); return; } for (int i = 0; i < 4; i++) if (op[i] != 0) { op[i]--; dfs(idx + 1, cal(i, res, nums[idx + 1])); op[i]++; } } 가능..

[백준] 12865 - 평범한 배낭 (자바/Java) : Knapsack Problem

[Gold V] 평범한 배낭 - 12865 문제 링크 성능 요약 메모리: 52664 KB, 시간: 192 ms 분류 다이나믹 프로그래밍(dp), 배낭 문제(knapsack) 문제 설명 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 ..

[백준] 17069 - 파이프 옮기기 2 (자바/Java)

문제 링크 성능 요약 메모리: 11880 KB, 시간: 84 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프..

[백준] 1759 - 암호 만들기 (자바/Java)

문제 링크 성능 요약 메모리: 13036 KB, 시간: 120 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 조합론(combinatorics), 수학(math) 문제 설명 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서..

[데이터베이스 개론] 2. 데이터베이스 관리 시스템

목차 데이터베이스 관리 시스템 01 데이터베이스 관리 시스템의 등장 배경 과거-파일 시스템을 이용 파일 시스템 장점: 별도의 구매비용x 응용 프로그램마다 파일을 따로 유지 문제점 같은 내용의 데이터가 여러 파일에 중복 저장 응용 프로그램이 데이터 파일에 종속적 데이터 종속성: 사용하는 파일의 구조를 변경하면 응용 프로그램도 함께 변경해야 한다 데이터 파일에 대한 동시 공유, 보안, 회복 기능이 부족하다 응용 프로그램을 개발하기 쉽지 않다 02 데이터베이스 관리 시스템의 정의 데이터베이스 관리 시스템(DBMS: DataBase Management System) 정의: 파일 시스템의 데이터 중복과 데이터 종속 문제를 해결하기 위해 제시된 소프트웨어 조직에 필요한 데이터를 데이터베이스에 통합하여 저장하고 이에..

[백준] 11444 - 피보나치 수 6

[Gold II] 피보나치 수 6 - 11444 문제 링크 성능 요약 메모리: 12888 KB, 시간: 108 ms 분류 분할 정복을 이용한 거듭제곱(exponentiation_by_squaring), 수학(math) 문제 설명 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오...

[백준] 2630 - 색종이 만들기 (자바/Java)

[Silver II] 색종이 만들기 - 2630 문제 링크 성능 요약 메모리: 30196 KB, 시간: 300 ms 분류 분할 정복(divide_and_conquer), 재귀(recursion) 문제 설명 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이..

[백준] 17070 - 파이프 옮기기 1 (자바/Java)

문제 링크 성능 요약 메모리: 18016 KB, 시간: 340 ms 분류 다이나믹 프로그래밍(dp), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이..

[백준] 10830 - 행렬제곱 (자바/Java)

[Gold IV] 행렬 제곱 - 10830 문제 링크 성능 요약 메모리: 12892 KB, 시간: 112 ms 분류 분할 정복(divide_and_conquer), 분할 정복을 이용한 거듭제곱(exponentiation_by_squaring), 선형대수학(linear_algebra), 수학(math) 문제 설명 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 ..