알고리즘
트리(Tree)
: 계층형 비선형 자료 구조
-
하나의 데이터에 밑에 밑에 어떤 값이 있는지 중요하다면 트리구조!
-
용어
Node: 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level -
종류 : 이진트리, 완전 이진 트리
-
표현방법
- 클래스 구현
- 배열 (완전 이진 트리 사용하는 경우)
- 트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용하지 않음 so None값 넣고 시작
-
높이: 루트노드 - 가장 아래 리프노트
이진트리(Binary Tree)
: 각 노드가 최대 두 개의 자식을 가진다.
o Level 0
o o o Level 1
o o o Level 2 # 이진 트리(X)
o Level 0
o o Level 1
o o o Level 2 # 이진 트리(O)완전 이진 트리(Complete Binary Tree)
: 노드를 삽입할 떄 왼쪽노드부터 차례대로 삽입
o Level 0
o o Level 1
o o Level 2 # -> 이진 트리 O 완전 이진 트리 X
o Level 0
o o Level 1
o o o Level 2 # -> 이진 트리 O 완전 이진 트리 O- 배열로 표현
None 값을 배열에 넣고 시작 [None]8 Level 0 -> [None, 8] 6 3 Level 1 -> [None, 8, 6, 3] 4 2 5 Level 2 -> [None, 8, 6, 3, 4, 2, 5]
- 구조분석
- 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스
- 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스
- 현재 인덱스 // 2 -> 부모의 인덱스
ex) 1번째 인덱스인 8의 왼쪽 자식은 6, 오른쪽 자식은 3
그러면 1 2 = 2번째 인덱스 == 6
그러면 1 2 + 1 = 3번째 인덱스 == 3
부모를 찾아보면,
3 // 2 = 1번째 인덱스 == 8
- 각 레벨에 최대로 들어갈 수 있는 노드의 개수 = 개
- 높이 h , 모든 노드가 차 있는 완전 이진트리의 모든 노드의 개수
= 1 + 2^1 + 2^2+ .....+ 2^h = - 최대 노드의 개수가 N이라면
따라서이진트리의 높이는 최대 $O(log(N)) $
힙heap
데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
- Max Heap: 상위레벨(큰 값)- 하위레벨(작은 값): 부모노드가 자식노드보다 큼
- Min Heap: 상위레벨(작은 값)-하위레벨(큰 값): 부모노드가 자식노드보다 작음
-> 최대값, 최솟값을 빠르게 구할 수 있음
Max Heap원소 추가
- 시간복잡도:
class MaxHeap:
def __init__(self):
self.items = [None]
def insert(self, value):
# 들어가는 노드 값 맨 마지막에 추가
# 부모노드와 비교-> 크면 바꿔 / 작으면 그대로 출력
# 꼭대기까지 반복
self.items.append(value)
curr_idx = len(self.items) -1 #현재 인덱스 값을 알아야 비교 가능
while curr_idx > 1:
parent_idx = curr_idx // 2
if self.items[curr_idx] > self.items[parent_idx]:
self.items[parent_idx], self.items[curr_idx] = self.items[curr_idx], self.items[parent_idx]
curr_idx = parent_idx
else:
break
return self.itemsMax Heap의 원소 제거 (루트노드 제거)
- 시간복잡도:
- 맨 나중에 넣은 원소만 제거할 수 있다
방법
- 루트 노드와 맨 끝에 있는 원소를 교체
- 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제
- 변경된 노드와 자식 노드들을 비교.
두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리 교체 - 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복
- 2에서 제거한 원래 루트 노드를 반환
class MaxHeap:
def __init__(self):
self.items = [None]
def insert(self, value):
self.items.append(value)
cur_index = len(self.items) - 1
while cur_index > 1: # cur_index 가 1이 되면 정상을 찍은거라 다른 것과 비교 안하셔도 됩니다!
parent_index = cur_index // 2
if self.items[parent_index] < self.items[cur_index]:
self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
cur_index = parent_index
else:
break
# 루트노드와 맨 끝 노드와 변경 --> 인덱스 필요 루트는 1, 맨 끝은 -1
# 맨 뒤 노드 삭제, 반환해줘야하니까 저장
# 자식노드 중 더 큰 애랑 비교 후 작으면 교체
# 크면 원
def delete(self):
self.items[1], self.items[-1] = self.items[-1], self.items[1]
prev_max = self.items.pop()
curr_idx = 1
while curr_idx <= len(self.items) -1:
left_child_idx = curr_idx * 2
right_child_idx = curr_idx * 2 +1
max_idx = curr_idx
if left_child_idx <= len(self.items) -1 and self.items[left_child_idx]> self.items[curr_idx]:
max_idx = left_child_idx
if right_child_idx <= len(self.items) -1 and self.items[right_child_idx]> self.items[curr_idx]:
max_idx = right_child_idx
if max_idx == curr_idx:
break
self.items[curr_idx], self.items[max_idx] = self.items[max_idx], self.items[curr_idx]
curr_idx = max_idx
return prev_max그래프
연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조. [천재학습백과]
-
연결관계에 초점
-
용어
노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다.
간선(Edge): 노드 간의 관계를 표시한 선.
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) -
종류
- 유방향 그래프: 방향이 있는 간선
- 무방향 그래프: 방향이 없는 간선
-
표현 방법
2 - 3
⎜
0 - 1
1) 인접 행렬(Adjacency Matrix): 2차원 배열로 연결 관계를 표현- 즉각적으로 연결 여부 알 수 있음 but 만큼의 공간 사용
0 1 2 3
0 X O X X
1 O X O X
2 X O X O
3 X X O X
이걸 배열로 표현하면
graph = [
[False, True, False, False],
[True, False, True, False],
[False, True, False, True],
[False, False, True, False]
]2) 인접 리스트(Adjacnecy List): 링크드 리스트로 연결 관계를 표현
- 만큼의 시간, 만큼의 공간 사용
0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2
딕셔너리로 표현하면
graph = {
0: [1],
1: [0, 2]
2: [1, 3]
3: [2]
}DFS (Depth First Search)
자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. [컴퓨터인터넷IT용어대사전]
- 끝까지 파고들어 탐색
- 공간을 적게 씀 but 최단경로 탐색은 어려움
- 과정
1) 노드를 방문하고 깊이 우선으로 인접한(엣지가 연결되어 있는) 노드를 방문한다.
2) 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
3) 만약 끝에 도달했다면 리턴한다.
- 반복되는 구조 -> 재귀함수
재귀함수 이용
graph = {
1: [2, 5, 9],
2: [1, 3],
3: [2, 4],
4: [3],
5: [1, 6, 8],
6: [5, 7],
7: [6],
8: [5],
9: [1, 10],
10: [9]
}
visited = []
#시작노드부터 시작
# 방문한 노드를 visited_array에 추가
# 방문한 노드와 인접한 방문하지 않은 노드 방문
def dfs_recursion(adjacent_graph, cur_node, visited_array):
visited_array.append(cur_node)
for adjacent_node in adjacent_graph:
if adjacent_node not in visited_array: #이게 탈출조건도 됨
dfs_recursion(adjacent_graph, adjacent_node, visited_array)- but 무한정 깊어지는 노드가 있는 경우 에러가 발생할 수 있음 ->스택
스택 이용
- 루트 노드를 스택에 넣는다.
- 현재 스택의 노드를 빼서 visited 에 추가한다.
- 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
- 2부터 반복한다.
- 스택이 비면 탐색을 종료한다.
def dfs_stack(adjacent_graph, start_node):
stack = [start_node]
visited = []
while stack: #스택이 비지 않았다면
curr_node = stack.pop()
visited.append(curr_node)
for adjacent_node in adjacent_graph[curr_node]:
if adjacent_node not in visited:
stack.append(adjacent_node)
return visitedBFS (Breadth First Search)
한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. [컴퓨터인터넷IT용어대사전]
- 갈라진 모든 경우의 수를 탐색한 후 다음 단계로
- 최단경로 탐색 쉬움, but 공간을 많이 씀
큐 이용
- 루트 노드를 큐에 넣는다
- 현재 큐의 노드를 빼서 visited 에 추가한다.
- 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
- 2부터 반복한다.
- 큐가 비면 탐색을 종료한다.
def bfs_queue(adj_graph, start_node):
queue = [start_node]
visited = []
while queue:
curr_node = queue.pop(0) #큐라서 0번째 인덱스를 빼는거임
visited.append(curr_node)
for adj_node in adj_graph[curr_node]:
if adj_node not in visited:
queue.append(adj_node)
return visited자바
문법
예외처리(Exception, Error Handling)
- 목적
- 예외의 발생으로 인한 실행 중인 프로그램의 비정상 종료를 막기 위해서
- 개발자에게 알려서 코드를 보완할 수 있도록 하게 위해서
- 자바에서는 상속을 이용해 모든 예외를 표현.
- 모든 예외 클래스는 Throwable의 자손 클래스
Throwable
Error: 프로그램이 종료되어야 하는 심각한 문제 표현Exception: 프로그램이 종료되지는 않지만 예외나 문제상황을 표현
- 기본은 자바에 미리 정의되어있는 예외 클래스를 사용하되,
필요한 것으로 표현할 수 없거나 구체적인 목적을 가진 예외를 정의하고 싶다면,
Throwable또는 그 하위에 있는 예외 클래스를 상속받아서 자신만의 예외 클래스를 정의
try-catch(-finally) 형식
try {
// 예외가 발생할 가능성이 있는 코드를 구현합니다.
} catch (FileNotFoundException e) {
// FileNotFoundException이 발생했을 경우,이를 처리하기 위한 코드를 구현합니다.
} catch (IOException e) {
// FileNotFoundException이 아닌 IOException이 발생했을 경우,이를 처리하기 위한 코드를 구현합니다.
} finally {
// 예외의 발생여부에 관계없이 항상 수행되어야하는 코드를 구현합니다. 필수는 아님.
}- 예외가 발생하지 않는다면 try->finally 순으로 실행
- 중복 catch블럭 사용 가능. 먼저 선언된 catch 블록 확인 후 잡혔다면 뒤의 블럭으로는 전파되지않음.
- 좁은 범위의 예외부터 앞에 선언하는 것이 좋음
- 상속관계에서 자식 클래스에 위치 할수록 좁은 범위임.
- 예를 들어서
IOException이 발생할 것 같아 예외처리를 하고, 그 외의 예외도 예외처리를 하고 싶다면IOException을 catch 하는 구문을 먼저,Exception을 catch하는 구문을 그 뒤에 작성
e.getMessage(): 에러의 원인을 간단하게 출력합니다.
try-with-resorce 형식
- 입출력과 함께 쓰이는 구문
-try()안의 입출력 스트림을 생성하는 로직을 작성할 때 해당 객체가 AutoClosable 인터페이스를 구현한 객체여야함
import java.io.FileOutputStream;
import java.io.IOException;
public class Main {
public static void main(String[] args) {
try (FileOutputStream out = new FileOutputStream("test.txt")) {
out.write("Hello Sparta".getBytes());
out.flush();
}catch (IOException e) {
System.out.println("IOException 발생" + e.getMessage());
e.printStackTrace();
}
}
}IOException: 데이터 읽기 쓰기 같은 데이터 입출력 문제가 있을 때 발생
FileOutputStream : byte단위로 파일을 기록하는 클래스.
->close()메소드로 닫아줘야 하지만 try-with-resource문은 try문을 벗어나는 순간 자동적으로 close()가 호출되기 때문에 여기선 입력을 안해도 됨.
예제
class ArrayCalculation {
int[] arr = { 0, 1, 2, 3, 4 };
public int divide(int denominatorIndex, int numeratorIndex) throws ArithmeticException, ArrayIndexOutOfBoundsException{
// divide()함수에서 발생할 수 있는 exception 종류를 throws 키워드를 사용하여 명시
return arr[denominatorIndex] / arr[numeratorIndex];
}
}
public class Main {
public static void main(String[] args) {
ArrayCalculation arrayCalculation = new ArrayCalculation();
System.out.println("2 / 1 = " + arrayCalculation.divide(2, 1));
try {
System.out.println("1 / 0 = " + arrayCalculation.divide(1, 0));
// java.lang.ArithmeticException: "/ by zero"
} catch ( ArithmeticException arithmeticException) {
System.out.println("잘못된 계산입니다." + arithmeticException.getMessage());
}
try {
System.out.println("Try to divide using out of index element = "
+ arrayCalculation.divide(5, 0)); // java.lang.ArrayIndexOutOfBoundsException: 5
} catch (ArrayIndexOutOfBoundsException arrayIndexOutOfBoundsException) {
System.out.println("잘못된 index 범위로 나누었습니다. 타당한 index 범위는 0부터" + (arrayCalculation.arr.length -1) + "까지입니다.");
}
}
}*denominator == 분모
*numerator == 분자
코드활용
날짜와 시간 다루기
import java.time.LocalDate; //자바 타임 패키지 임포트
import java.time.LocalDateTime;
import java.time.LocalTime;
public class Main {
public static void main(String[] args) {
System.out.println("now usages");
LocalDate date = LocalDate.now();
LocalTime time = LocalTime.now();
LocalDateTime dateTime = LocalDateTime.now();
System.out.println(date); // 2022-11-15
System.out.println(time); // 16:30:37.615
System.out.println(dateTime); // 2022-11-15T16:30:37.615
System.out.println("of() usage");
LocalDate dateOf = LocalDate.of(2022, 11,14);
LocalTime timeOf = LocalTime.of(22, 50, 0);
System.out.println(dateOf); // 2022-11-14
System.out.println(timeOf); // 22:50
}
}- formatter: 기본 형태에서 바꿔줌.
import java.time.LocalTime;
import java.time.format.DateTimeFormatter;
import java.time.format.FormatStyle;
public class Main {
public static void main(String[] args) {
DateTimeFormatter formatter = DateTimeFormatter.ofLocalizedTime(FormatStyle.SHORT);
String shortFormat = formatter.format(LocalTime.now());
System.out.println(shortFormat); //오후 4:37
}
}Ctrl누른 상태로 FormatStyle 클릭하면 설정 볼 수 있음
- 직접설정
public class Main {
public static void main(String[] args) {
DateTimeFormatter myFormatter = DateTimeFormatter.ofPattern("yyyy년MM월dd일");
String myDate = myFormatter.format(LocalDate.now());
System.out.println(myDate); //2022년11월15일
}
}- 날짜계산
import java.time.LocalDate;
import java.time.Period;
public class Main {
public static void main(String[] args) {
LocalDate today = LocalDate.now();
LocalDate birthday = LocalDate.of(2020,2,2);
Period period = Period.between(today, birthday);
System.out.println(period.getMonths()); //-9
System.out.println(period.getDays()); //-13
}
}프로그래머스_0단계_2주차
🔒분수의 덧셈
🔑 나의 답안
def solution(denum1, num1, denum2, num2):
numerator = denum1*num2 + denum2*num1
denominator = num1 * num2
for i in range(1, numerator + 1):
if (numerator % i == 0) & (denominator % i == 0):
gcd = i
return [numerator/gcd, denominator/gcd]- 처음에 최대공약수를 구하지 않고 값을 출력해서 정답이 안되었다.
- 최대공약수 구하는 방법을 구글링하는데 파이썬 내장함수 말고 방법을 알고싶었다.
- 물론 내장함수 방법도 있음
import math
def solution(denum1, num1, denum2, num2):
denum = denum1 * num2 + denum2 * num1
num = num1 * num2
gcd = math.gcd(denum, num)
return [denum//gcd, num//gcd]
gcd(num1, num2): num1과 num2의 최대공약수를 출력
//: 나눈 후 소수점 이하는 버리는 연산자
마무리
자바도 역시 어렵구나..
프로그래머스 문제 풀고 있는데
왜 0단계 2일차 문제들인데 어려운거지..
구글링을 해봐도 잘 모르겠넿ㅎㅎㅎ
내일은 알고리즘 타임어택이 있다는데..
잘 할 수 있을까?ㅎㅎ
자바는 문법 책을 따로 구입해야겠다.
강의로는 잘 모르겠는 부분도 있다.
참조
최대공약수 구하기
스파르타코딩클럽<쉽게 배우는 알고리즘 KDT 실무형 스프링 백엔드 엔지니어 양성과정 1회차>
스파르타코딩클럽<Java 실무 기초 KDT 실무형 스프링 백엔드 엔지니어 양성과정 1회차>
기록하자기록해!