개발자 지망생의 끄적끄적 개발기록

백준 12015 : 가장 긴 증가하는 부분 수열 2 등급 : Gold II 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 사용 알고리즘 : Binary Search 사용 자료구조 : Vector 소위 LIS(Longest Increasing Subsequence)라고 알려진 이 문제는 동적 계획법과 이분 탐색으로 풀 수 있다. 이때, 전체적인 수열을 구하는 것이 아닌 횟수만 측정한다면, 이분 탐색으로 더 빠르게 결과를 구하는 것이 가능하다..

백준 6443 : 애너그램 등급 : Gold V 6443번: 애너그램 (acmicpc.net) 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 사용 알고리즘 : Backtracking 사용 자료구조 : - 문자열 중복을 방지하며 백트래킹을 하는 문제였다. 들어오는 알파벳을 계수 정렬(Counting Sort)로 처리해주고, 이를 검사해가면서 풀면 가능하게 된다. ( 방문 정보를 set으로 탐색하는 경우 TLE가 발생한다 ) 1. 알파벳을 계수 정렬 해주기 위해 크기가 26인 visit 배열 생성. 2. ..

백준 1202 : 보석 도둑 등급 : Gold II 1202번: 보석 도둑 (acmicpc.net) 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 사용 알고리즘 : Greedy, Sorting 사용 자료구조 : Deque, Priority_Queue 정렬과 우선순위 큐를 이용해 푸는 그리디 문제였다. 가방의 크기와 보석을 무게순으로 오름차순으로 정렬하고, 가방을 하나씩 선택해 현재 가방의 허용 무게 내의 보석을 선택. 현재 가방에 들어갈 수 있는 ..

백준 1080 : 행렬 등급 : Silver I 1080번: 행렬 (acmicpc.net) 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 사용 알고리즘 : Greedy 사용 자료구조 : Vector 그림의 4×4 행렬에서 (0, 0)의 위치와 (1, 1)의 위치를 기준으로 3×3 크기의 행렬을 선택 후 반전하였을 때, 그림의 결과와 같이 어느 곳을 먼저 반전을 하든 같은 결과가 나옴을 볼 수 있다. 즉, 행렬 반전 함수의 경우 교환 법칙이 성립한다. 이 점을 이용하여, 처음부터 탐색 해 원하는 행렬과 값이 다른 정점이 나..

백준 1062 : 가르침 등급 : Gold IV 1062번: 가르침 (acmicpc.net) 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 사용 알고리즘 : Brute-Force, Backtracking, Bitmasking 사용 자료구조 : Vector 백트래킹과 비트마스킹을 적절히 이용하여 풀 수 있는 문제. 탐색 완료를 점검하는 조건에서 코너 케이스가 있어 반례를 찾고 수정하는 데 약간 애를 먹었다. 1. 전체 단어 중 포함된 알파벳을 저장할 배열 chk[26]과, 현재 단어에서 포함된 알파벳을..