목록알고리즘 (6)

율코딩

[알고리즘] 백준 2110번 문제

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이문제는 이진탐색을 활용하여 푸는 문제이다. 반복적으로 gap을 설정하여 c개 이상의 공유기를 설치할 수 있는 경우를 찾는다. 먼저,start, end를 설정하여 최소 gap과 최대 gap 을 설정한다. 예제를 활용하여 코드를 구현해 보자. n,c = 5,3 arr = [1,2,4,8,9] start = arr[1] - arr[0] end = a..
알고리즘/백준 2022. 9. 25. 17:56
[알고리즘] 키로거 5397번

https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 이 문제는 스택을 활용하여 푸는 문제이다. 이 문제의 아이디어는 스택을 2개를 만들어서 커서를 스택 2개의 중간지점이라고 생각하면 된다. 데이터를 삽입하면 왼쪽 스택에 데이터를 넣는다. '-'가 나오면 왼쪽 스택에 마지막 원소를 뺀다. ''가 나오면 반대로 오른쪽 스택에서 왼쪽 스택으로 원소를 옮기면 된다. 이 방식으로 코드를 구현하면 아래처럼 구현된다. n=int(input()) for ..
알고리즘/백준 2022. 8. 15. 19:25
[자료구조] 퀵정렬 VS 병합정렬

퀵 정렬 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘 기준값(Pivot)을 중심으로 자료를 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다. 왼쪽 부분집합으로 기준값보다 작은 원소를 이동시키고, 오른쪽 부분집합으로 기준값보다 큰 원소를 이동시킨다. 퀵 정렬은 분할과 정복(Divide and Conquer)라는 작업을 반복하여 수행한다. 특징 기본적으로 지원되는 내장 정렬 함수는 대부분은 퀵 정렬을 기본으로 한다. 성능은 pivot 값을 어떻게 선택하느냐에 따라 크게 달라질 수 있음. 시간 복잡도: 최선의 경우 O(NlogN), 최악의 경우 O(N^2) 활용 케이스 메모리가 부족하고(병합정렬 사용 불가)할 경우 배열이 이미 정렬/역정렬되어있을 가능성이 없고(퀵..
자료구조 2022. 8. 15. 19:01
[알고리즘/백준] N과 M(1) 백트래킹 문제 풀이

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 1부터 N중 하나를 선택한 뒤 다음 1부터 N부터 선택할 때, 이미 선택한 값이 아닌 경우 선택 M개를 선택 할 경우 프린트 아이디어 백트래킹 재귀함수 안에서 for 문 돌면서 숫자 선택 ( 이 때 방문여부 확인) 재귀함수에서 M개를 선택할 경우 print 시간복잡도 N!: 중복이 불가, N = 10까지 가능 자료구조 방문 여부 : bool[] 선택한 값 입력 배열: int[] n,m..
알고리즘/백준 2022. 5. 29. 18:50
[알고리즘] 백트래킹(Backtracking)이란?

백트래킹(backtracking) : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 알고리즘 문제 모든 경우의 수를 확인해야할 때 for로는 확인이 불가능 한 경우 (깊이가 달라질 때) 백준 15649 N과 M(1) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://hyeyul-k.tistory.com/11
알고리즘 2022. 5. 29. 18:18
[MySQL/HackerRank] SQL Project Planning 문제 풀이

https://www.hackerrank.com/challenges/sql-projects/problem SQL Project Planning | HackerRank Write a query to output the start and end dates of projects listed by the number of days it took to complete the project in ascending order. www.hackerrank.com 이번 문제는 문제 자체가 어렵다기 보다는 접근 방식이 어려웠다. 나는 결국 풀지 못하고 Discussion을 보고 이해하였는데, 굉장히 단순하면서도 색다르게 느껴졌다. Start_Date 중 End_Date에는 없는 Start_Date는 각 연속적이지 않으므로..
SQL/HackerRank 2022. 5. 22. 17:43
Prev 1 Next