새벽 기상을 꿈꾸는 루민

안녕하세요 세기무민입니다. 이번 포스팅에서는 그리디 알고리즘에 대해 다뤄보도록 하겠습니다. 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() ..