본문 바로가기
728x90
반응형

알고리즘109

재귀, DFS 알고리즘하면서 재귀의 중요성을 알려준 DFS. 하지만 어려워서 계속 까먹는다. 그래서 이번에 정리를 아예 해둘려고 한다. 재귀를 쓰는 이유 뭐 사실 알고리즘 시간에서는 특정 케이스를 제외하면 시간복잡도나 효율면에서 떨어진다고 학습을 하기 마련이다. 하지만 재귀를 사용하면 수많은 for문을 사용해야되는 경우, 복잡한 코드 같은 경우를 손 쉽게 구현할 수 있다. 종만북에서 n 개의 서로 다른 원소a 중 x 개의 원소를 순서를 고려해서 뽑는 경우의 수를 구한다면, x개만큼의 반복문이 필요하기 때문 재귀함수를 잘 사용할려면 문제를 소문제로 잘 분리 시켜야된다. 간단한 아래 예시를 보자 아래는 중복순열을 구하는 재귀함수코드이다. 이 코드의 핵심은 트리를 만들면서 진행한다는 소리인데 이게 아는 사람들은 금방 이해하.. 2024. 4. 6.
[백준] 2920번: 음계 - python https://www.acmicpc.net/problem/2920 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 금공강의 힐링을 즐기며 누워서 브론즈 문제 한 문제로 일상 시작. 쉬운 문제지만 O(n)로 짤려고 생각했다. arr1 = [1,2,3,4,5,6,7,8] arr2 = [8,7,6,5,4,3,2,1] arr = list(map(int, input().split())) cnt1 = 0 cnt2 = 0 for i in range(8): if arr[i] == a.. 2024. 4. 5.
[백준] 11279번: 최대 힙 - python https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 최소 힙 풀었더니 옆에 연관문제라고 떠서 봤는데 날로 먹는 최대 힙 문제였다ㅎㅎ 행복하게 - 두개 붙이고 통과 import heapq import sys input = sys.stdin.readline n = int(input()) hq = [] for i in range(n): m = int(input()) if m: heapq.heappush(hq, -m) else: i.. 2024. 4. 5.
[백준] 1927번: 최소 힙 - python https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 힙 자료구조를 잘 사용할 수 있는지 테스트하는 문제 ^^ 전에 회의실 문제에서 사용해서 익숙해서 쉽게 풀었다. import heapq import sys input = sys.stdin.readline n = int(input()) hq = [] for i in range(n): m = int(input()) if m: heapq.heappush(hq, m) else: if h.. 2024. 4. 5.
728x90
반응형

티스토리툴바