CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 언뜻 보기에는 bfs로 풀 수 있을 것 같은 문제이지만, 특히 JAVA를 이용해 bfs로 구현을 하면 메모리 초과, 또는 시간 초과가 뜰 확률이 굉장히 높습니다. 이 문제는 bfs 대신 다이나믹 프로그래밍을 이용해 해결할 수 있습니다. 우선 arr라는 배열에 입력으로부터 행렬을 받아 넣습니다. 그리고 arr[i][j]를 오른쪽 아래 꼭짓점으로 하는 정사각형의 한 변의 길이를 d..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 난이도: 실버 3 사용언어: JAVA 풀이 이 문제는 '', 그리고 공백에 대한 예외처리만 잘해주면 쉽게 해결할 수 있습니다. 저는 스택을 이용해 문자열을 뒤집고 출력했습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 난이도: 실버 2 사용언어: JAVA 풀이 복잡하게 생각하지 말고, 배열에서 증가하는 부분과 감소하는 부분을 별개로 반복문을 수행하면 쉽게 정답을 찾아낼 수 있습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 난이도: 실버 4 사용언어: JAVA 풀이 이 문제는 스택을 이용하여 해결할 수 있습니다. 자신보다 오른쪽에 있는 수 중에 자신보다 크고 가장 왼쪽에 있는 수를 찾는 문제이기 때문에, 배열의 가장 뒤에서부터 반복문을 돌며 자신보다 크고 가장 왼쪽에 있는 수를 스택에 저장하는 방법을 사용하였습니다. 아래의 예시를 이용해 설명해보도록 하겠습니다. 우선 스택에 가장 오..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 난이도: 실버 2 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 이 문제를 풀기 위해서는 기본적인 아이디어가 하나 필요합니다. n이라는 값이 주어진다면, n은 1 + (n-1) or 2 + (n-2) or 3 + (n-3) 으로 표현될 수 있습니다. 다시 말해, n-1을 만드는 경우의 수에 1을 더하면 n이 되고, n-2를 만드는 경우의 수에 2를 더하면 역시..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍으로 접근할 수 있습니다. 상황에 따라 옮길 수 있는 위치가 다 다르므로 (직각으로 꺾을 수 없다던지...), 배열을 3개 선언하여, 오른쪽 칸으로 보내줄 수 있는 경우의 수, 아래쪽 칸으로 보내줄 수 있는 경우의 수, 대각선으로 보낼 수 있는 경우의 수..

데이터베이스 설계란 데이터베이스를 생성하는 일련의 과정으로 볼 수 있습니다. 데이터베이스 설계는 다음과 같은 순서로 진행됩니다. 요구사항 분석 -> 개념적 설계 -> 논리적 설계 -> 물리적 설계 -> 구현 각 단계에 대해 자세히 공부해보도록 하겠습니다. 1. 요구사항 분석 요구사항 분석은 말 그대로 사용자의 요구사항을 수집하고 분석하는 과정입니다. 성공적인 데이터베이스 설계를 위해서는 반드시 정확한 사용자의 요구사항을 도출해내어야 하며, 전체 시스템 개발 과정 중에 가장 어려운 단계로 볼 수도 있습니다. 사용자에 따른 수행 업무와 필요한 데이터의 종류, 용도, 처리 형태, 흐름, 제약 조건 등을 수집해야 하며, 수집한 자료를 바탕으로 요구사항 명세서를 작성합니다. 2. 개념적 설계 개념적 설계란 현실 ..

1. 데이터베이스란? 데이터베이스는 특정 업무를 수행하는 데 필요한 상호 관련된 데이터들의 모임입니다. 이 정의를 풀어서 설명하면 다음과 같습니다. 1. 통합된 데이터 (Integrated Data): 데이터베이스는 자료의 중복을 배제한 데이터의 모임입니다. 그러나 실제로는 중복을 완전히 배제하지는 않고, 필요에 따라 효율성을 높이기 위해 통제된 중복(Controlled Redundancy)은 허용합니다. 2. 저장된 데이터 (Stored Data): 데이터베이스는 컴퓨터가 접근할 수 있는 매체에 저장된 자료입니다. 3. 운영 데이터 (Operational Data): 데이터베이스의 데이터들은 조직의 업무를 수행하는 데 있어서 반드시 필요한 데이터들입니다. 4. 공용 데이터 (Shared Data): 데..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 난이도: 실버 3 사용언어: JAVA 풀이 다이나믹 프로그래밍으로 누적 합을 구하는 아주 기초적인 문제입니다. 배열을 하나 별도로 만들어 우선 해당 값까지의 총합을 구해 저장시켜두고, 입력으로 구간을 받아 해당 구간의 합을 구해주면 됩니다. 예제에서 배열의 입력이 5 4 3 2 1 이었으니, 해당 값까지의 합을 구해두는 배열 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 난이도: 실버 1 사용언어: JAVA 풀이 백준에 나와있는 알고리즘 분류에는 DFS나 플로이드-와샬과 같은 알고리즘도 적혀있지만, 가장 해결하기 쉬운 방법은 그냥 브루트포스로 접근하는 것입니다. 우선 입력으로부터 친구들을 모두 구하고, 해당 친구들의 친구까지 확인하여 카운팅 해주기만 하면 됩니다. 코드의 주석을 보는 것이 이해하기 편할 것 같습니다. 1..