개발일지

이진탐색이란?- 어떤 값을 찾을때 정렬의 특징을 이용해 빨리 찾음- 정렬이 되어 있을 경우, 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개의 수 ..

투포인터란?- 각 원소마다 모든 값을 순회해야할때, o(n^2)- 연속하다는 특성을 이용해 처리, O(N)- 두개의 포인터(커서)가 움직이면서 계산 처음 아이디어- for문으로 각 숫자의 위치에서 이후 K개의 개수를 더함- 이때마다 최대 값으로 갱신 처음 시간 복잡도- for문 : O(N)- 각 위치에 K개의 값 더함: O(K)- 총 : O(NK) 아이디어- 처음 K개의 값을 구함- for문: 다음 인덱스의 값을 더하고, 앞의 값을 뺌- 이때 최대값을 갱신 시간 복잡도- 숫자 개수만큼 for => O(N) 자료구조- 전체 정수 배열: int[]- 합한 수 : int 문제풀이- 백준 2559 1.public class num_2559{ static void Main(string[] args) {..

시뮬레이션이란?- 각 조건에 맞는 상황을 구현하는 문제(지도상에서 이동하면서 탐험?하는 문제, 배열 안에서 이동하면서 탐험? 하는 문제)- 별도 알고리즘 없이 풀수 있으나, 구현력이 중요- 매 시험마다 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. 자료..

DFS란?- 바로가기 [필수 알고리즘] 그래프 탐색그래프 탐색이란?- 어떤 것들이 연속해서 이어질때, 모두 확인하는 방법- Graph: Vertex(어떤 것) + Edge(이어지는 것) 그래프 탐색 종류- BFS : 너비 우선 탐색- DFS : 깊이 우선 탐색 BFS- 자기 자식을 우선lhy-info.tistory.com- Stack과 재귀함수를 이용해 풀수 있음- 그래프 탐색은 BFS로 대부분 풀수 있으며, DFS는 재귀 함수를 사용하기 위함이며 백트래킹에서 효율적이라함 재귀함수란?- 자기 자신을 다시 호출하는 함수- DFS, 백트래킹에서 주로 사용 풀이방법- 시작 Vertex 찾기- 연결된 Vertex를 계속 찾음(끝날때 까지)- 더이상 연결된 Vertex 없을 경우 다음 진행- 1 -> 2 -> 3..

BFS란?- 바로가기 [필수 알고리즘] 그래프 탐색그래프 탐색이란?- 어떤 것들이 연속해서 이어질때, 모두 확인하는 방법- Graph: Vertex(어떤 것) + Edge(이어지는 것) 그래프 탐색 종류- BFS : 너비 우선 탐색- DFS : 깊이 우선 탐색 BFS- 자기 자식을 우선lhy-info.tistory.com 풀이 방법1. Vertex 찾기2. 찾은 Vertex를 Queue에 저장3. Queue에서 뽑아 반복 *Queue란?- 선입선출로 먼저 들어온 것이 제일 먼저 나간다. - 1번 추가 -> 2,5번 추가 -> 2번 확인하며 3번 추가 -> 5번 확인하며 4번 추가 -> 4번 확인하며 6번 추가 시간복잡도(Big - O)- 알고리즘이 얼마나 오래 걸리는지- 제한시간안에 나와야함 BFS의 시..

그래프 탐색이란?- 어떤 것들이 연속해서 이어질때, 모두 확인하는 방법- Graph: Vertex(어떤 것) + Edge(이어지는 것) 그래프 탐색 종류- BFS : 너비 우선 탐색- DFS : 깊이 우선 탐색 BFS- 자기 자식을 우선 탐색- 탐색 순서 : 1 -> 2 -> 5 -> 3 -> 4 -> 6 DFS- 자식의 자식을 우선 탐색- 탐색순서 : 1 -> 2 -> 3 -> 4 -> 6 -> 5 참고 영상- 바로가기