Jesse's devlog

오늘도 프로그래머스에서 문제들을 풀어 보았습니다. 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" 나는 이게 좀 더 와 닿았다. 시간 효율 고려하지 말고 가능한 경우의 수는 다 보자는 얘기 였다. 그렇다면 최소한 문제 내에서 시간 제한을 넉넉하게 주지 않을까 하는 ..