이것저것

메모리 상에 원소를 연속하게 배치한 자료구조. 시간복잡도 O(1)으로 k번째 원소의 위치를 바로 계산 (확인 및 변경 등) 할 수 있다.타 자료구조와는 다르게 추가적으로 소모되는 메모리의 양이 거의 없다.메모리 상에 데이터들이 붙어있으므로 Cache hit rate가 높다.Cache hit rate란 캐시 적중률을 의미하며 명령이나 자료를 찾기 위해 캐시 메모리에 접근했을 때 자료가 존재하면 적중 Hit 되었다 하고 없다면 실패했다고 한다. 적중률은 적중횟수/총 접근횟수 이며 컴퓨터의 성능을 나타내는 척도로 사용된다.메모리 상 연속한 구간을 잡아야 하므로 할당에 다소 제약이 존재한다. 기능원소를 확인/변경 : O(1)배열 끝에 원소를 추가 : O(1)배열 끝 원소를 제거 : O(1)임의의 위치에 원소를 ..

시간복잡도 컴퓨터는 1초에 대략 3-5억 개의 연산을 처리할 수 있다. 따라서 시간 제한이 1초라고 한다면 3-5억 번의 연산 안에 답을 내고 종료되는 프로그램을 짜야 한다는 뜻으로 이해하면 된다. 입력의 범위를 보고 문제에서 요구하는 시간복잡도를 대략적으로 유추가 가능하다.N의 크기허용 시간복잡도N O(N!)N   25O(2^N)N   100O(N^4)N   500O(N^3)N   3000O(N^2logN)N   5000O(N^2) N   1,000,000O(NlogN)N   10,000,000O(N)그 이상O(logN), O(1) 문제 1N 이하의 자연수 중 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 프로그램을 작성하라. N은 5만 이하의 자연수이다.var n = int.Parse(C..

알고리즘을 공부하는 목적?코딩 테스트의 출제 의도 파악을 분명히 함'최적화'에 대한 이해개인 프로젝트의 퀄리티를 높임포트폴리오의 어필 방향을 확실히 함종류빅오 표기법 Big-O notation - 시간복잡도, 공간복잡도완전 탐색 Brute-force search탐욕적 기법 Greedy Algorithm분할 정복 Divide and conquer동적 계획법 Dynamic programming이진 탐색 Binary search파라메트릭 탐색 Parametric search깊이 우선 탐색 Depth-First search (DFS)너비 우선 탐색 Breadth-First search (BFS)백트래킹 Backtracking비트마스킹 Bit masking구간합 배열 Prefix sum에라토스테네스의 체 Siev..

자료구조를 공부하는 목적?알고리즘 학습에 선행함 종류리스트 List배열 Array연결 리스트 Linked list스택 Stack큐 Queue덱 Double Ended Queue (Dequeue)그래프 Graph트리 Tree이진 검색 트리 Binary search tree우선순위 큐 Priority queue (PQ)유니온 파인드 Union-Find (Disjoint-set)세그먼트 트리 Segment tree (ST)최소 스패닝 트리 Minimum spanning tree (MST)머지 소트 트리 Merge sort tree퍼시스턴트 세그먼트 트리 Persistent segment tree

//5086두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오.첫 번째 숫자가 두 번째 숫자의 약수이다.첫 번째 숫자가 두 번째 숫자의 배수이다.첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다.using System.Diagnostics;int[] input() => Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);int[] i;while(true){ i = input(); if (i[0] == 0 && i[1] == 0) return; else { if ((i[0] % i[1] == 0)) Console.WriteLine("multiple"); el..

//2738N*M크기의 두 행렬 A와 B가 주어졌을 때, 두 행렬을 더하는 프로그램을 작성하시오.int[] xy = Array.ConvertAll(Console.ReadLine().Split(), i => int.Parse(i));int x = xy[0];int y = xy[1];int[,] matrixA = new int[x, y] ;int[,] matrixB = new int [x, y];for (int k = 0; k int[] F() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);int[] nm = F();int[][] n = new int[nm[0]][];for (int i = 0; i   //25669×9 격자판에 쓰여진 81개의 자연..

//2745B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35**진법 B가 15이고, N이 BAA라고 가정했을때.BAA = 11, 10, 10이므로 11 * (15^2) + 10 * (15^1) + 10 * (15^0) 이 되어서 2635가 정답이다.string[] input = Console.ReadLine().Split(' ');string num = input[0];int baseValue = int.Parse(input[1]);long answer = 0;for (int i..

//25083Console.WriteLine(" ,r'\"7");Console.WriteLine("r`-_ ,' ,/");Console.WriteLine(" \\. \". L_r'");Console.WriteLine(" `~\\/");Console.WriteLine(" |");Console.WriteLine(" |");  //3003첫째 줄에 입력에서 주어진 순서대로 몇 개의 피스를 더하거나 빼야 되는지를 출력한다. 만약 수가 양수라면 동혁이는 그 개수 만큼 피스를 더해야 하는 것이고, 음수라면 제거해야 하는 것이다.int[] chessOrigin = { 1, 1, 2, 2, 2, 8 };int[] inputs = Array.ConvertAll(Console.Re..

//27866using static System.Console;string s = ReadLine();int i = int.Parse(ReadLine());WriteLine(s[i-1]);  //2743using static System.Console;string s = ReadLine();WriteLine(s.Length);  //9086using static System.Console;int count = int.Parse(ReadLine());string s = "";for (int i = 0; i using static System.Console;string x() => ReadLine();var s = x();while ((s = x()) != null) WriteLine($"{s[0]}"..

//10807using System;namespace TEST{ class Test { static void Main(string[] args) { int num = int.Parse(Console.ReadLine()); string[] v = Console.ReadLine().Split(); int key = int.Parse(Console.ReadLine()); int answer = 0; for (int i = 0; i   //10871using System;namespace TEST{ class Test { static void Main(st..