코딩테스트/자료구조∕알고리즘
[알고리즘] 복잡도, 빅오(Big-O) 표기법
알고리즘 어떠한 주어진 문제를 풀기위한 절차나 방법을 말한다. 컴퓨터 프로그램을 기술함에 있어 실행 명령어들의 순서를 의미한다. 조건 입력 : 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다. 출력 : 알고리즘은 최소 1개 이상의 결과를 가진다. 유한성 : 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다. 명확성 : 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다. 효과성 : 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간안에 정확하게 수행할 수 있을 정도로 충분히 단순해야한다. 종류 / 문제유형 그리디 알고리즘 (욕심쟁이 알고리즘, Greedy Algorithm) 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘 "매 선택에서 지금 이..
DFS (Depth-First Search) : 깊이 우선 탐색
DFS (Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조 혹은 재귀함수를 이용하며, 구체적으로 다음과 같이 동작한다. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고, 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. Java import java.util.*; public class test { //변수 생성 public static boolean[] visited = new boolean[9]; public stat..
[알고리즘] 트리와 이진트리 - 이진트리(Binary Tree) 검색
이번 코딩테스트 문제는 이진검색을 활용해서 풀어야한다고 해서 이론공부를 먼저 하고, 관련된 실습문제를 따라 작성해보았다. 이진트리 이론은 이해했지만, 자바코드로 구현하려니 머리가 멍해졌다. 💭 자바코드로 구현할 때 노드 자체를 써 본 경험이 적어서 그런것 같아 이번기회에 정리하고 익숙해지려고 한다. 1. 트리(Tree) 트리는 노드(Node)들과 이 노드들을 연결하는 링크(link)로 구성되며 계층적 구조를 표현할 때 사용된다. 조직도 디렉토리와 서브디렉토리 구조 가계도 트리(Tree) 의 기본 성질 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다. 트리 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두 번 이상 방문하지 않는다는 조건..