개발일지

이진탐색이란?- 어떤 값을 찾을때 정렬의 특징을 이용해 빨리 찾음- 정렬이 되어 있을 경우, O(N) -> (logN)- 기존 다른 방법으로 시간 복잡도를 생각했을때, 안되면 이진탐색으로 처리하면 좋음 첫 아이디어- M개의 수마다 각각 어디에 있는지 찾기- for : M개의 수- for : N개의 수안에 있는지 확인 첫 시간복잡도- for : M개의 수 > O(M)- for : N개의 수안에 있는지 확인 > O(N)- O(MN) = 1e10 > 시간초과 아이디어- M개를 확인해야는데, 연속하다는 특징 활용 가능(투포인터)? => 연속하지 않아 불가- 정렬해서 이진탐색 가능?(N개의 수 먼저 정렬)(M개의 수 하나씩 이진 탐색으로 확인) 시간 복잡도- N개의 수 정렬 : O(N * lgN)- M개의 수 ..

시뮬레이션이란?- 각 조건에 맞는 상황을 구현하는 문제(지도상에서 이동하면서 탐험?하는 문제, 배열 안에서 이동하면서 탐험? 하는 문제)- 별도 알고리즘 없이 풀수 있으나, 구현력이 중요- 매 시험마다 1문제 이상 무조건 출제 시간복잡도- N * M- 각 칸에서 4방향 연산 수행 자료구조- 전체 지도 int[][]- 내 위치, 방향; int, int, int 문제풀이- 백준 14503 1. // 입력 받기string[] input = Console.ReadLine().Split();int N = int.Parse(input[0]);int M = int.Parse(input[1]);input = Console.ReadLine().Split();int y = int.Parse(input[0]);int x =..

백트래킹이란?- 모든 경우의 수를 확인해야할 때 사용(for으로 확인 불가할 경우 - 깊이가 달라질때)- 수열을 구하는 문제에 사용 아이디어 1. 1~N중에 하나를 선택2. 이미 선택한 값이 아닌 경우를 선택(방문여부 체크)3. M개를 선택할때 프린트(재귀 함수 사용) 시간복잡도- N^N: 중복이 가능, N = 8까지 가능 (2억이 넘지 않아야함)- N! : 중복이 불가능, N = 10까지 가능 (2억이 넘지 않아야함) 자료구조- 방문 여부 확인 배열 : bool[]- 선택한 값 입력 배열 : int[] 문제풀이- 백준 15649번 1. /*1. 아이디어- 백트래킹 재귀함수 안에서, for 돌면서 숫자 선택(이때 방문 여부 확인)- 재귀함수에서 m개를 선택할 경우 출력2. 시간복잡도- N! 3. 자료..

깃 링크 : 바로가기링크 : 바로가기 1차시도class num_2798{ static void Main() { string[] input = Console.ReadLine().Split(); int N = int.Parse(input[0]); int M = int.Parse(input[1]); string[] input2 = Console.ReadLine().Split(); List list = new List(); for (int i = 0; i result) { result = sum; } ..

깃 링크 : 바로가기링크 : 바로가기 1차시도class num_24267{ static void Main() { string[] input = Console.ReadLine().Split(); int a1 = int.Parse(input[0]); int a0 = int.Parse(input[1]); int c = Convert.ToInt32(Console.ReadLine()); int n0 = Convert.ToInt32(Console.ReadLine()); bool check1 = a1 결과- "f(n) = 7n + 7, g(n) = n, c = 8, n0 = 10 이라고 한다 - n0는 n의 최소값이며, n0를 n..

깃 링크 : 바로가기링크 : 바로가기 1차시도class num_24267{ static void Main() { long n = long.Parse(Console.ReadLine()); long result = n * (n - 2) * (n - 1) / 6; Console.WriteLine(result); Console.WriteLine(3); } /* MenOfPassion(A[], n) { sum 결과- 삼중 반복문으로 최고다항은 3- for문에 "to n - 2", "to n - 1"이기 때문에 수행시간은 "n * (n-2) * (n-1) / x"이며- x값은 삼중 반복문이라 3이라 생각할 수 있지만 3!으로..

깃 링크 : 바로가기링크 : 바로가기 1차시도class num_24266{ static void Main() { int n = int.Parse(Console.ReadLine()); Console.WriteLine(Math.Pow(n, 3)); Console.WriteLine(3); } /* MenOfPassion(A[], n) { sum 결과- 삼중 반복문으로 최고차항수는 3이며,- Math.Pow는 double타입으로 표기 문제가 있다고함 2차 시도class num_24266{ static void Main() { long n = long.Parse(Console.ReadLine()); ..

깃 링크 : 바로가기링크 : 바로가기 1차시도class num_24265{ void Main() { int n = int.Parse(Console.ReadLine()); Console.WriteLine((long)n * (n - 1) / 2); Console.WriteLine(2); } /* MenOfPassion(A[], n) { sum 결과- 이중 반복문으로 최고차항수는 2 - 수행시간은 for문에 n-1이기 때문에 n * (n-1) / 2 처리, - "첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다."이기 때문에 500,000 * 499,999 / 2 = 124,999,750,000로 int값인 21..

깃 링크 : 바로가기링크 : 바로가기 1차시도class num_24264{ void Main() { int n = int.Parse(Console.ReadLine()); Console.WriteLine(Math.Pow(n, 2)); Console.WriteLine(2); } /* MenOfPassion(A[], n) { sum 결과- 이중 반복문으로 알고리즘 수행 시간이 n*n이기 때문에 최고차항은 2이며 O(n^2)로 판단- 최고차항수는 2, 수행 횟수는 n의 2승이며 Math.Pow를 이용하여 계산

깃 링크 : 바로가기링크 : 바로가기 1차시도class num_24263{ static void Main() { int n = int.Parse(Console.ReadLine()); Console.WriteLine(n); Console.WriteLine(1); } /* MenOfPassion(A[], n) { sum 결과- MenOfPassion 함수를 보면 for문을 이용해 계산하고 있어 시간복잡도는 O(n)이며, 상수가 아니기 때문에 최고차항은 1이다.