알고리즘(코딩테스트)26 빅오(Big-O) 표기법 What is Big-O? 알고리즘의 성능을 수학적으로 표현해주는 표기법 시간과 공간 복잡도를 표현할 수 있음 데이터나 사용자의 증가에 따른 알고리즘의 성능을 측정하는 것이 목표 상수는 모두 1이 됨 O(1) 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘 O(n) 입력 데이터의 크기에 비례해서 처리 시간이 늘어나는 알고리즘 O(n^2) 입력 데이터의 크기만큼 각각의 요소에서 돌 때(ex. 이중 포문) O(nm) m을 n만큼 돌릴 때(만약 m과 n이 같다면 O(n^2)) O(n^3) 입력 데이터의 크기만큼 세 번 돌 때(ex. 삼중 포문) O(2^n) 재귀 함수로 구현 한 피보나치수열 O(logn) 한 번 처리할 때마다 검색해야 하는 데이터의 양이 절반으로 줄어드는 알고리즘(ex. 이.. 2021. 11. 21. 백준 1932번 정수 삼각형(JAVA) 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 .. 2021. 10. 28. 유니온 파인드(Union find) 알고리즘 개념 유니온 파인드란 합집합 찾기라는 의미로, 상호 배타적 집합(Disjoint set)이라고도 한다. 여러 노드가 존재할 때, 두 개의 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 해당 알고리즘은 find와 union 연산으로 이루어지며, find는 a가 어떤 집합에 포함되어 있는지 부모를 찾는 연산이고, union은 a와 b가 포함되어 있는 집합을 합치는 연산이다. 설명 노드 번호 1 2 3 4 5 부모 노드 1 2 3 4 5 만약 위와 같이 독립된 노드들이 있을 때 각 노드의 부모는 자기 자신이다. 노드 번호 1 2 3 4 5 부모 노드 1 1 3 4 5 이때 1과 2번 노드를 합친다(union)고 생각해보자. 부모를 합칠 때는 일반적으로 더 작은 노드를 기준으로 합치기 때문에 2의 .. 2021. 10. 10. 코딩테스트 SQL 문법 정리 SELECT 모든 레코드 조회하기 - 오름차순 select * from 테이블명 order by 정렬기준컬럼 asc; - 내림차순 select * from 테이블명 order by 정렬기준컬럼 desc; 조건없는 특정 컬럼 조회하기 select 컬럼명 from 테이블명; 조건있는 특정 컬럼 조회하기 - 값이 일치하는 행 가져오기 select 컬럼명 from 테이블명 where 컬럼명 = "값"; - 값이 일치하지 않는 행 가져오기 select 컬럼명 from 테이블명 where 컬럼명 != "값"; 여러 기준으로 정렬하기 select * from 테이블명 order by 컬럼명1 asc, 컬럼명2 desc; 상위 N개 조회하기 select * from 테이블명 order by 컬럼명 limit N; MA.. 2021. 10. 9. 이전 1 2 3 4 5 6 7 다음
