[파이썬] 백준 4344: 평균은 넘겠지

[파이썬] 백준 4344: 평균은 넘겠지

문제 출처 https://www.acmicpc.net/problem/4344 나의 코드 import sys input = sys.stdin.readline c = int(input()) cases = [[x for x in map(int, input().strip().split())] for _ in range(c)] for case in cases: population = case[0] scores = case[1 : len(case)] score_avg = sum(scores) / population above_avg = 0 for score in scores: if score > score_avg: above_avg += 1 result = above_avg * 100 / population pri..

  • format_list_bulleted 프로그래밍/자료구조와 알고리즘
  • · 2024. 4. 3.
Memory Layout of Programs (프로세스의 메모리 구조)

Memory Layout of Programs (프로세스의 메모리 구조)

메모리구조 영역의 구분 정적할당과 동적할당을 담당하는지 여부에 따라 영역을 구분합니다. 정적할당의 경우 text segment과 bss segment, data segment가 담당하고 동적할당의 경우 stack segment과 heap segment가 담당합니다. 정적할당 정적할당이란 컴파일 단계에서 메모리를 할당하는 것입니다. text segment(텍스트 영역) text segment은 메모리에 올라간 실행 중인 프로그램의 영역입니다. text segment은 실행 가능한 instruction들이 들어가 있습니다. 텍스트 영역은 오작동을 막기 위해 읽기만 가능합니다. initialized data segment(초기화 된 데이터 영역) 전역변수와 정적 변수 중에 초기화 된 변수들이 존재하는 영역을 ..

  • format_list_bulleted 프로그래밍/자료구조와 알고리즘
  • · 2024. 4. 2.
다익스트라 알고리즘

다익스트라 알고리즘

다익스트라 알고리즘 개념 사용환경 가중치 그래프에서 시작점과 도착점이 주어졌을 때 최단 경로를 찾는 알고리즘 원리 방문할 수 있는 노드 중에 가장 비용이 작은 곳(우선순위가 높은 곳)을 방문 1. 우선순위 큐에 시작노드 추가 2. 우선 순위가 가장 높은 노드 추출 3. 방문 여부 확인 4. 비용 업데이트 5. 현재노드와 연결된 노드를 우선순위 큐에 추가 6. 목적지에 기록 된 비용 반환구현 다익스트라 알고리즘 import heapq def dijkstra(graph, start, final): costs = {} pq = [] heapq.heappush(pq, (0, start)) while pq: cur_cost, cur_v = heapq.heappop(pq) if cur_v not in costs: ..

  • format_list_bulleted 프로그래밍/자료구조와 알고리즘
  • · 2024. 4. 2.
우선순위 큐

우선순위 큐

우선순위큐 개념 정의 우선순위큐는 들어온 데이터의 우선순위에 따라 데이터를 꺼내는 자료구조입니다. 큐는 들어온 순서에 따라 데이터를 꺼내는 반면에 우선순위큐는 우선순위에 따라 데이터를 꺼냅니다. 우선순위 큐는 3가지 방식으로 구현할 수 있습니다. ① 배열 ② 연결리스트 ③ 힙으로 구현할 수 있습니다. 배열과 연결리스트의 경우, 정렬의 유무에 따라 데이터 처리의 시간복잡도가 O(N) ~ O(NlogN)이나 힙의 경우 O(logN)으로 동일합니다. 따라서 우선순위큐는 힙으로 구현합니다. 힙 자료구조 구현 힙 자료구조는 완전이진트리의 한 형태로 리프노드를 제외한 모든 노드들이 점유되어 있고 자식노드는 왼쪽부터 채워지는 구조입니다. 완전이진트리의 특징은 다음과 같습니다. 1. 리프노드를 제외한 모든 레벨에 노드..

  • format_list_bulleted 프로그래밍/자료구조와 알고리즘
  • · 2024. 4. 2.
[백준] 5639: 이진 검색 트리 파이썬

[백준] 5639: 이진 검색 트리 파이썬

문제요약 이진탐색트리의 전위순회환 결과를 토대로 해당 트리를 후위순회한 결과를 출력하는 문제입니다. 나의 접근법 1) 전위순회를 통해 이진검색트리를 재현하기 2) 이진검색트리를 후위순회하여 그 순서를 출력하기 활용한 개념 1) 이진탐색트리 코드의 구현 이진탐색트리 def add(self, data: int): """데이터 추가하기""" if self.root is None: self.root = Node(data) return current = self.root while True: if current.value < data: if current.right is None: current.right = Node(data) break current = current.right elif current.valu..

  • format_list_bulleted 프로그래밍/자료구조와 알고리즘
  • · 2024. 3. 30.
트리의 구현

트리의 구현

배열로 트리 구현 이진트리를 배열로 표현할 수 있습니다. 부모노드와 자식노드는 다음의 인덱스 관계를 갖습니다. [배열활용] 부모노드와 자식노드의 인덱스 관계 부모노드의 인덱스: n 자식노드의 인덱스: 2*n + 1, 2*n + 2[배열활용] 부모-자식 노드의 관계 표현 my_tree = [&#39;A&#39;,&#39;B&#39;,&#39;C&#39;,&#39;D&#39;,&#39;E&#39;,&#39;F&#39;,None,&#39;G&#39;] i = 0 n = len(my_tree) while i < n: if my_tree[i]: print(f"Parent: {my_tree[i]}", end=&#39;, &#39;) left = 2 * i + 1 right = 2 * i + 2 if left < n..

  • format_list_bulleted 프로그래밍/자료구조와 알고리즘
  • · 2024. 3. 30.