본문 바로가기

알고리즘

백준 9934번 : 완전 이진 트리 [Python]
🖥️ 오늘의 백준 2023. 5. 27. 백준 9934번 : 완전 이진 트리 [Python] https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 첫 실버 1 .... 진짜 ㅠㅠ 너무 어려웠다 풀이들을 찾아봤지만 이해가 안갔음 그래서 그냥 내 방식대로 무작정 풀었다.. 중위순회를 거꾸로 하는 것이라는 거는 이해는 했지만 구현을 못하겠어서 포기. 그냥 규칙 찾아서 규칙대로 끼워넣었다. 풀이 설명 깊이 K를 입력 받고 K를 이용하여 노드의 개수를 구한다. 2**K -1개 빌딩에 들어간 순서를 input_tree 리스트에..
💡알고리즘 2023. 5. 21. [알고리즘] DP(Dynamic Programming: 동적 계획법) 알고리즘 DP (동적 계획법) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고 그 결과를 이용하여 다시 큰 문제를 해결할 때 사용하는 것 DP가 적용되기 위해선 1. 겹치는 부분이 존재해야한다. 문제를 작은 문제로 나누고 그 결과값을 저장한다. 저장한 값을 재활용하여 전체의 답을 구할 수 있을 때 사용한다. 즉, 겹치는 부분이 존재하지 않는다면 결과값을 저장해도 쓸모가 없기 때문에 dp를 사용할 수 없다. 2. 최적 부분 구조 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야한다. 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성된 문제 구조를 말한다. DP 적용 방법 DP는 점화식의 연속이다. 점화식을 진행하는 방식에는 2가지가 있다. 1. ..
[알고리즘] 그리디(Greedy: 탐욕) 알고리즘
💡알고리즘 2023. 5. 20. [알고리즘] 그리디(Greedy: 탐욕) 알고리즘 Greedy : 탐욕스러운 선택의 순간에서 가장 탐욕스러운 최적의 상황만을 쫓아 해답에 도달하는 방법 ⚠️ 그 순간에서는 최적일 수 있지만 종합적으로 보았을 때 최적이라는 보장은 절대 없다. ex ) 마시멜로 실험에서 지금 마시멜로를 먹지않고 기다린다면 2개를 먹을 수 있는 더 좋은 결과가 있지만 그리디 방법으로는 지금 당장 눈앞에 마시멜로 1개를 먹는 것이 더 최적이라고 판단하게됨 (미래를 보지 않고 현재에서 판단함 ) 그리디 알고리즘 방법 선택 절차 : 현재 상태에서 최적의 해답을 선택 적절성 검사 : 선택한 해가 문제의 조건을 만족하는 지 해답 검사 : 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 다시 1번 선택절차로 돌아가 위의 과정 반복 💡탐욕 알고리즘은 앞의 선택이 이후의 선택에 영향을..
[자료구조] 트리 (Tree)
💡알고리즘 2023. 5. 12. [자료구조] 트리 (Tree) 트리 정점과 간선을 이용하여 데이터의 배치 형태를 나타낸 자료구조 ex ) 힙을 구현하는 방법 중 하나이다. 기본용어 A,B,C,D,..., J는 트리의 구성요소인 노드이다. A는 최상위 노드인 루트 노드다. B 노드를 기준으로 보자면 B의 부모 노드는 A 노드 B의 자식 노드는 D,E 노드이다. 노드와 노드를 잇는 선은 edge이다. 자식이 없는 노드는 leaf 노드이다. 부모가 같은 F, G 노드는 형제 노드이다. 트리의 특징 각 항목들을 계층적으로 구조화할 때 사용하는 비선형 자료 구조이다. 부모, 자식의 계층적인 관계로 표현된다 (리스트는 그냥 나열) 트리는 데이터를 저장하기 보다는 데이터를 탐색하는데 사용된다. 루트 노드를 제외한 모든 노드들은 하나의 부모노드를 가진다. 사용 계층적 데이터를 저..
백준 1003번 : 피보나치 함수 | 메모이제이션, dp 알고리즘 [C++]
🖥️ 오늘의 백준 2023. 4. 28. 백준 1003번 : 피보나치 함수 | 메모이제이션, dp 알고리즘 [C++] https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 주어진 피보나치 함수에서 n이 0일때, 1일때의 경우에 count를 증가시켜서 0과 1의 호출 수를 확인하였다. => 시간초과 실패 원인 피보나치 함수가 재귀함수라서 계속해서 함수를 호출하게 되므로 시간초과가 일어남 해결 1. 계산했던 값은 미리 저장해두고 또 필요하면 꺼내서 쓰기 => 메모이제이션 기법 메모이제이션 memoization : 계산을 반복적으로 해야할 때 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 실행 속도를 빠르게 해주는 기법이다. (피보나치 수열 계산 시 ..

티스토리툴바