비트(Bit)와 비트마스킹(Bitmasking) 비트마스킹 기법에 대해 학습한 내용을 정리해둔다. 자바의 비트 연산자와 비트 이동 연산자를 알아보고, 비트마스킹이 무엇인지 알아보도록 하겠다. 자바 비트 연산자 & bit AND 연산자 비교하는 비트가 모두 1이면 1 # a = 22, b = 14 # a & b 00010110 (AND) & 00001110 ------------------ 00000110 | bit OR 연산자 비교하는 비트 중 하나라도 1이면 1 # a = 22, b = 14 # a | b 00010110 (OR) | 00001110 ------------------ 00011110 ^ bit XOR 연산자 양쪽 비트가 같으면 0, 다르면 1 # a = 22, b = 14 # a ^ b..

이진 탐색 이진 탐색(Binary Search)은 이분 탐색이라고도 하며, 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다. 이진 탐색 조건 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다. 이진 탐색 특징 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정이다. 이진 탐색 동작 과정 이진 탐색의 동작 과정은 다음과 같다. 데이터 리스트(arr)..

정렬 알고리즘 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘은 다양한 알고리즘이 존재하는데, 그 중 대표적인 정렬 알고리즘인 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해서 정리하고자 한다. 선택 정렬 선택 정렬 알고리즘은 리스트에서 매번 가장 작은 데이터를 선택하여 차근차근 정렬하는 방식의 알고리즘이다. 가장 작은 데이터를 선택하여 앞으로 보내는 과정을 반복하면 전체 데이터의 정렬이 이루어진다. 선택 정렬의 과정은 다음과 같다. 리스트의 길이(N)-1 만큼 다음 내용을 반복한다. 반복 횟수를 K라고 한다(0 = 0 && arr[a] > tmp) { // a 포인터의 값을 한 칸 다음으로 민다. arr[a + 1] = arr[a]; a--; } // b 포인..

DFS/BFS DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다. DFS는 스택 자료구조 또는 재귀 함수를 통해 구현할 수 있고, BFS는 큐 자료구조를 통해 알고리즘을 구현할 수 있다. 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 ‘두 노드는 인접하다’라고 표현한다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 메모리 측면에서 인접 행렬 방식은 모든 관계를 저장하므로 노드의 개수가 많을 수록 메모리가 불필요하게 낭비된다. ..

최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 알고리즘 특징 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 그대로 적용된다는 특징이 있다. 또한 최단 경로 문제는 보통 그래프를 이용해서 표현하는데 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다. 최단 경로 알고리즘에는 다익스트라 알고리즘, 플로이드 워셜 알고리즘, 벨만 포드 알고리즘 등과 여러 알고리즘이 있다. 여기서는 다익스트라 알고리즘과 플로이드 워셜에 대해 알아본다. 다익스트라 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다..