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

백준 1806 : 부분합 등급 : Gold IV 1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 사용 알고리즘 : Two Pointer 사용 자료구조 : Vector 정렬되지 않은 배열에서의 합의 길이가 최소가 되는 길이를 구하는 문제이다. Sum이 Target보다 크거나 같으면 Left를 늘려주고, Sum이 Target보다 작으면 Right를 늘려주는 방식으로 풀 수 있다. 1. n값과 s값, n에 따른 배열 값을 입력받음. 2. left, righ..

백준 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 크기의 행렬을 선택 후 반전하였을 때, 그림의 결과와 같이 어느 곳을 먼저 반전을 하든 같은 결과가 나옴을 볼 수 있다. 즉, 행렬 반전 함수의 경우 교환 법칙이 성립한다. 이 점을 이용하여, 처음부터 탐색 해 원하는 행렬과 값이 다른 정점이 나..