Sujin's Log Sujin's Log

BFS(Breadth First Search, 너비 우선 탐색)이 알고리즘의 핵심은 큐(Queue)를 사용하는 것노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보를 큐에 넣어 큐에 먼저 들어있던 노드부터 방문.list 형식을 사용해 큐를 구현할 수도 있지만, list.pop(0)은 시간복잡도가 O(N)이므로 비효율적. -> collections 라이브러리의 deque를 사용. 방문하지 않았던 노드를 큐에 넣을때는 set타입을 사용. DFS(Depth First Search, 깊이 우선 탐색)이 알고리즘의 핵심은 스택(Stack)을 사용하는 것.

문제 1) 피보나키 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다. 2) 입력은 피보나치 수열의 총 항의 수 이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다. 메모이제이션을 사용하지 않은 구현 import java.util.Scanner; public class Section7_4_Ver1 { public static int DFS(int n) { if (n == 1 || n == 2) return 1; else return DFS(n - 2) + DFS(n - 1); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scann..

이진탐색이란? "정렬되어 있는 데이터"에서 특정한 값을 찾아내는 알고리즘이다. 문제 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다. 입력 첫 줄에 한 줄에 자연수 N(3

삽입정렬이란? 현재 비교하고자 하는 target과 그 이전의 원소들과 비교하며 자리를 교환(swap)하는 정렬 방법. 선택정렬, 버블정렬과는 다르게 안정 정렬. 삽입정렬의 과정(오름차순 기준) 1. 인덱스 1부터 시작한다. 현재 인덱스를 타겟 인덱스로 하고 변수에 넣는다. 이 변수보다 이전 인덱스가 작으면 이전 인덱스의 값을 그 다음 인덱스에 넣어준다. 2. 만약에 인덱스 2가 타겟이고, 타겟의 값이 인덱스 1보다 작다면 그 다음 인덱스에 넣는다. 또 인덱스 0이 타겟보다 작으면 또 그 다음 인덱스에 넣는다. 그리고 타겟 인덱스의 값을 인덱스 0에 넣어준다. 3. 이를 계속 반복한다. 구현 코드 import java.util.Scanner; public class Main { private int[] s..

버블 정렬이란? 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. 과정 1. 첫 번째 반복문에서 첫번째 원소와 두 번째 원소를 비교한다. 만약 첫 번째 원소가 더 크면 교환. 두 번째 원소와 세 번째 원소를 비교후 두번째가 크면 교환. 이렇게 해서 n-1번재 원소까지 비교하면 가장 큰 수는 n에 가있게된다. 2. 그럼 n은 가장 큰 수이니까, 다시 n-2원소까지 비교를 반복. 그럼 두 번째로 큰 수가 n-1번에 가게 된다. 이렇게 반복하면 모든 수가 정렬된다. 구현 코드(Java) import java.util..

선택정렬이란? 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환함으로써 정렬하는 정렬 방법이다. 선택 정렬의 과정 와 같은 원리로 오름차순 정렬이 된다. 1. 현재의 인덱스를 minIndex에 넣어준다. 2. 그 뒤의 인덱스에서 for문을 돌려 만약에 다른 인덱스의 값이 더 작다면 바꿔준다. 이렇게 마지막까지 돌면 minIndex의 인덱스 값은 가장 작은 값을 가진 인덱스일 것이다. 마지막 인덱스는 이미 그 앞의 인덱스를 통해 교체가 되어 가장 큰 수일 것이므로 for문은 n-1번까지만 돌면 된다. 구현 코드 import java.util.Scanner; public class Main { private int[] solution(int n, int[] list) { for..

문제 N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요. 만약 N=8, M=6이고 수열이 다음과 같다면 1 2 1 3 1 1 1 2 합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다. 또 이중 for문을 돌면서 풀이하면 쉽겠지만 그렇게 되었을 경우 시간복잡도가 O(N^2)가 되기 때문에 만약 N이 0~100000000 M도 0~1000000정도 되는 경우에는 엄청난 크기가 되어버린다. 그래서 저번에 배웠던 슬라이딩 윈도우(https://suucong.tistory.com/74)알고리즘과 투포인터(https://suucong.tistory.com/7..

문제 12 15 11 20 25 10 20 19 13 15 와 같은 N개의 원소를 가지고 있는 배열과 변수 K가 주어졌을 때 연속된 K개의 합중에서 가장 큰 값을 구해라 예시 입력 10 3 12 15 11 20 25 10 20 19 13 15 예시 입력의 첫번째 수는 N개의 배열을 줄것이다라는 것이고, 두번째 수는 K를 주는 것이다. 예시 출력 56 처음에 내가 짰던 알고리즘은 이중 for문을 사용하였다. 그랬더니 또 Timeout Error가 발생하였다. 나는 이중 for문을 이용해도 시간복잡도가 O(N)일거라고 생각하였다. 저 예시 입력의 경우에는,,, 생각해보면 만약 N이 100000인데, K가 60000이다? 그러면 시간복잡도는 거의 O(N*N)이 되어버린다.. 그래서 타임아웃 오류가 발생하였던 ..