목록백준 (4)

율코딩

[알고리즘] 백준 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
[알고리즘/백준] 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
Prev 1 Next