본문 바로가기

알고리즘24

[BOJ 1068 파이썬] 파이썬 트리 BFS 풀이 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 이 문제를 처음 보자마자 든 생각은 BFS로 풀면 되지 않을까? 였다. 먼저, 지워질 노드를 고려하지 않고 모든 노드들을 edge로 연결해주어 그래프를 만들어주었다. 이후, BFS로 탐색 하되 삭제한 노드로는 탐색하지 않게끔 예외를 주고, 부모노드가 삭제되었을 때의 예외를 해주었다. 루트노드는 연결 edge가 하나 밖에 없으므로 탐색시 연결 edge가 하나라면 답에 더해주었다. 그래서 처음 완성한 코드가 from collections import deque.. 2022. 6. 21.
[알고리즘] 브루트포스(brute force) 기법 정리 Goal 1. 브루트포스 알고리즘이 무엇인지에 대하여 정확히 이해한다. 2. 브루트포스 알고리즘이 쓰이는 문제의 종류에 대하여 정리한다. 브루트포스(brute force) 알고리즘이란? 브루트포스 알고리즘이란, 완전 탐색 알고리즘을 말한다. 즉, 가능한 모든 경우의 수를 탐색하면서 조건문을 통해서 요구조건이 충족되는 결과를 도출해 낸다. 모든 경우의 수를 탐색한다 -> 예외 없이 100%확률로 답을 가져올 수 있다. - 알고리즘 설계의 가장 근본적인 방법은 해가 있을 곳을 예상해서 탐색하는 것이다. - 브루트포스 알고리즘은 전체 구역을 탐색한다. - 전체 구역을 탐색하는 방법은 선형구조를 전체 탐색하는 순차 탐색 (반복문을 통한 전체 순차 탐색), 비선형 구조를 전체 탐색하는 DFS(깊이 우선 탐색), .. 2022. 2. 23.
[JAVA] 스택(Stack) Goal - 스택(Stack)의 각 함수의 시간복잡도를 구할 수 있다. - 자바로 스택(Stack)을 구현할 수 있다. 스택(Stack)의 개념 LIFO(Last in First Out) 구조의 선형 자료구조 즉, 가장 최근에 넣은 데이터만 pop()을 통해서 뽑아낼 수 있다. 스택(Stack)의 함수 push() public E push(E item) { addElement(item); return item; } 자바 라이브러리에서 구현한 함수를 봤을때, 우선 Generic을 사용해서 여러 자료형의 Data 혹은 객체가 Stack에 들어올 수 있게 해주었고, 부모 클래스인 Vector에 있는 addElement를 통해서 데이터를 push하고 있는 것을 알 수 있다. 단순 데이터를 맨마지막에 집어넣는 작.. 2022. 2. 19.
정렬 알고리즘 정리 버블 정렬이란? 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 인덱스를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 선택 정렬과 기본 개념이 유사하다. 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 위 과정이 마치 거품이 차오르는 것처럼 정렬이 된다고 하여 버블정렬이.. 2021. 10. 31.

티스토리툴바