본문 바로가기

Algorithm705

[Algorithm] 백트래킹(Backtracking): 안될 싹은 미리미리 가지치기 DFS 탐색 중 가능성이 없는 방향은 가지 않는 '백트래킹' 기법에 대해서 알아보겠습니다. [ Contents ] 1. DFS 2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. DFS(Depth First Search) 깊이 우선 탐색(DFS): 방문하지 않은 인접. star7sss.tistory.com 깊이 우선 탐색(DFS): 방문하지 않은 인접 노드가 없을 때까지 탐색하여 한 곳씩 마무리하는 방식 DFS는 끝이 나올.. 2022. 3. 20.
[탐색/Brute Force] 백준 1107 리모컨 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 2. 문제 풀이 100번에서 원하는 채널(N)로 전환하기위해 리모컨 버튼을 눌러야 합니다. 위아래로 이동할 수 있는 화살표와 0~9번까지의 버튼이 있습니다. 이 중 숫자버튼 일부가 고장났을 때, 눌러야 할 버튼의 최소 횟수를 구하는 문제입니다. 2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법? [Algorithm] 브루트 포스(.. 2022. 3. 20.
[탐색/BFS] 백준 9019 DSLR - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 2. 문제 풀이 D: (N*2) % 10000 S: N-1, 단 0이면 9999 L: 왼쪽으로 회전 R: 오른쪽으로 회전 최소의 DSLR 연산으로 A가 B가 되도록 만드는 문제입니다. 개인적으로 DP로도 풀 수 있을 거 같은데, 중복되는 수가 많이 안 나올 거 같아서 효율은 보장 못하겠네요. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터.. 2022. 3. 19.
[구현/문자열] 백준 2495 연속구간 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2495번: 연속구간 여덟 자리의 양의 정수가 주어질 때, 그 안에서 연속하여 같은 숫자가 나오는 것이 없으면 1을 출력하고, 있으면 같은 숫자가 연속해서 나오는 구간 중 가장 긴 것의 길이를 출력하는 프로그램을 www.acmicpc.net 2. 문제 풀이 같은 숫자가 연속해서 나오는 최대 길이를 구하는 문제입니다. 이전 글자와 같은지 판별한 뒤, 연속 횟수를 세주면 됩니다. 3. 코드 #입력 for _ in range(3): s = input() len_max = 0 #가장 긴 길이 cnt = 1 #같은 숫자가 나온 횟수 for i in range(1, len(s)): #전과 같으면 +1, 다르면 1로 초기화 if s[i-1] == s[i]: cnt +=.. 2022. 3. 18.
[자료구조/큐] 백준 5430 AC - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 2. 문제 풀이 1) R: 정수배열 뒤집기 2) D: 첫 번째 수 버리기 (단, 빈 배열이면 Error) 두 연산을 수행하는 자료구조를 만들어야 합니다. 배열의 크기가 최대 100000이고, R연산이 최대 100000번 일어날 수 있습니다. 따라서 R연산마다 배열을 뒤집으면 시간 초과가 납니다. 2022.02.10 - [Algorithm] - [Algorithm] 큐(Queue), 선입선출 줄서기 자료구조 [Algorithm] 큐(Queue), 선입선출 줄서기 자료구조 .. 2022. 3. 17.
[탐색/플로이드] 백준 11404 플로이드 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2. 문제 풀이 플로이드 알고리즘을 이용해서 최단경로를 탐색하는 문제입니다. 2022.02.28 - [Algorithm] - [Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기 [Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기 모든 쌍의 최단 경로를 '플로이드 - 와샬' 알고리즘으로 구하는 방법을 알아보고, 구현 코드도 살펴보겠습니다. [ Contents ] 1. 모든 쌍의 최단 경로 위 .. 2022. 3. 16.
[구현/그리디] 백준 2810 컵홀더 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net 2. 문제 풀이 컵홀더를 사용할 수 있는 사람의 수를 구하는 문제입니다. 좌석은 S(싱글)과 LL(커플)석이 있습니다. 커플석 사이에는 컵홀더가 없기 때문에, 자칫 컵홀더를 사용하지 못하는 사람이 나올 수 있습니다. (커플이 문제) *S*LL*LL*S*S*LL* 위 예시에서는 2명이 컵홀더를 사용하지 못합니다. 2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 경주마들을.. 2022. 3. 16.
[구현/문자열] 백준 15904 UCPC는 무엇의 약자일까? - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 2. 문제 풀이 주어진 문장을 축약해서 UCPC를 만들 수 있는지 판별하는 문제입니다. 3. 코드 #입력 s = input() find = 'UCPC' #찾아야할 문자열 idx = 0 for i in s: # 해당 글자를 찾았으면 다음 글자로 넘어감 if i == find[idx]: idx += 1 # UCPC를 모두 찾았으면 끝내기 if idx == 4: print("I love UCPC").. 2022. 3. 15.
[탐색/구현] 백준 14500 테트로미노 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 2. 문제 풀이 테트릭스 모양으로 탐색한 뒤, 가장 점수를 출력하는 문제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. .. 2022. 3. 14.

티스토리툴바