helloahram

1. 문제00과 1로 이루어진 타일을 붙여 길이가 n인 모든 2진 수열의 개수를 구하고그 값을 15746로 나눈 나머지를 출력하는 문제 2. 요구사항시간 제한 0.75초 메모리 제한 256MB1 3. 알고리즘 분류* 다이나믹 프로그래밍4. 접근 방식처음에는 n = 7 까지 모든 경우의 수를 계산해 봤는데, 알고보니 피보나치 수열이었다그리고 같은조 ㅎㅇ님이랑 얘기하며 알게된 내용인데, 아래와 같은 사실을 알게 되었다1) 타일은 00 과 1 로 구분할 수 있다2) 그래서 n == 3 이상일 때◻️◼️◼️ 한 칸만 비어있는 경우는 빈 칸에 1 이 들어가고 ◻️◻️◼️ 두 칸이 비어있는 경우는 빈 칸에 00 이 들어간다고 생각하면n == 3 이상 일 때는 n-1 과 n-2 의 합이다(◻️◼️◼️ / ◼️◼️◻️..

1. 문제n 이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), 0  2. 알고리즘 분류* 수학* 다이나믹 프로그래밍 3. 접근 방식n 이 90까지라서 재귀로 풀면 시간 초과가 뜬다는 말을 듣고,어제 공부했던 Dynamic Programming 의 메모이제이션을 활용하여 구현해 보았다메모이제이션 - 이전 결과 값을 저장하여 중복 계산을 피하는 것  4. 코드 구현 def fibo(n): if n

1. 문제그래프를 DFS 로 탐색한 결과와 BFS 로 탐색한 결과를 출력하는 프로그램을 작성하시오 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V M 개의 줄에는 간선이 연결하는 두 정점의 번호가 주어지고, 입력으로 주어지는 간선은 양방향이다1 2. 알고리즘 분류* 그래프 이론* 그래프 탐색* 너비 우선 탐색* 깊이 우선 탐색3. 접근 방식DFS (Stack 이용) 와 BFS (deque 이용) 를 공부한 김에 관련 문제를 풀어봤다DFS, BFS 개념 정리 [TIL] DFS 깊이 우선 탐색 BFS 너비 우선 탐색그래프를 탐색하는 방법에는DFS 깊이 우선 탐색과 BFS 너비 우선 탐색이 있다 그래프에 대한 설명은 그래프 종류와 표현 방식에 정리해 놨다 1. DFSDepth-First Se..

플로이드 와샬 Floyd Warshall 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘거쳐가는 정점을 기준으로 최단 거리를 구한다  플로이드 와샬 특징 1. 시작 정점과 도착 정점의 구분 없이 모든 경로에 대한 최단 경로를 구하는 데 사용된다2. 동적 계획법을 사용하여, 경로가 점차적으로 개선되면서 최단 경로를 찾는다3. 음수 가중치를 갖는 그래프에서도 동작하지만, 음수 사이클이 있으면 알고리즘이 제대로 동작하지 않는다  (음수 사이클 - 음수 가중치를 갖는 경로로 인해 무한히 작은 경로가 생기는 경우)4. 시간 복잡도 가 O(N^3) 으로, 정점의 수가 적을 때는 효율적이지만 정점 수가 많을 수록 비효율적일 수 있다 5. 인접 행렬로 표현하여 사용되며, 행렬의 각 값은 두 정점 사이의..

1. 문제1번부터 N번까지의 도시와 M개의 단방향 도로가 존재할 때 (모든 도로의 거리는 1이다)특정한 도시 X로부터 출발하여 최단 거리가 K인 모든 도시의 번호를 구하는 프로그램을 작성하시오2  2. 알고리즘 분류* 그래프 이론* 그래프 탐색* 너비 우선 탐색* 최단 경로* 데이크스트라 3. 접근 방식Week02 퀴즈 주제인 다익스트라를 이용하여 문제를 푸려고 한다 4. 전체 코드첫번째 시도 다익스트라 함수를 별개로 구현하고, N, M, K, X 를 입력 받아 딕셔너리 형태로 graph 를 만들었다 그리고 딕셔너리에서 items() 로 node 와 edge 를 꺼내 edge 와 K 를 비교해서 result list 에 append 하고, 나중에 .join() 으로 정리해서 print 했다import h..

다익스트라를 공부하는데 코드 구현에서 heapq 가 나와서 정리한다 힙큐 heapq최대값과 최소값을 찾는 연산에 특화된 완전 이진 트리 우선순위 큐를 위해 만들어 자료 구조이다  최소힙 Min Heap 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 것최대힙 Max Heap 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 것 힙큐는 최소힙 자료 구조를 이용한다  heapq 메서드1. heapq.heapify(iterable)원래 있던 리스트를 힙으로 사용하기 위해 힙화 (heapify) 진행Heapify 의 디폴트 값은 최소힙이다import heapqheap2 = [5, 2, 1, 3, 8]heapq.heapify(heap2)print(heap2) # 결과 출력 [1, 2, 5, 3, 8..

위상 정렬 Topology Sort순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘 사이클이 없는 DAG 에만 적용이 가능하다  DAG Directed Acyclic Graph 방향이 있는, 비순환적인 그래프대학교의 선후수 과목에 비유할 수 있다전자회로 과목은 회로이론과 기초전자회로실험 과목을 이수해야 수강이 가능하다 여기에서 회로이론과 기초전자회로실험의 수강 순서는 중요하지 않다  진입 차수와 진출 차수위상 정렬 동작 과정을 보기 전에 진입 차수와 진출 차수에 대한 개념을 먼저 알아 두어야 한다 진입 차수 Indegree 는 노드로 들어오는 간선의 개수이고진출 차수 Outdegree 는 노드에서 나가는 간선의 개수이다 위상 정렬 동작 과정1. 진입 차수가..

그래프를 탐색하는 방법에는DFS 깊이 우선 탐색과 BFS 너비 우선 탐색이 있다 그래프에 대한 설명은 그래프 종류와 표현 방식에 정리해 놨다 1. DFSDepth-First Search, 깊이 우선 탐색 최대한 깊이 내려가고, 더 이상 깊이 내려갈 곳이 없을 경우 옆으로 이동모든 노드를 방문하는 경우에 사용한다 * 스택 또는 재귀를 이용해서 구현 시간 복잡도 - 인접 리스트 O(V+E), 인접 행렬 O(V^2)   DFS 기본 원칙"앞으로 찾아 가야할 노드" 와 "이미 방문한 노드" 를 기준으로 데이터 탐색한다경로 찾기, 탐색 문제, 백트래킹, 사이클 탐지 등에 유용하다 DFS 코드 구현탐색 순서1 - 2 - 4 - 5 - 3 - 6 4 방문 후 2로 백트래킹하여 5를 방문하고, 다시 2 - 1로 백트래..

클래스 Class객체를 만들기 위한 설계도 (템플릿 역할)객체 Instance클래스를 기반으로 만들어진 구체적인 실체각 인스턴스는 클래스에서 정의한 속성과 메서드를 가진다 node_a = Node('A') # node_a 는 Node 클래스의 객체 self 의 역할1. 자기 참조 클래스 내에 메서드가 호출될 때, 그 메서드가 소속된 객체 자신을 참조한다 즉, 클래스의 인스턴스 (객체) 자신을 가리킨다 2. 객체의 속성과 메서드 접근self 를 통해 각 객체의 속성이나 메서드에 접근할 수 있다그래서 각 객체가 독립적으로 데이터를 저장하고 동작할 수 있다 class Node: def __init__(self, value): self.value = value # self.value 는 현재 객체의 va..

트리 Tree 노드들이 나무 가지처럼 연결된 비선형 계측적 자료 구조 트리 구조를 왜 사용하는가?선형 데이터 구조로는 계층형 구조를 나타낼 수 없기 때문에 트리의 구조는 '데이터 저장'의 의미보다는'저장된 데이터를 더 효과적으로 탐색'하기 위해 사용한다  트리의 구조 노드 Node트리를 구성하고 있는 기본 요소노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있다 간선 Edge노드와 노드 간의 연결선루트 노트 Root Node트리 구조에서 부모가 없는 최상위 노드부모 노드 Parent Node자식 노드를 가진 노드자식 노드 Child Node부모 노드의 하위 노드 형제 노드 Sibling Node같은 부모를 가지는 노드깊이 Depth루트에서 어떤 노드까지의 간선 Edge 수높이 Height어떤 노..