BOJ 백준 10273 고대 동굴 탐사 문제: https://www.acmicpc.net/problem/10273 10273번: 고대 동굴 탐사 입력의 첫 줄엔 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 10) 각 테스트 케이스의 첫 줄엔 탐사할 수 있는 동굴의 수 N과 서로 직접 연결된 동굴 쌍의 수 E가 주어진다. (1 ≤ N ≤ 2 · 10 4; 0 ≤ E www.acmicpc.net 문제 내용이 길고 복잡해서 처음에는 문제 풀기가 까다로웠다. 그런데 간단히 정리하면 다음과 같다. 단방향 그래프가 주어지고 각 정점 방문 시 얻을 수 있는 이익과 각 간선을 탔을 때의 비용이 주어졌을 때, 해당 그래프를 탐색해서 얻을 수 있는 순이익의 최댓값을 구한다. 앞의 작업 진척도에 관한 내용은 사실 크..

BOJ 백준 6672 Electricity 문제: https://www.acmicpc.net/problem/6672 6672번: Electricity Blackouts and Dark Nights (also known as ACM++) is a company that provides electricity. The company owns several power plants, each of them supplying a small area that surrounds it. This organization brings a lot of problems - it often happens that there i www.acmicpc.net 처음에는 문제 내용을 제대로 이해하지 못해서 난처했는데, 결국 간단히 정리..

BOJ 백준 17501 수식 트리 문제: https://www.acmicpc.net/problem/17501 17501번: 수식 트리 수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다. 연산자 노드는 항상 두 개 www.acmicpc.net N개의 피연산자 노드와 N-1개 연산자 노드로 구성된 이진트리에서 피연산자 노드 정수 값을 원하는 만큼 서로 바꿨을 때 나올 수 있는 수식 트리의 최댓값을 구해야 한다. 문제에서는 노드에 있는 정수를 원하는 만큼 바꾸어서 수식 트리의 결과값이 최대가 되도록 한다고 서술했지만, 관점을 달리 바라보면 처음부터 트리를 구성할 때 원하는대로 노드의 정수값을..

BOJ 백준 16472 고냥이 문제: https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 문제에서 주어지는 문자열을 S라고 하자. 이 문제는 크게 두 가지 풀이가 있다. 하나는 인식할 수 있는 문자열의 길이를 가지고 이분 탐색(Binary Search)하는 것과 다른 하나는 두 포인터(Two Pointer)를 사용해서 푸는 것이다. 1. 이분 탐색으로 풀기 이분 탐색 대상을 인식할 수 있는 문자열의 길이로 설정한다. 즉, 길이 mid만큼 연속되는 문자열을 ..

BOJ 백준 19535 ㄷㄷㄷㅈ 문제: https://www.acmicpc.net/problem/19535 19535번: ㄷㄷㄷㅈ 첫 번째 줄에 주어진 트리가 D-트리라면 D, G-트리라면 G, DUDUDUNGA-트리라면 DUDUDUNGA를 출력한다. www.acmicpc.net 정점 수가 N인 트리가 주어졌을 때, 4개의 정점으로 이루어진 ㄷ’ 모양의 서브트리와 ‘ㅈ’ 모양의 서브트리 개수에 3배한 값을 비교하여 해당 트리가 어떤 트리에 속하는지 출력해야 한다. (4 ≤ N ≤ 300,000) 처음에 이 문제를 보고 (트리에서의) 다이나믹 프로그래밍(Dynamic Programming)으로 해결하는 문제일 것으로 예상했다. 그러나 실제로 확인해보니 굳이 거창하게 다이나믹 프로그래밍까지 확장하여 생각할 ..

BOJ 백준 14505 팰린드롬 개수 구하기 (Small) https://www.acmicpc.net/problem/14505 14505번: 팰린드롬 개수 구하기 (Small) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 승수는 주 www.acmicpc.net 'BOJ 백준 14517번 팰린드롬 개수 구하기 (Large)'와 동일한 풀이로 해결 가능한 문제여서 BOJ 14517번을 기준으로 풀이했다. BOJ 백준 14517 팰린드롬 개수 구하기 (Large) https://www.acmicpc.net/problem/14517 1..

BOJ 백준 20667 크롬 문제: https://www.acmicpc.net/problem/20667 20667번: 크롬 첫 줄에는 N, M, K 값이 주어진다. (N ≤ 100, M ≤ 1,000, K ≤ 100,000) N 은 총 크롬 탭 수이다. M 은 목표 CPU 사용량이다. K 은 목표 메모리 할당량이다. 다음 N 줄에는 다음과 같이 크롬 탭의 정보가 www.acmicpc.net N개의 탭 중 일부 탭을 지워서 CPU 사용량을 M 이상, 메모리 사용량을 K 이상 확보하면서 지운 탭의 중요도의 합을 최소로 하는 것을 목표로 한다. 이 때의 중요도 합의 최솟값을 구해야 한다. 우선 이 문제는 다이나믹 프로그래밍(Dynamic Programming)으로 해결해야 한다. 그러면 여기서 다이나믹 프로그..

SQL 제약 조건 제약조건은 데이터의 무결성을 유지하기 위해 특정 컬럼을 원하는 조건의 데이터만 갖도록 하기 위한 제약이다. 제약조건의 종류 타입 설명 PRIMARY KEY (기본 키) 테이블의 행을 고유하게 식별하기 위한 컬럼이며, NULL 값은 불가하므로 기본 키 생성 시 반드시 주의해야 한다. 기본 키 생성 시 DBMS에서 자동으로 UNIQUE 인덱스를 생성한다. (UNIQUE & NOT NULL로 이해하면 쉽다.) FOREIGN KEY (외래키) 다른 테이블의 기본 키를 참조하는 경우 필요한 컬럼이다. UNIQUE (고유 키) 테이블에 저장된 행을 고유하게 식별하기 위한 컬럼이며, 기본 키와는 다르게 NULL 값이 가능하다. NOT NULL 해당 컬럼이 NULL 값을 갖지 못하도록 할 때 선언한다..