이진 탐색은 정렬된 배열에서 원하는 value의 element를 O(logn) 이라는 좋은 성능으로 수행할 수 있는 알고리즘입니다.


문제 해결 방법은 간단합니다.


이미 정렬이 되어 있는 배열이기 때문에 배열중에 중간에 위치한 값을 체크해서 체크해야 하는 element들의 수를 반씩 줄이는 방법입니다.


import unittest
from typing import List


def binary_search(target: int, a: List[int]) -> int:
start, end = 0, len(a)
mid = (start + end) // 2
while mid != 0 and mid != len(a):
if target > a[mid]:
start = mid + 1
mid = (start + end) // 2
elif target < a[mid]:
end = mid - 1
mid = (start + end) // 2
else:
return mid

return -1


class TestCase(unittest.TestCase):
def test(self):
input_a = [i for i in range(100)]
target = 55
expected = 55

input_a2 = [i ** 2 for i in range(10)]
target2 = 81
expected2 = 9

input_a3 = [i ** 2 for i in range(10)]
target3 = -81
expected3 = -1

self.assertEqual(binary_search(target, input_a), expected)
self.assertEqual(binary_search(target2, input_a2), expected2)
self.assertEqual(binary_search(target3, input_a3), expected3)


코드를 보시면 보는 것 과 같이 가운데 값을 체크해서 원하는 값보다 크면 오른 쪽을 버리고,


작으면 왼쪽을 버리고 길이를 반으로 줄인 배열을 다시 같은 방법으로 줄여가면서 원하는 값을 찾습니다.


코드는 github으로도 확인하실수 있습니다.


https://github.com/baidoosik/ProblemSolving/blob/master/Search/binary_search.py



감사합니다.











오늘 풀어본 문제는 프로그래머스에 있는 완주하지 못한 선수라는 문제입니다.


링크: https://programmers.co.kr/learn/courses/30/lessons/42576



이 문제에 대해 간단히 설명을 하자면


마라톤에 참여한 선수들의 이름 리스트가 있고, 그 중 완주한 선수들의 이름 리스트가 있습니다.


완주하지못한 선수는 단 1명 뿐입니다. 그러므로 참여선수리스트와 완주한 선수들의 리스트의 길이 차는 1입니다.



참가자 중에는 동명이인이 있습니다.



먼저, 해당 문제에서는 어떤 자료구조를 선택해서 문제를 해결하느냐가 핵심일 것 같습니다.


생각해본 문제 풀이 방법은


1) 정렬을 해서 비교하면 다른 원소일 때 해당 값을 리턴 하는 방법. 정렬하는데 O(nlogn)의 시간이 소요되는데 리스트가 2개이고 또 마지막에 순회할 때 O(n) 의 시간복잡도가 필요하기 때문에 좋은 방법이라고 생각하지 않았습니다.


2) 해쉬 자료구조를 사용해서 이름을 키로 사용한 후에 해당 키에 접근에서 빼는 방식으로 하면 O(n) 의 시간복잡도를 2번 필요로 하기 때문에 위에 방법보다 더 좋은 방법이라고 생각했습니다.




제가 작성한 코드입니다.


먼저 완주한 선수 리스트를 dictonary에 넣어준 후에


참가자리스트에 있는 선수들을 나온 순서로 체크해서 이미 해당 값의 key의 value가 0이 되거나 value이 없는경우 해당 key 를 리턴해주도록 작성하였습니다.




복사 가능한 코드


def solution(participant: list , completion:list ) -> str:

    dictionary = {}

    for v in completion:

        if dictionary.get(v):

            dictionary[v] +=1

        else:

            dictionary[v] = 1

    

    for v in participant:

        if dictionary.get(v):

            if dictionary == 0:

                return v

            else:

                dictionary[v] -=1

        else:

            return v

        

    return answer



다른 분이 작성한 코드 중에서 파이썬이 collections 패키지의 Counter 를 사용해서 문제를 해결한 분이 있어서 소개드리려고 합니다.


collections 패키지는 파이썬에서 제공하는 강력한 컨테이너 데이터 타입입니다.


그 중에서 Counter는 hashable 객체의 카운팅을 위한 Dict의 서브클래스입니다. 


즉, 위에서 제가 dictonary를 사용해서 해당 키의 빈도를 counting한 경우에 사용하면 딱인 데이터 타입입니다.




이런식으로 리스트를 이용해서 생성하면 다음과 같이 dictionary가 만들어집니다.



Counter 를 사용한 코드입니다.




코드가 보다 간결해진 것을 확인할 수 있습니다.



문제를 풀다 보면 다양한 방법으로 푼 다른 분들의 

코드를 볼 수 있어서 많이 도움이 됩니다.


혹시, 잘못된 부분이 있거나 궁금하신점이 있으면 댓글 남겨주세요.


감사합니다.







알고리즘 문제를 풀다보면 10진수에서 2진수로 2진수에서 10진수로 변경을 필요로 하는 문제가 많이 있습니다.


이러한 문제가 나오는 이유는 컴퓨터가 애초에 2진수 체계로 만들어져 있기 때문에 컴퓨터에 대한 이해에 있어서 진법을 이해하는 것이 중요하기 때문이라고 생각합니다.



실제로 컴퓨터에서 곱하기 연산이나 나누기 연산을 한 자리 씩 shift 시키면서 하는 것을 보면


흡사 십진수를 이진수로 변환하는 프로그래밍과 유사하다는 느낌도 받았습니다.(저의 개인적인 생각입니다...!)




십진수를 이진수로 바꾸는 방법은 십진수를 2로 나눈 몫, 나머지 를 이용해서 각 자리를 정해줍니다.


19 이라는 수가 있다면


맨처음 2로 나누면 몫 9이고 나머지는 1 이기 때문에 최하위 bit 1이되고


다시 9를 2로 나누면 몫 4 이고 나머지는 1이기 때문에 그 다음 자리의 bit 1이 됩니다.


계속에서 끝까지 살펴보면 4를 2로 나누면 몫2 나머지 0 그 다음 자리의 bit 0


그 다음 2를 2로 나누면 몫 1 나머지 0 이니깐 그 다음 자리의 bit 0


이제 1을 2로 나누면 몫 0 나머지 1 이니깐 최상위 비트는 1 그리고 몫이 0이므로 루프를 종료합니다.


그래서 10001(2) 라고 변경이 됩니다.




위의 과정을 코드로 구현 하면 10진수에서 2진수로 변경하는 함수가 됩니다.


그리고 저위에 나누는 수를 2 대신 3으로 하면 3진수로 변경하는 함수가 됩니다.



제가 구현한 코드를 보면 다음과 같습니다.





테스트코드에서 사용한 bin 함수는 파이썬에서 10진수를 2진수로 변환하는 builtin 함수입니다. 


bin(20) 을 출력하면 '0b10100' 문자열로 앞에 0b를 출력하기 때문에 이부분을 제외하기 위해서 slicing을 해서 int로 형변환을 하였습니다.




복사 가능한 코드


def change_binary(n : int) -> int:

    result, idx = 0,0

    while (n >=1):

        remainder =n % 2

        n = n // 2

        result += (10**idx)* remainder

        idx +=1

    return result



위에서 이야기 한 것처럼 이번에는 3진수로 변환하는 함수를 그대로 구현보겠습니다.





3진수로 변환하는 함수는 단순히 나누는 수를 2->3으로 변경한 것입니다. 


그렇기 때문에 2진수로 바꾸는 방법을 이해하신 분은 4진수 5진수 등도 쉽게 변경하는 함수를 만들 수 있을 것 입니다.






조언이나 피드백은 언제나 감사합니다.


감사합니다.








해당 문제는 프로그래머스에서 제공하는 문제에 대한 개인적인 풀이입니다.


더 좋은 방법이 있거나 의견이 있으신분은 댓글 주시면 자유롭게 의견교환 하실 수 있습니다.




이번에 풀어본 문제는 주식가격이라는 문제입니다.


초단위당 주식 가격이 리스트로 매개변수로 주어질 때 각 시간에 주식가격이 유지된 기간이 몇 초인지 return 하는 함수를 작성하는 문제입니다.


문제에서 제한 사항이 주어졌지만, 혹시 주어지지 않았다면 면접시에는 수의 범위나 리스트의 대략적인 크기에 대해서 물어보시면 더욱 좋을 것 같습니다.



여기서 저는 가격이 유지된다는 의미를 가격이 아예 같다라는 의미로 받아들였는데 예시를 보니 하락 하지 않은 상태를 의미하는 것 이었습니다.





해당 문제에 대한 제 코드입니다.


먼저, 가격이 유지되었는지 확인하는 부분은 비교해보는 방법 뿐이고, 필요한 연산을 위해서 첫번째 for 루프에서 이미 계산한 index를 제외하고 시작하는 index라는 표현을 하기위해서 start라고 변수명을 지어서 사용했습니다. 


두 번째 for loop에서 


1) 유지되어 있는 기간을 찾으면 더 이상 비교해볼 필요가 없으모로 break 를 사용해서 그 당시에 index에서 start를 빼줘서 유지되는 기간을 반환할 리스트에 더해줬습니다.


2) 계속 유지된 경우라면 마지막 for loop에서 i-start가 유지된 기간이 되므로 아래와 같이 작성하면 코드가 조금 더 간결해질 것 이라고 생각했습니다.





복사 가능한 코드


def solution(prices: list) -> list:

    answer = []

    for start in range(0, len(prices)):

        pivot = prices[start]

        for i in range(start, len(prices)):

            if prices[start] > prices[i]:

                break

        answer.append(i-start)

    return answer




읽어 주셔서 감사합니다. 


조언이나 피드백은 언제나 환영입니다.


  1. ㅎㅈ 2019.01.07 15:20 신고

    글 올려주셔서 고마운데 여러군데 봐도 설명이 이해가 안 되는 제 머리....ㅠ pivot 변수는 등장 이후 안 쓰인거 같은데 왜 필요한건가요...ㅠ



다시 알고리즘 공부를 시작해보려고 쉬운 문제부터 다시 천천히 풀어보고 있습니다.



최근에 읽고 있는 책에서 기술 문제를 푸는 과정이나 접근방법에 대해서도 배우고 있어서 간단하게 기술 문제를 푸는 과정에 대해서 간단히 소개하고 문제를 풀어보도록 하겠습니다.



Cracking The Code Interview에서 소개한 기술 문제를 푸는 다섯 단계


1. 면접관에게 문제의 모호한 부분에 대해 묻는다.


2. 알고리즘을 설계한다.


3. 가상 코드 


4. 코드


5. 테스트




문제:


문자열의 입력을 받아서 해당 문자열에 들어 있는 소괄호가 올바른지 판단하는 함수를 만드시오.



알고리즘에서 체크해야하는 부분


- 괄호는 열리면 닫혀야 한다. (즉, 열리면 닫혀야함)


- 괄호는 열리는게 먼저다. 즉, 항상 열린 후에 닫혀야 한다.



코드:


def parenthesis_validator(a: str) -> bool:

    total: int = 0

    for w in a:

        if w == "(":

            total +=1

        elif w==")":

            total -=1

            if total <0:

                return False

    return True if total==0 else False



테스트:


class ValidatorTest(unittest.TestCase):

    testcase1 = "((abcd))"

    testcase2 = "(((abcd))"

    testcase3 = "((abcd)))"

    testcase4=""

    

    def test(self):

        self.assertEqual(parenthesis_validator(self.testcase1), True)

        self.assertEqual(parenthesis_validator(self.testcase2), False)

        self.assertEqual(parenthesis_validator(self.testcase3), False)

        self.assertEqual(parenthesis_validator(self.testcase4), True)


test = ValidatorTest()


test.test()



오랜만에 쉬운 문제풀이를 하나 포스팅했습니다. 


이제부터 꾸준히 알고리즘 문제를 풀고 공유하도록 하겠습니다.


감사합니다.






어떤 문자열을 URL 화 하고 싶을 때가 있습니다.


예를 들면 공백을 기준으로 URL 화 하거나 어떤 기호를 기준으로 URL 화 할 수 있습니다.



'hello world' -> 'hello/world'



이를 파이썬 코드로 만들어 보겠습니다.



해결 방법 : 순회하면서 특정 문자일 때 / 로 변환하여 저장.




매일 간단한 문제라도 푸려고 하고 있습니다.


감사합니다.








오랜만에 다시 알고리즘 문제


기본 문제부터 파이썬 알고리즘 문자열 중복 체크하기.



문자열 중복을 체크하는 방법으로 


1) 중복된 element를 제거해주는 자료구조인 set 을 이용해서 해결.


2) 단순하게 for 문으로 element 들을 순회 하면서 중복을 체크.



1) 자료구조 set 을 이용.





2) for 문을 순회





이제 한 동안은 알고리즘과 자료구조를 공부를 열심히 해보려고 합니다.


감사합니다.






리스트에서 자주 출현한 숫자 구하기

주사위를 굴려서 나온 숫자를 리스트에 순서대로 적은 값과 k를 입력 받았을 때, 리스트에 자주 출현한 k개의 숫자를 리턴하는 코드를 작성.

  • ex) 주사위 던진 결과 [3,2,3,1,2,5,3,6,2,4] 이고 k가 2이면 2가 세번 3이 세번으로 자주출현한  [2,3]을 출력.
  • 예를 들어, 주사위 던진 결과가 [1,1,1,2,2,2,3,3,4,4] 이고 k 가 3이면 [1,2,3] or [1,2,4] 를 출력


접근 1)

dictionary + sorting 으로 구현

sorting O(nlogn) 의 시간 복잡도를 필요. 코드는 간결한 편.



-> lambda 함수를 이용해서 정렬 후에 k개의 key 를 리턴



접근 2)

dictionary + while 문으로 구현

큰 k값을 구할 때 리스트를 순회하면서 k개의 값을 뽑으므로 O(kn) 의 시간 복잡도를 필요로 함. 성능이 더 좋음.

하지만, 코드는 위에 코드보다 조금 긴편.



오늘도 알고리즘 문제를 파이썬으로 해결해봤습니다. 


감사합니다.







안녕하세요.



오늘은 HEAP TREE 구조에 대해서 알아보겠습니다.


MAX Heap Tree 는 부모 노드가 자식 노드보다 크기만 크면 되는 구조를 가진 자료형입니다. 


(반대로 Minium heap tree 도 있습니다.)





부모노드가 자식노드 보다 큰 특성을 가지고 있으니 가지고 있으니 


당연히 ROOT 노드는 가장 큰 수가 됩니다.



그렇기 때문에  가장 큰 수와 가장 작은 수를 O(1) 의 성능으로 가져올 수 있다는 장점이 있습니다.



그렇기 때문에 최대 값, 최소 값을 위해 정렬이 필요한 경우 사용하면 O(N) 의 성능으로 heap 구조를 만들고 


최대, 최소 값을 o(1)의 성능으로 가져올 수 있습니다.



다음에는 heap sort에 대해서도 구현해보겠습니다.


감사합니다.



나는 어떤 과정으로 Problem Solving을 하는지 , 


즉 문제를 해결해나가는지 정리 정리해보면서 그 과정에 맞추어 triple sum이라는 문제를 풀어봤다.


triple sum은 어떤 배열이 주어졌을 때 배열의 3가지 원소로 0을 만드는 경우의 수를 찾는 문제이다.



나는 어떤 과정으로 문제를 푸는지 생각해봤다.




1. 코딩을 하기 전


문제 파악 : 어떤 문제인지 이해


문제 쪼개기: 해결해야하는 문제를 나눈다.


나눈 문제를 어떤 로직이나 알고리즘 모듈로 해결할지 고민한다.



2. 코딩


위에 생각한 내용을 바탕으로 해당 기능이 수행되도록 구현한다.



3. 코딩 후


테스트 / 디버깅 : 테스트 및 버그 수정


시간/공간 복잡도 계산 및 개선점 찾아보기





다시 위 과정 순서대로 triple sum이라는 문제를 보면



코딩 전


문제는 명확하기 때문에 바로 이해할 수 있고, 


task를 두 개로 나눈다.



1) 리스트에서 가능한 3가지 수를 뽑아서 모든 리스트로 만든다. 


2) 그리고 그 리스트에서 합이 0인지 확인하고, 합이 0인 배열을 return 한다.



이제 코딩


def pick_triple_number(alist):

    result_list = []

    for i in range(len(alist)):

        for j in range(i+1,len(alist)):

            for k in range(j+1, len(alist)):

                result_list.append([alist[i], alist[j], alist[k]])

    return result_list



def triple_sum(alist):

    result = pick_triple_number(alist)

    final = []

    [final.append(i) for i in result if sum(i)==0]

    return final



테스트




시간/공간 복잡도, 개선점 찾기


생각해보면 전체 리스트를 저장할 필요가 없다. 애초에 조건에 해당하는 리스트만 저장하면 메모리 및 실행 속도를 줄일 수 있다.




 


Triple sum 이라는 문제를 풀면서 내가 문제를 풀 때 어떤 과정으로 문제를 해결하는지 정리해봤다....


부족한게 많겠지만 이 또한 과정이겠지...!




+ Recent posts