분류 전체보기

[백준] 16139 - 인간-컴퓨터 상호작용 (자바/Java)

문제 링크 성능 요약 메모리: 106172 KB, 시간: 608 ms 분류 누적 합(prefix_sum) 문제 설명 승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. '문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.' 승재를 도와 특정 문자열 $S$, 특정 알파벳 $\alpha$와 문자열의 구간 $[l,r]$이 주어지면 $S$의 $l$번째 문자부터 $r$번째 문자 사이에 $\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 $0$번째부터 세며, $l$번째와 $r$번..

[백준] 11659 - 구간 합 구하기 4 (자바/Java) : 누적 합

문제 링크 성능 요약 메모리: 235808 KB, 시간: 1080 ms 분류 누적 합(prefix_sum) 문제 설명 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 누적합 알고리즘의 기본을 익힐 수 있는 문제다. 누적 합 arr[i] = 0~i까지의 합 i부터 j까지의 누적 합: arr[j]-arr[i-1]; = i, i+1, … j-1, j 까지의 합 pack..

[백준] 2565 - 전깃줄 (자바/Java)

문제 링크 성능 요약 메모리: 13084 KB, 시간: 124 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에..

[SWEA][모의 SW 테스트] 2105 - 디저트 카페 (자바/Java)

대각선으로 사방탐색을 하는 문제다. 주의해야할 조건은 같은 숫자의 디저트를 만나면 안된다. 시작점을 제외하고 이미 방문했던 곳은 다시 방문할 수 없다. 시작점으로 돌아오도록 사각형이 그려져야 한다. 최대한 많은 디저트를 먹어야 한다. map의 좌표가 N일 때, 대각선으로 투어를 해야하기 때문에 양 끝 꼭짓점에서는 순회를 시작할 수 없다. 가장 큰 사각형의 가로 세로의 합은 N-1이다. 위 사진에서 N은 5고, 두 사각형이 가능한 최대 길이의 사각형이다. 왼쪽의 경우 가로가 3, 세로가 1이고 오른쪽은 가로가 2, 세로가 2다. 일직선이나 자기 자신만 투어하는 경우는 불가능하기 때문에 사각형의 한 변의 최소 길이는 1, 최대 길이는 N-2가 될 것이다. 이를 활용해서 두 변의 길이의 합이 최대일 때부터 최..

[데이터베이스 개론] 4. 데이터 모델링

목차 4. 데이터 모델링 01 데이터 모델링과 데이터 모델의 개념 데이터 모델링: 현실 세계에 존재하는 데이터를 컴퓨터 세계의 데이터베이스 옮기는 변환 과정 추상화(abstraction): 데이터베이스에 저장하여 관리할 만한 가치가 있는 중요 데이터를 찾아내는 과정 현실 세계 → (개념적 모델링) → 개념 세계 → (논리적 모델링) → 컴퓨터 세계 개념적 모델링: 현실 세계에서 중요 데이터를 추출하여 개념 세계로 옮기는 작업 논리적 모델링: 개념 세계의 데이터를 데이터베이스에 저장할 구조를 결정하고 이 구조를 표현하는 작업 데이터 모델: 데이터 모델링의 결과물을 표현하는 도구 데이터 구조 개념적 데이터 모델-현실 세계를 개념 세계로 추상화했을 때 어떤 요소로 이루어져 있는지를 표현하는 개념적 구조 논리적..

[백준] 11053 - 가장 긴 증가하는 부분 수열 (자바/Java)

문제 링크 성능 요약 메모리: 16964 KB, 시간: 192 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 가장 긴 증가하는 부분 수열 (LIS)를 구하는 문제다. 여러 가지 방법이 있지만 입력이 10..

[데이터베이스 개론] 3. 데이터베이스 시스템

목차 03 데이터베이스 시스템 01 데이터베이스 시스템의 정의 데이터베이스에 데이터를 저장하고, 저장된 데이터를 관리하여 조직에 필요한 정보를 생성해주는 시스템 데이터베이스: 데이터를 저장해두는 곳, 저장된 데이터의 집합 데이터베이스 관리 시스템: 데이터베이스에 저장된 데이터를 관리 데이터베이스 시스템: 데이터베이스와 데이터베이스 관리 시스템을 이용해 조직에 필요한 정보를 제공하는 ‘전체 시스템’ → 데이터베이스 시스템의 핵심 구성 요소 = 데이터베이스, 데이터베이스 관리 시스템 +사용자, 데이터 언어, 컴퓨터 등 02 데이터베이스의 구조 1. 스키마 schema 데이터베이스에 저장되는 데이터 구조와 제약조건을 정의 ex. 고객- 고객번호(INT), 이름(CHAR(10)), 나이(INT), 주소 (CHA..

[백준] 1463 - 1로 만들기 (자바/Java) : DP

문제 링크 성능 요약 메모리: 55224 KB, 시간: 224 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 정수 X가 2와 3 모두 나누어 떨어지지 않는 경우에는 X-1을 하면 된다. 문제는 2 또는 3과 나누어 떨어지는 경우에, 2나 3으로 나누는 것이 최적의 답이 아닐 ..

[SWEA] 1767 - 프로세서 연결하기 (자바/Java)

조합을 통해 경우의 수를 한정하는 방법을 자주 사용해야 할 것 같다. 처음에는 그냥 dfs로 풀어서 답은 맞았는데, 시간과 메모리를 너무 많이 잡아 먹었다. 지금 생각해보니 필요 없는 경우의 수까지 모두 탐색해서 그런 것 같다. 연결하는 코어의 수가 최대여야 하기 때문에, 모든 코어를 연결하는 경우의 수부터 dfs를 진행하고, 만약 그 수의 코어를 연결할 수 없다면 코어의 개수 N 중 N-1개, N-2개를 뽑는 조합을 통해 dfs를 반복하여 결과값이 나올 때까지 계속하면 된다. 이런 경우에서는 조합을 활용하는 게 유용한 것 같다. for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { arr[i][j] = sc.nextInt(); if (arr[i][j] ..

[백준] 2579 - 계단 오르기 (자바/Java) : DP

문제 링크 성능 요약 메모리: 13208 KB, 시간: 128 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다...