BFS (너비 우선 탐색) 트리나 그래프를 탐색하는 방법으로 시작 정점에서 가장 가까운 정점을 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 방법이다. BFS를 구현할 때는 Queue를 활용하는데 왜 Queue를 쓰는지 아래의 과정을 통해 알아보자. BFS 탐색 과정 1. 루트 노트 방문 2. 큐에서 A를 제거 후 방문 처리, 다음 인접 노드들 큐에 삽입 3. queue 에서 요소 하나 pop(B) 후 방문 처리, B의 인접 노드 큐에 삽입 4. queue 에서 요소 하나 pop(C) 후 방문 처리, C의 인접 노드 큐에 삽입 5. queue 에서 요소 하나 pop(D) 후 방문 처리, D의 인접 노드 큐에 삽입 6. queue에서 남아있는 요소들을 위와 같은 방법으로 방문 및 표시하면서 큐가 완전히..
순차 탐색 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 데이터 크기에 따라 효율이 다르기 때문에 데이터가 많다면 비효율적인 방법 최악 : O(n) 이진 탐색 데이터가 정렬되어 있는 배열에서 찾고자 하는 값을 비교할 때마다 탐색 범위를 반으로 줄이면서 특정한 값의 위치를 찾는다 분할 정복 알고리즘 - 리스트 개수 0,1개일 때 처리하고 2개 이상일 때 재귀 호출로 구현 동작 방식 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같다면 종료 (mid=key) 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다. (mid < key) 중간 값보다 검색 값이 작다면 중간값 기준 배열의..
재귀호출 함수안에서 동일한 함수를 호출하는 방식 시간복잡도 : O(n) 스택 기반 방식 동적계획법, 분할 정복 DP : 입력 크기가 작은 부분 문제들을 해결후 memoization 기법을 사용해 보다 큰 크기의 문제를 해결, 상향식 분할 정복 : 문제를 나눌 수 없을 때 까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘, 하향식 공통점 : 문제를 잘게 쪼갬 차이점 : 동적 : 상위 문제 해결시 재활용, 부분 문제 중복 분할 : 부분 문제를 서로 중복되지 않음 재귀호출은 계속 계산하지만 DP는 이전 계산한 값을 저장하기 때문에 계속 쓸 수 있다. 시간복잡도 비교적 나아진다. 대신 공간 복잡도는 희생된다
시간복잡도 : 얼마나 빠른지 - 핵심 공간복잡도 : 얼마나 많은 공간이 필요한지 파라미터 n 에 따라 계산 시간과 공간은 반비례 공간복잡도 - 빅데이터를 다룰 때 고려 - 고정 : 코드 저장 구간 - 가변 : 실행 중 동적으로 필요한 공간 스왑시 collections.swap 활용 버블정렬 - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 - 오름차순으로 1회전시 가장 큰 수가 가장 오른쪽에 - for 진행 끝날때마다 n번 계산 줄이기 선택정렬 - 해당 순서에 원소를 넣을 위치는 이미 정해져 있고 어떤 원소를 넣을지 정하는 알고리즘 - 기준값 하나 반복하며 기준값을 제외하고 가장 작은 수를 찾아 교환 - 1회전을 수행하고 나면 가장 작은 값의 자료가 맨앞에 삽입정렬 - 자료 배열의 모든 요소를 앞에서..
퀵정렬(Quick Sort)이란? 퀵정렬은 분할정복에 기반한 알고리즘이다. 분할정복이란 전체를 공략하는 대신 전체를 구성하는 구성 요소들을 나누어 잘게 쪼개진 적을 공략하는 개념이다. 퀵 정렬은 아래와 같은 과정으로 분할 정복을 이용해 정렬을 한다. 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소의 왼편에, 큰 값은 오른편에 위치시킨다. 1에서 나눈 데이터 집합들을 다시 1처럼 임의의 기준 요소를 선택하고 같은 방법으로 데이터 집합을 분할한다. 1,2 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻는다. 이를 토대로 예시를 들어보겠다. 요소 5를 기준으로, 5보다 작은 요소는 왼쪽, 5보다 큰 요소는 오..
삽입 정렬(Insertion Sort) 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘이다. 삽입 정렬도 버블 정렬만큼 구현이 간단해서 프로그래머들에게 애용된다. 삽입 정렬은 아래와 같은 과정을 진행한다.(오름차순 정렬) 데이터 집합에서 정렬 대상이 되는 요소들을 선택합니다. 이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개지만, 알고리즘 반복 횟수가 늘어날 때마다 1개씩 커진다. 정렬 대상의 최대 범위는 '데이터 집합의 크기 - 1' 이다. 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인한다. 그렇지 않다면 이 요소를 정렬 대상에서 뽑아내고 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾는다...
정렬은 사전적 의미로 "물건 등을 가지런히 늘어 세우다" 라는 뜻을 갖고 있다. 우리는 정렬을 왜 할까? 이유는 간단하다. 찾을려고 하는 것을 쉽게 찾고싶어서이다. 즉, 탐색을 위해 정렬을 한다는 것이다. 앞으로 정렬 알고리즘 중 활용도가 높은 버블 정렬, 삽입 정렬, 퀵 정렬 3 가지에 대해 알아볼 예정이고 먼저 버블 정렬(Bubble Sort)부터 소개하겠다. 버블 정렬(Bubble Sort) 버블 정렬은 알고리즘이 데이터를 정렬하는 과정이 마치 물 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여진 이름이다. 버블 정렬은 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행한다. 이해를 돕기위해 제멋대로 나열되어 있는 수의 집합을 오름차순으로 정렬해보..
문제설명 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요. 제한조건 x는 1 이상, 10000 이하인 정수입니다. 입출력 예 arr return 10 true 12 true 11 false 13 false 풀이 class Solution { public boolean solution(int x) { return (x % getHarshadSum(x) == 0) ? true : false; } private int getHarshadSum(int paraX) { int tmp = 0..
