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

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

CPU 명령어 수행 과정과 파이프라인 [ CPU 명령어 수행 과정 ] 1. Instruction Fetch : 실행할 명령어를 메모리에서 읽어 CPU로 가져오는 단계. 1) PC가 가리키는 주소를 MAR에 전송. 2) MAR에 적힌 주소를 메모리에서 읽어 MBR로 전송. 3) MBR에 있는 명령어를 IR에 저장. 4) 다음 명령어를 가리키도록 PC 주소값 증가. ※ PC(Program Counter) : 다음 명령어를 가리키는 주소값을 가진 레지스터. MAR(Memory Access Register) : CPU가 사용하려는 명령어 주소를 일시적으로 저장하는 레지스터. MBR(Memory Buffer Register) : CPU에 쓰여질 데이터를 일시적으로 저장하는 버퍼 레지스터. IR : 가장 최근에 인..