분류 전체보기
-
자물쇠와 열쇠프로그래머스/구현 2022. 7. 6. 15:23
1. 풀이 1) 예제 설명 문제 예시에 나온 key 배열과 lock 배열은 다음과 같다. key 배열 0 0 0 1 0 0 0 1 1 lock 배열 1 1 1 1 1 0 1 0 1 그림으로 나타내면 다음과 같다. 진한 보라색, 노란색 : 돌기 연한 보라색, 노란색 : 홈 => key의 돌기 부분과 lock의 홈 부분이 만나야 됨 key lock 즉, 열쇠의 돌기 부분이 자물쇠의 홈 부분에 맞게 채워졌을 때는 아래와 같은 그림이 된다. 진한 선은 lock(자물쇠) 부분에 key(열쇠)가 잘 맞게 채워진 상태를 표현했다. 2) 확장된 lock 배열 이러한 상태를 나타내기 위해서는 확장된 lock 배열을 사용해야 한다. 즉 다음과 같이 표현할 수 있다. 자물쇠는 제 자리에 있고, 열쇠가 이동하면서 자물쇠가 맞..
-
선택 정렬백준/정렬 2022. 7. 2. 22:27
1. 선택 정렬 선택 정렬은 다음과 같이 진행된다. 1. 주어진 숫자에서 최솟값을 찾는다. 2. 최솟값을 맨 앞자리 값과 바꾼다. 3. 맨 앞 자리를 제외한 나머지 값 중 최솟값을 찾아서 반복한다. 시간복잡도 : O(N*N) 2. 그림으로 설명 다음과 같이 a배열이 있다고 하자. 즉, a[0] = 5 이다. 단계 1 1) min = 0 i = 0 부터 시작한다. 즉, 위의 숫자 배열에서 맨 처음값부터 시작한다. 그리고 이때 min 이라는 변수를 사용하는데, min = i 이다. 즉, 처음에 min = 0 이다. j = i+1 = 1부터 시작한다. 그래서 혹시 a[j] < a[min] 이라면, min = j 로 바꿔준다. 즉, a[1] < a[0] 이므로 min = 1 이 된다. 2) min = 1 min..
-
버블 정렬백준/정렬 2022. 6. 29. 18:28
1. 버블 정렬 버블 정렬은 다음과 같이 진행된다. (오름차순 기준) 1. 맨 앞 숫자(a) 부터 비교를 시작한다. 2. 바로 뒤의 숫자(b) 와 비교해서 뒤의 숫자가 더 작으면 자리를 바꿔준다. 즉, a b 순서였는데 b < a 이면 b a 로 자리를 바꿔준다. 3. 그 다음 숫자와 비교하면서 위와 같은 과정을 반복한다. 4. 맨 끝까지 비교가 끝나면 다시 맨 앞 숫자를 뒤의 숫자와 비교한다. 시간 복잡도 최선의 경우 : O(N) 평균 : O(N*N) 단점 : 다른 정렬 알고리즘에 비해 교환과정이 많아서 시간 소비가 크다. 2. 그림으로 설명 다음과 같은 상황이라고 하자. 단계 1 맨 앞에 있는 값은 1이다. 바로 뒤의 5와 비교한다. 5가 더 크므로 둘의 자리를 그대로 둔다. 그 다음 5와 3을 비교..
-
위상 정렬백준/위상 정렬 2022. 6. 28. 23:08
1. 위상 정렬 알고리즘 그래프와 관련된 알고리즘이다. 선후 관계가 정의된 구조에서 정렬을 하기 위해 사용된다. 1) 예제로 설명 5가지 업무가 있다고 하자. 그런데 이 업무에는 우선순위가 있어서 아래와 같이 각 줄에 주어진 순서대로 업무가 진행되어야 한다. 1 2 3 5 1 3 4 4 1 이때 5가지 업무를 어떤 순서로 진행해야 위에 주어진 우선순위를 만족할지 구하는 것이 위상 정렬 알고리즘이다. 2) 조건 방향성이 있어야 한다. 사이클이 없는 그래프여야 한다. 3) 그림으로 설명 위의 상황을 그래프로 표현하면 다음과 같다. 사이클도 없고 방향성도 있다. 이때 사용되는 배열이 있다. => value 배열 진입차수를 나타내는 배열이다. 즉 특정한 노드로 들어오는 간선의 개수를 나타낸다. 예를 들어서 위에..
-
1541 잃어버린 괄호백준/파싱 2022. 6. 28. 16:44
1. 풀이 다른 사람 블로그를 참고했다. 예를 들어서 설명하겠다. 10 + 20 - 30 + 40 - 50 + 60 괄호를 쳐서 주어진 입력의 결과를 최소값으로 만들라고 했다. 핵심은 - 부호를 이용하는 것이다. 즉, 위의 예제에서는 10 + 20 - (30 + 40) - (50 + 60) 이 된다. 이처럼 - 부호 뒤에 ( 괄호를 치고 다음 - 부호가 나오기 전에 ) 괄호를 쳐주면 된다. 즉, 음수값이 크게 만들면 된다. 단계 1 제일 먼저 입력값을 String 으로 받는다. 단계 2 - 부호를 기준으로 입력값을 분리해준다. 단계 3 분리된 입력값을 각각 + 연산한다. 단계 4 맨 앞에 있는 값 제외하고 모두 - 연산하면 된다. 즉, 30 - 70 - 110 = -150 이 정답이 된다. 2. 최종 코..
-
2671 잠수함식별백준/정규 표현식 2022. 6. 28. 15:07
1. 풀이 다른 사람 블로그를 참고했다. 문제에서 식별하고자 하는 잠수함의 엔진소리 패턴은 다음과 같다. (100~1~|01)~ 그러면 이에 대한 정규표현식 패턴을 만들면 다음과 같다. ^(100+1+|01)+$ 여기에 사용된 정규표현식 문법을 나타내면 다음과 같다. 그리고 코드에 보면 입력 문자열과 패턴이 일치하는지 여부를 mathes() 메서드로 확인하고 있다. matches() 메서드 : 대상 문자열과 패턴이 일치하는 경우 true 반환 2. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(St..
-
11653 소인수분해백준/소수 판정 2022. 6. 27. 22:32
1. 풀이 다른 사람 블로그를 참고했다. 문제 예제에 나온 72를 가지고 설명하겠다. 1) 소인수 : 소수인 약수 즉 72를 소수인 약수들로 분해하면 된다. 2) 소수 : 약수가 1과 자기 자신뿐인 자연수 소수는 1이 아니라 2부터 시작한다. 단계 1 N = 72 72를 2로 나눈다. 나머지가 0이므로 2는 72의 인수이다. 그리고 소수이다. => 2를 출력 => 72/2 = 36에 대해서 반복 단계 2 36을 2로 나눈다. 나머지가 0 => 2는 36의 소인수 => 2를 출력 => 36/2 = 18 에 대해서 반복 단계 3 18을 2로 나누면 나머지가 0 => 2는 18의 소인수이다. => 2를 출력한다. => 18/2 = 9 에 대해서 반복 단계 4 9를 2로 나누면 나머지가 0이 아니다. => 2는..
-
삽입 정렬백준/정렬 2022. 6. 27. 20:36
1. 삽입 정렬 삽입 정렬은 다음과 같이 진행된다. 1. 현재 타깃이 되는 숫자와 이보다 앞에 위치하는 숫자들을 비교 2. 타깃 숫자 서로 교환 3. 타깃 숫자 > 앞에 위치하는 숫자 => 다음 타깃으로 이동 4. 위와 같은 방법으로 반복 시간복잡도 최선의 경우 : O(N) => 거의 정렬된 경우는 매우 효율적 최악의 경우 : O(N*N) => 역순에 가까울 수록 매우 비효율적 2. 그림으로 설명 다음과 같은 상황이라고 하자. 단계 1 첫번째 타깃은 두 번째부터 시작된다. 이때 타깃 숫자인 2보다 앞에 위치한 1이 작다. 그러면 자리 변경없이 끝이 난다. 다음 타깃으로 이동한다. 단계 2 두번째 타깃은 세 번째에 위치한 5이다. 앞에 있는 2가 더 작으므로 역시 자리 변경 없..