Sujin's Log Sujin's Log

이진탐색이란? "정렬되어 있는 데이터"에서 특정한 값을 찾아내는 알고리즘이다. 문제 임의의 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)이 되어버린다.. 그래서 타임아웃 오류가 발생하였던 ..

문제 A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요. (각 집합안의 원소는 중복되지 않는다.) 입력 예시 5 1 3 9 5 2 5 3 2 5 7 8 출력 예시 2 3 5 일단 내가 짠 코드는 이중 for문을 이용하여 n과 m이 각 리스트의 원소의 수라고 하였을 때 시간복잡도가 O(n*m)이었다. 그랬더니 리스트별로 데이터가 각 30000개일 경우 타임아웃 오류가 났다. 제한이 1000ms인데 1700ms인가.. (머쓱..) 투포인터 알고리즘을 이용한다면 시간복잡도가 O(n+m)이 되게 된다. 이 방법으로 타임아웃 에러를 해결할 수 있었다. 이중 for문 import java.util.ArrayList; import java.util.Scann..