Jesse's devlog

더보기 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 그렇지 않으면 J를 인쇄합니다. 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다. 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의..

오늘도 코딩테스트 준비 겸 프로그래머스에서 문제를 풀어 보았습니다. 위에 사진은 보트에 관한 문제 풀이라서 넣어보았어요 ㅎ 보트에는 2명까지만 탈수 있습니다. 즉, 필요한 구명보트의 개수를 최소값으로 줄이기 위해선 보트마다 최대한 주어진 무게 제한에 가깝게 채워야 된다는 얘기가 됩니다. 어떻게 2명을 선정할것인지가 관건인 문제네요. 2명을 선정하는 데에는 여러가지 방법이 존재 합니다. 제가 생각해낸 방법은 무게 제한을 넘지 않는 선에서 가장 무거운 사람과 가벼운 사람을 매치 시키는 방법 입니다. 예를 들면, 30kg, 50kg, 70kg, 50kg의 인원들이 있고 무게 제한이 100kg라면, 답은 이렇게 30kg와 70kg을 태워서 100kg를 만들고 50kg 2명을 태워서 100kg를 만드는 겁니다. ..

우선 사전의 역할을 하는 리스트를 만들어야 겠다는 생각을 했습니다. 리스트에는 문제에서 제시해준것처럼 알파벳 대문자 A부터 Z까지 넣었습니다. 저는 리스트를 썼는데 이 부분은 딕셔너리를 써도 무방하다고 생각합니다. 여기서 input으로 들어오는 메시지를 리스트로 바꿔 넣었습니다. 이거는 pop을 써서 앞에서부터 하나씩 제거해나가기 위함인데요. string은 pop function을 지원하지 않기 때문에 그랬습니다. 다른 방법으로는 slice를 써서 string을 압축하려는 만큼씩 계속 자르는 방법도 있겠네요. def solution(msg): answer = [] dictionary = [chr(i) for i in range(65,91)] msg_lst = [ch for ch in msg] comp =..

오늘도 프로그래머스에서 문제들을 풀어 보았습니다. Input은 오직 괄호로만 이루어져 있습니다. 올바른 괄호인지 아닌지만 체크해서 True나 False로 리턴하면 되는 문제입니다. Leetcode에도 비슷한 문제가 있고 Hackerrank에도 비슷한 문제가 있는걸로 봐서 굉장히 유명하고 자주 나오는 유형 같습니다. 1. input string s를 처음부터 끝까지 살펴볼것이기 때문에 for loop을 쓴다. 2. 왼쪽 괄호와 오른쪽 괄호의 개수를 세자 3. 왼쪽부터 loop을 돌리는데 오른쪽 괄호가 더 많다면 그건 올바르지 않은 괄호다. def solution(s): opened, closed = '(', ')' cnum, onum = 0,0 for ch in s: if ch == closed: cnum..

오늘은 프로그래머스에서 이진 변환 트리를 풀어보았습니다. 주어진 숫자는 오직 0과 1로만 이루어져 있고 먼저 0을 모두 제거합니다. 그 후에 남은 1이 몇개인지 세고 1의 개수를 다시 이진법으로 변환합니다. 이 작업을 마지막 1이 남을때까지 반복하는 해야 되네요. 그리고 마지막에 0의 개수와 총 몇번이나 이 과정을 거쳤는지 list 안에 넣어서 리턴하면 됩니다. 1. 0을 제거하고 남은 1의 개수를 이진법으로 변환하는 과정을 몇번이나 해야 되는지 알수 없다. 2. 그러므로 첫 loop은 while loop으로 (1이 되면 loop이 깨지는 구조) 3. 안에 또 다른 loop이 필요한가? 그렇다 1의 개수를 세야 한다 4. 굳이 0을 제거할 필요가 있는가? 아니다 1의 개수만 세서 이진법으로 변환한 숫자가..

같은 문자 두개가 붙어 있다면 제거가 되는 룰이 있네요. 그렇게 계속 제거를 해 나가다가 "cdcd"처럼 제거가 되지 않는 경우에는 0을 리턴하고 모두 제거가 되면 1을 리턴하면 되는 문제 입니다. 생각의 과정 1. 우선 입력된 문자열 s를 위한 loop이 하나 필요할것 같다. 2. 그 후에 안에 서로 연속된게 있는 loop을 하나 더 넣어서 nested loop을 만들까? 이러면 많이 느려질것이다. 3. 연속된게 2개 이상이라도 어차피 한번에 제거될수 있는 개수는 2개뿐이다. 4. 그렇다면 stack을 따로 만들어서 끝자리끼리만 비교해보자 풀이 def solution(s): stack = [] s_list = [ch for ch in s] while s_list: temp = s_list.pop() i..

문제를 읽어보니까 Finn이라는 친구가 수학을 참 좋아하나 보네요...ㅎ 문제가 그리 어려워 보이진 않네요. 주어진 숫자를 연속된 숫자로 표현하는 방법이 몇가지나 있나 찾는 거군요. 1. nested loop을 써서 1부터 더해보자. 그 다음은 2 그다음은 3 이런식으로... 2. 문제가 너무 쉽게 풀린다. nested loop이니 효율성을 고려해보자 3. 일단 위에서 모든 숫자는 덧셈 없이 그대로 표현할수 있는 한가지 방법이 있으니 최소 1이다 def solution(n): answer = 1 middle = int(n/2) for i in range(1,middle+1): temp = 0 for j in range(i,middle+2): temp += j if temp == n: answer += 1..

요즘 시간 날때마다 프로그래머스에서 문제를 하나씩 풀어보고 있습니다. 문제 내용은 그리 길지 않네요. 이상하게 문제 내용이 길고 제한 사항이 많으면 시작부터 좀 꺼려 집니다.... 다른 문제를 고를껄 그랬나 하지만 이 문제는 짧고 원하는게 명확하네요. 주어진 string에서 최소값과 최대값만 찾아서 리턴하면 되는군요 1. string 안에서 숫자들을 뽑아내서 리스트를 만드는게 먼저일것 같다 2. 어떻게 숫자 사이 사이에 있는 공백들을 제거할것인가? 3. loop을 돌려도 되지만 그냥 split()을 쓰자. 4. 그 후에 리스트에서 최소값과 최대값을 찾는건 매우 쉬움 def solution(s): s_list = s.split() num_list = [int(x) for x in s_list] maxi, ..

요즘은 시간 날때마다 알고리즘 문제를 하나씩 풀고 있는데요. 프로그래머스에 있는 최솟값 만들기 문제를 풀어 봤습니다. "두개의 주어진 리스트에서 각각 한개씩 뽑아 두 수를 곱한 값을 더했을때 최솟값을 찾아라" 언뜻 보면 굉장히 골치 아픈 문제 같아 보입니다. 더할수 있는 모든 경우의 수를 찾아야 되나? 처음 봤을때 이런 생각 하신 분들 많을것 같아요. 곱했을때 1. 곱했을때 최소값을 만드려면 어떻게 해야 될까? 2. 첫번째 리스트에서 가장 작은 숫자와 두번째 리스트에서 가장 큰 숫자를 곱하면 최소값을 만들수 있다. 3. 마찬가지로 첫번째 리스트에서 가장 큰 숫자가 나온다면 두번째 리스트에서는 당연히 가장 작은 숫자가 나와야 함 def solution(A,B): answer = 0 A.sort() B.so..

설명 완전 탐색이라는건 모든 경우의 수를 전부 찾고 그중에서 답을 찾는 알고리즘을 뜻한다. 완전 탐색을 하는 방법에는 여러가지가 있는데 이중에 가장 대표적인게 Brute-Force Search 또는 Brute-Force Attack이라고도 불린다. 단어 그대로 직역을 해보자면 무차별 검색 또는 무차별 공격이라고 나오는데 무슨 말인지 잘 감이 오질 않아서 영어로 된 설명을 좀 찾아보았다. "Trying every single possibility rather than advanced technique to improve efficiency" 나는 이게 좀 더 와 닿았다. 시간 효율 고려하지 말고 가능한 경우의 수는 다 보자는 얘기 였다. 그렇다면 최소한 문제 내에서 시간 제한을 넉넉하게 주지 않을까 하는 ..