공부 || 정리/Algorithm
[Java] 진법 변환 토이 프로젝트 (N진수를 K진수로 변환하기, No Library)
[Java] 진법 변환 토이 프로젝트 (N진수를 K진수로 변환하기, No Library)
2021.07.26개요 코딩 테스트에서 진법 변환 문제가 나왔습니다. 여러 조건 때문에 결국 못 풀어서 한이 남아 아예 프로젝트를 하나 만들고 포스팅으로 박제하고자 합니다. 한번 익혀두면 잊어버리지 않으니, 공부하면 좋은 지식이 될 거라 생각합니다. N진수를 입력 받아 N진수를 K진수로 변환하는 방법을 알아보겠습니다. ex) 1111(2) -> 17(8) N = (2 ~16) 진수 K = (2~16)진수 NotationConversion NotationConversion은 제가 지은 프로젝트 이름입니다. N진수를 K진수로 바꾸는 변환 과정은 다음과 같습니다. N진법으로 표기된 숫자를 10진법으로 바꾸고 바꾼 10진수를 K진법으로 바꿔줬습니다. 자바 코드로 먼저 확인해보겠습니다. import java.io.BufferedR..
[Java] 다익스트라(Dijkstra) 알고리즘.
[Java] 다익스트라(Dijkstra) 알고리즘.
2021.05.28공부가 목적인 포스팅으로, 미흡한 점이 있다면 피드백 부탁드리겠습니다. 다익스트라로 불리는 이 알고리즘은 그래프의 가중치를 활용하여 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 어떤 한 정점(노드)에서 나머지 모든 정점(노드)에 대하여 최단 거리를 알려줍니다. 하지만 이때 단 하나의 음의 간선(음의 가중치)이 존재하면 안됩니다. 말 그대로 '최단 거리'를 구하고자 하는 것이기 때문에 음의 간선이 존재하면 최단 거리의 의미가 퇴색됩니다. 다익스트라 알고리즘은 그리디 알고리즘 + 다이나믹 프로그래밍(DP) 알고리즘을 합친 버전이라 볼 수 있습니다. 방문하지 않은 정점 중 가장 가중치가 적은 정점을 선택하는 방법(그리디) + 하나의 최단 거리를 구할 때 그 이전에 구한 최단 거리 정보를 이용하는 방법(D..
[Java] 이분 탐색(Binary Search)
[Java] 이분 탐색(Binary Search)
2021.05.15공부를 목적으로 진행하는 포스팅으로 만약 틀린 부분이 있거나 미흡한 점이 있으면 피드백 부탁드리겠습니다. 이분 탐색 혹은 이진 탐색이라 불리는 이 알고리즘은 간단하면서 굉장히 효율적인 알고리즘입니다. 이 알고리즘을 수행하기 위해서는 기본적으로 정렬이 되어있어야 합니다. 정렬된 자료구조 안에서 특정 값을 찾을 때 절반씩 나누어 값을 찾는다는 것이 핵심적인 아이디어입니다. 이분 탐색은 탐색을 진행할 때마다 탐색 범위를 반으로 줄입니다. 분할 정복(Divide Conquer)알고리즘과 유사한데 이분 탐색은 분할 정복 알고리즘의 한 예입니다. 만약 탐색 범위가 더이상 나눠지지 않는 1이 될 때의 탐색 횟수를 T라고 하고, 정렬된 배열의 길이가 N인 자료구조에서 이분 탐색을 했을 경우의 시간 복잡도를 표로 보여드..
[Java]투 포인터 / 슬라이딩 윈도우 알고리즘
[Java]투 포인터 / 슬라이딩 윈도우 알고리즘
2021.05.13비슷하면서도 다른 두 알고리즘을 설명하겠습니다. 공부를 목적으로 진행하는 포스팅으로 만약 틀린 부분이 있거나 미흡한 점이 있다면 피드백 부탁드리겠습니다. 투 포인터와 슬리이딩 윈도우. 이 두 알고리즘은 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공통점이 있습니다. 그렇다면 이 두 알고리즘의 차이점은 무엇일까요? 바로, 부분 배열 길이의 변화 여부입니다. 더 쉽게 말해서, 투 포인터 알고리즘은 부분 배열의 길이가 가변적이지만 슬리이딩 윈도우 알고리즘은 부분 배열의 길이가 고정적입니다. 투 포인터 투 포인터는 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘입니다. 여..
[Java] DFS, BFS 정리
[Java] DFS, BFS 정리
2020.12.15DFS( 깊이 우선 탐색 , Depth-First Search) 루트 노드( 혹은 다른 임의의 노드)에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법. 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색합니다. 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 지닙니다. (재귀 or 스택) 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것입니다. (이를 검사하지 않을 경우 무한루프에 빠질 수 있다. ) ex) visit[index] = true; 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다..
[Java] 스택(Stack) 정리 및 구현
[Java] 스택(Stack) 정리 및 구현
2020.06.17이번 포스팅에서는 자료구조의 하나인 '스택(Stack)'을 다루고자 한다. 먼저 스택의 정의에 대해서 간략하게 설명하고 스택의 동작과 스택의 구현 방법을 JAVA코드를 참고해 구현해보겠다. 1. 스택(Stack)이란 무엇인가? 우선 영어 단어 '스택(Stack)'이란 '쌓다' , '쌓아 올린 더미'를 의미하며, 자료구조의 '스택(Stack)' 역시 이러한 특징을 지닌다. 스택은 메모리 안 데이터들을 더욱 효율적으로 다루기 위해 만들어진 데이터 참조 방식이며, 한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조이다. 즉, 마지막에 들어온 데이터가 가장 먼저 나가는 특징인 LIFO구조(Last In First Out, 후입 선출)를 갖는다. 네모 상자 안에 여러 개의 공을 넣고 빼는 생각을 하면 편리하다. ..