몽상실현개발주의

[BOJ] 1967 / 트리의 지름 / Python 파이썬 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 전날 풀었던 [BOJ] 1167 / 트리의 지름 / Python 파이썬 문제와 같이 Tree 의 지름을 구하는 문제이다. 다시 복습하자면, Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로 선형 시간내에 Tree 의 지름을 구하는 Algorithm 트리에서 임의의 정점 xx..

[BOJ] 1167 / 트리의 지름 / Python 파이썬 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 Tree 의 지름을 구하는 문제이다. 문제를 선형시간안에 풀기위해서는 Tree 의 지름과 구하는 알고리즘에 대한 사전 지식이 필요하였다. Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로 선형 시간내에 Tree 의 지름을 구하는 Algorithm 트리에서 임의의 정점 xx를 잡..

[알고리즘 기초] 09_SW 문제해결 응용_2 / Python 1. 완전 검색 & 그리디 1.1 반복과 재귀 반복(Iteration)과 재귀(Recursion) 반복과 재귀는 유사한 작업을 수행할 수 있다. 반복은 수행하는 작업이 완료 될때까지 계속 반복 루프(for, while 구조) 재귀는 주어는 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 하나의 방법 하나의 큰 문제를 해결할 수 잇는 (해결하기 쉬운) 더 작은 문제로 쪼개고 그 결과들을 결합한다. 재귀 함수로 구현 반복 구조 초기화 반복되는 명령문을 실행하기 전에 조건 검사에 사용할 변수의 초기값 설정 조건검사 반복할 명령문 실행 업데이트 무한루프가 되지 않게 조건이 거짓이 되게 한다 재귀적 알고리즘 재귀적 정의는 두 부분으로..

[BOJ] 11725 / 트리의 부모 찾기 / Python 파이썬 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 각 node의 root를 찾는 문제이다. 최상단의 root 노드가 항상 1로 시작하기 때문에, 모든 edge 를 기록한뒤 1부터 Tree 를 내려가며 root 를 기록하였다. from collections import deque N = int(input()) graph = [[] for _ in range(N+1)] for _ in range(N-1): f, t = map(int, inpu..

[BOJ] 1991 / 트리 순회 / Python 파이썬 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 풀이 트리 순회의 기본 문제이다. 전위 순회(pre-order): Root -> Left -> Right 중위 순회(in-order): Left -> Root -> Right 후위 순회(post-order): Left -> Right -> Root N = int(input()) tree = {} for _ in range(N): nod..

[알고리즘 기초] 08_SW 문제해결 응용_1 / Python 1. SW 문제 해결 문제 해결 역량 프로그램을 하기 위한 많은 제약조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력 프로그래머가 사용하는 언어나 라이브러리, 자료구조, 알고리즘에 대한 지식을 적재적소에 퍼즐을 배치하듯 이들을 연결하여 큰 그림을 만드는 능력 추상적인 기술 훈련이 필요하다 문제 해결 과정 문제를 읽고 이해한다. 문제를 익숙한 용어로 재정의 한다. 어떻게 해결할지 계획을 세운다. 계획을 검증한다. 프로그램으로 구현한다. 어떻게 풀었는지 돌아보고, 개선할 방법을 찾는다. 문제 해결 전략 직관과 체계적인 접근 2. 복잡도 분석 알고리즘 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다. 주로 컴퓨터용어로 쓰이며, 컴퓨터..

[알고리즘 기초] 07_Tree / Python Tree 트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층 관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 트리의 정의 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다 노드 중 최상위 노드를 root 라 한다. 나머지 노드들은 n(>=0) 개의 분리 집합 T1, ..., TN 으로 분리될 수 있다. 이들 T1, ..., TN 은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리 (subtree)라 한다. 트리의 용어 노드(node) - 트리의 원소 간선(edge) - 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드(root node) - 트..

[알고리즘 기초] 06_Queue / Python Queue Queue 의 특성 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조 선입선출구조 (FIFO : First In First Out) 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제 된다. 큐의 기본 연산 삽입 : enQueue() ( Queue의 Rear 동작 ) 삭제 : deQueue() ( Queue의 Front 동작) 생성 : createQueue() 공백 확인 : isEmpty() 포화 확인 : isFull() 삭제 없이 원소 반환 : Qpeek() 1. 선형 큐 1차원 배열을 이용한 큐 큐의 크기 = 배열의 크기 front : 저장..