계발자 블로그

문자열 알고리즘을 풀 때 가끔 기억이 안나서 한번에 정리 하면서 공부 해보려고 합니다. toLowerCase() 문자열을 소문자로 변환 해줍니다. toUpperCase() 문자열을 대문자로 변환 해줍니다. String s = "abcdefg1234"; s = s.toUpperCase(); System.out.println(s); s = s.toLowerCase(); System.out.println(s); replace(기존문자, 바꿀 문자) 해당 문자열의 일부를 치환 해줍니다. String s = "abcdefg1234"; s = s.replace("1234", "hijk"); System.out.println(s); substring() 문자열의 특정 인덱스만큼 혹은 특정 인덱스 이후로 잘라냅니다. ..

유클리드 호제법이란? 유클리드 互除法 / Euclidean algorithm 互(서로 호), 除(나눌 제, 뺄 제) 서로 나눈다는 의미입니다. 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 알고리즘입니다. 인류 최초의 알고리즘이라고 하네요. gcd는 최대공약수를 뜻합니다. Greatest Common Divisor의 줄임말입니다. 자바 코드로 나타내면 // 반복문 방식 int gcd(int a, int b) { while(b != 0) { int r = a % b; a = b; b = r; } return a; } // 재귀 방식 int gcd(int a, int b) { if(a%b == 0) return b; return gcd(b, a % b); } 이렇게 됩니다. 최소공배수는 a * b /..

삽입정렬(Insertion Sort)이란 ? 삽입정렬은 정렬되지 않은 데이터를 앞에서 부터 차례대로 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘입니다 5 3 2 4 1 이런 배열이 주어졌을 때 3은 5의 앞으로 가야 하기 때문에 3을 빼서 3의 자리로 5를 밀고 원래 5가 있던 자리에 3을 삽입합니다. 3 5 2 4 1 그 다음 2는 2는 5보다 앞으로 가야 됩니다 위에서 3이 했던 것과 같이 2를 빼서 5를 밀고 앞에 3이 또 있으니까 3과 비교해 줍니다 3보다도 앞으로 가야 하니까 3을 또 밀어주고 2는 맨 앞으로 가게 됩니다 이렇게 앞에 수와 비교해 주면서 맞는 위치에 삽입해 주는 것입니다. public int[] solution(int n, int[] arr) { for(in..

버블정렬(Bubble Sort)이란 ? 버블정렬은 서로 인접한 두 수를 검사하여 정렬하는 알고리즘입니다. 9 8 7 3 2 5 4 1 6 이런 배열이 있다면 8 9 7 3 2 5 4 1 6 8 7 9 3 2 5 4 1 6 8 7 3 9 2 5 4 1 6 ... 8 7 3 2 5 4 1 9 6 8 7 3 2 5 4 1 6 9 이렇게 가장 큰 수가 맨 뒤로 가게 됩니다. 그럼 그 다음부터는 8번째 원소 까지만 정렬을 해줍니다. public int[] solution(int n, int[] arr) { for(int i=0; i

선택정렬(Selection Sort)이란 ? 선택정렬은 데이터를 정렬 할 때 가장 작은 수를 선택 하여 맨 앞자리의 수와 바꿔주는 정렬입니다. 9 1 8 4 2 3 5 6 7 이런 배열이 있다면 1 9 8 4 2 3 5 6 7 1 2 8 4 9 3 5 6 7 1 2 3 4 9 8 5 6 7 ... 1 2 3 4 5 6 7 9 8 1 2 3 4 5 6 7 8 9 순으로 정렬 되는 것이 선택정렬입니다. public int[] solution(int n, int[] arr) { for(int i=0; i

에라토스테네스의 체? 에라토스테네스의 체란 n까지의 소수를 찾는 알고리즘입니다. 소수를 찾는 알고리즘 중에 가장 빠른 방법입니다. 소수는 약수를 1과 자기 자신만 갖는 수를 말합니다. n을 15라 가정하면 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 이렇게 2부터 15까지의 배열을 하나 만듭니다. (1은 소수가 아니기 때문에 2부터 합니다.) 그리고 각 수의 배수들을 지워줍니다. (본인은 지우지 않음) 그럼 2의 배수 3의 배수들을 지워 가다 끝까지 가면 지워지지 않은 남는 숫자들이 소수입니다. import java.util.*; public class Main { public int solution(int n) { int answer = 0; int [] ch =..

BFS란? Breadth-First Search의 줄임말로 너비 우선 탐색이라고 합니다. 그래프 탐색 알고리즘 중 하나로 루트 노드(혹은 다른 임의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방식입니다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택합니다. 특징 재귀적으로 동작하지 않는다. 큐(Queue) 자료구조를 사용한다. 0 - 1 - 2 - 3 - 4 - 5 - 6 순으로 탐색하게 됩니다. 코드로 구현해 보기 BFS에서는 queue를 직접 생성해줍니다. DFS에서 stack은 컴퓨터가 항상 스택의 원리를 사용하고 있기 때문에 굳이 새로운 스택을 사용하지 않아도 됬습니다. 각 노드의 레벨을 나타내기 위한 L을 만들었습니다. 성공적으로 너비 우선 탐색이 실행된 모습..

DFS란? Depth-First Search의 줄임말로 깊이 우선 탐색이라고 합니다. 그래프 탐색 알고리즘 중 하나로 한 루트로 최대한 깊숙이 들어가서 확인한 뒤 가장 가까운 곳으로 돌아가 다른 루트로 탐색하는 방식입니다. 미로 찾기에서 한 방향으로 끝까지 갔다가 막히면 그곳에서 가장 가까운 갈림길부터 다시 찾는 것입니다. 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택합니다. 특징 일반적으로 재귀호출을 사용하여 구현한다. 스택이 사용된다. 어떤 노드를 방문했었는지 여부를 검사해야 한다 그렇지 않을 경우 무한루프에 빠질 수 있다. 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다. 0 - 1 - 3 - 4 - 2 - 5 - 6 순으로 탐색하게 됩니다. 코드로 구현해보기 방문한 순서가 ..

오늘은 피보나치 수열을 풀어보겠습니다. 피보나치 수열이란? 앞의 두개의 숫자를 합하여 다음 숫자가 되는 수열입니다. 1, 1, 2, 3, 5 .... 이렇게 되겠죠. n번째 까지의 피보나치 수열을 구하는 문제를 풀어봅시다. 구현 방법은 간단합니다. 배열을 하나 만들고 for문을 이용해서 해결했습니다. 피보나치 수열에 첫번째와 두번째 값은 항상 1, 1이기 때문에 0번째와 1번째 인덱스에는 1을 넣어줬습니다. for문을 이용해 풀면 간단한데 재귀함수를 이용해서 풀어보겠습니다. 마찬가지로 첫번째와 두번째는 1이 들어가니 1은 고정으로 넣어줍니다 그리고 앞의 두개 숫자를 더해주면서 재귀함수를 호출합니다. 단, n이 5처럼 적은 숫자가 들어갔을때는 빠르게 연산이 되지만 45처럼 큰 숫자가 들어가면 뒤로 갈수록 ..

안녕하세요 재귀함수와 스택프레임에 대해 알아보겠습니다. 재귀함수란(Recursive function)? 함수가 자기 자신을 호출하여 작업을 수행 반복하는 작업을 수행할 수 있음 함수 내에서 자신을 호출한 후 호출한 함수가 끝날 때 까지 함수 호출 이후의 코드는 수행되지 않음 반복문과 마찬가지로 종료 지점을 명확하게 생각하고 구현해야 무한루프를 방지할 수 있음 우리가 보통 반복되는 작업을 사용할 때 for문을 많이 쓰듯이 똑같이 재귀함수를 통해 구현할 수 있습니다. 코드를 보겠습니다 1부터 3까지의 수를 차례로 출력하라는 문제를 재귀함수로 풀어보겠습니다. 여기서 코드를 보시면 메인함수에서 DFS함수를 호출하고, 프린트하고 다시 DFS 자신을 호출합니다 이게 재귀함수입니다. 이렇게 하면 3 2 1 이런식으로..