새벽 기상을 꿈꾸는 루민

안녕하세요 세기무민입니다. 회사 다니다보니 알고리즘 공부에 조금 소홀했는데 향후 이직이나 알고리즘 공부를 위해 틈틈히 풀면 좋을 것 같아서 이번 포스팅은 백준 알고리즘 포스팅으로 찾아왔습니다. 문제 설명 예시 문제 풀이 우선 해당 문제에서는 패턴만 파악하면 되는 문제인데 예시로 나온 dir a?b.exe를 유심히 봅시다. acb.exe, aab.exe, apb.exe가 나와도 문제 없다고 하는 말을 다시 해석해보면 ?표에 들어간 단어는 달라도 무관하다는 의미를 가집니다. 즉, 입력받은 값들 중 같은 값이 아닌 경우에는 ? 표시를 해주면 되는 문제입니다. 코드를 보면 아래와 같습니다. # 명령 프롬포트 - 1032 inputValue = int(input()) for i in range(inputValue..

안녕하세요 세기무민입니다. 이번 포스팅에서는 DFS/BFS 알고리즘에 대해 다뤄보도록 하겠습니다. DFS/BFS? DFS와 BFS 알고리즘은 코딩테스트에 거이 단골 문제 중 하나입니다. DFS는 깊이 우선 탐색 알고리즘 BFS는 너비 우선 탐색 알고리즘 대표적으로 DFS의 경우 재귀함수 또는 스택으로 문제를 해결할 수 있고 BFS의 경우 큐(덱큐)를 이용하여 문제를 해결할 수 있습니다. DFS와 BFS를 가장 쉽게 알 수 있는건 아래의 그림으로 볼 수 있습니다. [DFS]! 위의 그림처럼 깊이부터 하나씩 탐색하는 방식입니다. 1에서 가장 가까운 2를 탐색하고 2의 다음 노드인 4를 탐색합니다. 노드 4 이후로 연결된 노드가 없음으로 노드 1로 다시 이동하여 탐색을 반복해줍니다. [BFS!] BFS는 가장..

안녕하세요 세기무민입니다. 이번 포스팅은 브루트포스 알고리즘에 대해 다뤄보겠습니다. 브루트포스? 브루트 포스는 무차별 대입을 통해 값을 도출하는 방법입니다. 브루트 포스 알고리즘은 암호 해독에 유명한 알고리즘 중 하나입니다. 브루트 포스는 조합 가능한 모든 문자열을 하나씩 대입해보는 완전 탐색 기법이라고 생각하면 됩니다. 브루트포스 알고리즘 장단점? 조합 가능한 모든 문자열을 대입하기 때문에 정확도가 100%를 도출합니다. 단, 모든 경우의 수를 찾아가기 때문에 조금만 알고리즘이 복잡해져도 알고리즘의 시간 복잡성은 올라갑니다. 예시 알고리즘 문제 위의 문제는 가장 대표적인 브루트 포스 알고리즘 중 하나입니다. 3개의 숫자를 합했을 때 M의 크기와 가장 가까운 값을 찾는 문제인데 해당 문제는 순열을 통해서..

안녕하세요 세기무민입니다. 이번 포스팅에서는 그리디 알고리즘에 대해 다뤄보도록 하겠습니다. Greedy? 탐욕? 우선 그리디 알고리즘은 탐욕 알고리즘이라고도 말합니다. 그리디 알고리즘에서 가장 중요하게 생각하는 포인트는 "현재 선택지 중 가장 좋은(최적)의 방법을 선택하는 것" 그리디 알고리즘에 대한 가장 좋은 예시는 최단거리를 구하는 것이다. 아래의 그림으로 설명해보면 시작 지점으로부터 끝지점까지 최단거리를 구해보도록 하자. 시작 지점에서 4로 시작하는 경우 2가지의 경우의 수가 만들어지며 20, 23의 거리를 가진다. 시작 지점에서 4보다 큰 6으로 시작했을 경우 19의 거리를 가지게 되고 최종적으로 가장 짧은 거리를 가지게 된다. 즉 그리디 알고리즘은 여러개 중 한개를 선택해야 할 경우 그 순간에 ..

ㅋ안녕하세요 세기무민입니다. 이번에 풀어볼 문제는 2020년도 카카오 블라인트 문제 중 하나인 자물쇠와 열쇠 문제입니다. 문제 설명 입출력 예시 문제 풀이 흠.... 개인적으로 일단 이번 문제에서 포인트는 배열 회전하는 것이라고 생각한다. 파이썬에서 배열 회전에 사용되는 내장 함수 중 Zip이라고 있는데 이걸 사용하여 0 / 90 / 180 / 270도 회전하여 한번씩 key를 넣어보면 되는 문제이다. 아래의 그림으로 좀더 쉽게 설명해보면 간단한 예시로 Lock과 Key의 값은 위와 같고 0도부터 하나씩 Lock에 Key를 넣어줍니다. 넣었을 때 Lock의 모든 값이 1이라면 True를 반환해주면 되고 0, 90, 180, 270도 회전하여 동일하게 하나씩 탐색했음에도 불구하고 모든값이 1인 경우가 없다..

안녕하세요 세기무민입니다. 이번에 풀어볼 문제는 2018년도 카카오 블라인드 테스트 1차 비밀지도 문제입니다. 문제 설명 입출력 및 예시 문제 풀이 이번 문제는 위의 설명대로 문제를 접근하면 됩니다. 요약을 하자면 1. 2진수로 변환하기 2. 2진수로 변환한 수의 자리수를 맞춰주기 3. 2진수로 변환한 값들을 비교 및 #으로 출력 arr1과 arr2의 값들을 2진수로 변환해서 두개를 합쳤을 때 1인 경우에 #으로 표시해주면 됩니다. 여기서 2진수로 변환하는 방법이 여러가지가 있지만 저는 format을 이용하였습니다. 2진수로 변환을 완료했다면 다음으로 확인할 것은 해당 배열의 자리수와 일치하는지 확인이 필요하고 만약 자리수가 다르면 자리수를 맞춰주면 됩니다. 마지막으로 자리수를 맞췄다면 해당 값들을 비교..

안녕하세요 세기무민입니다. 이번에 돌아온 포스팅은 프로그래머스 알고리즘 풀이 문제로 돌아왔습니다. 문제설명 입출력 예시 문제풀이 우선 저는 이 문제를 보자마자 메모장에 그림을 그렸습니다. 전화기가 위와 같이 있다고 가정하면 일단 왼쪽의 숫자들은 3으로 나눴을 때 나머지가 1인 경우의 수 오른쪽의 숫자들은 3으로 나눴을 때 나머지가 0인 경우의 수라는 것을 알 수 있습니다. 그런 뒤 이 문제에서 가장 중요한건 가운데 숫자를 클릭하는 방법인데 우선은 가운데 숫자들은 3가지의 조건을 생각해봤습니다. 1. 왼쪽과 오른쪽의 길이가 같은 경우 2. 왼쪽이 오른쪽 길이보다 큰 경우 3. 오른쪽이 왼쪽 길이보다 큰 경우 위와 같이 3가지로 나눌 수 있는데 그렇다면 어떻게 길이를 구분할 지 고민해본 끝에 좌표 이동을 생..

오늘 풀어볼 문제는 LeetCode의 Exchange Seats 문제입니다. 1. 문제 및 예시 2. 문제풀이 이번 문제는 앞뒤로 바꾸는 쿼리 결과를 조회하면된다. 그렇다면 곰곰히 생각해보면 2의 배수의 경우는 앞뒤로 변경이 가능하지만 2의 배수에서 -1인 경우는 마지막의 값은 변경이 불가능하다. 이 말은 즉슨 Mod(ID, 2) = 1 공식에 따라서 문제를 풀면 된다. 3. 코드 /** * LeetCode : Exchange Seats * URL :https://leetcode.com/problems/exchange-seats/ */ SELECT ID, IFNULL(CASE WHEN MOD(ID, 2) != 0 THEN LEAD(student) over() ELSE LAG(student) over() ..

오늘 포스팅 할 내용은 LeetCode에서 Trips and Users문제를 풀어봤습니다. 1. 문제 설명 2. 문제 예시 3. 문제 풀이 이번 문제는 driver_id와 client_id만 잘 구분해주면 된다. 말 그대로 cancel의 확률을 구하면 되는데 사용자 중 banned가 yes라면 제외한 확률을 구해주면 된다. 그래서 날짜별로 평균값을 구해주면 되는 문제이다. /** * LeetCode : Trips and Users * URL :https://leetcode.com/problems/trips-and-users/ */ /* * AVG 사용 */ select trip_totals.day, ,round(avg(trip_totals.status like '%cancel%'), 2) as "Canc..

오늘 포스팅 할 내용은 LeetCode 문제 중 하나인 Rising Temperature문제를 풀어봤습니다. 1. 문제 설명 2. 문제 예시 3. 문제 풀이 이번 문제는 전일 대비 온도가 높은 ID를 출력해주면 됩니다. 그렇다면 해당 문제를 접근한는 방법은 현재일과 현재일에서 DATE_ADD를 통해 1일을 추가한 일자와 비교하여 온도를 비교해주면 된다. 또 다른 방법은 DATEDIFF를 이용하여 날짜의 차이가 1일인 경우 온도를 비교해주면 된다. /** * LeetCode : Rising Temperature * URL : https://leetcode.com/problems/rising-temperature/ */ # DATEDIFF를 통해 날짜의 차이를 구하는 방식 select w1.id from W..