algorithm
-
CTCI | 분할(Partition)Algorithm/Linked List 2024. 4. 3. 17:53
값 x가 주어졌을 때 x보다 작은 노드들을 앞에, 크거나 같은 노드들을 뒤에 오게하는 코드를 작성하라 Linked List에서 약간의 Sorting을 해야하는 문제다. 복잡해 보이지만, 생각보다 단순하다. LinkedList 두개를 생성해서, x보다 작은것은 첫번째 리스트에, 큰것은 두번째 리스트에 추가하고, 나중에 그 두 리스트를 연결만 하면 된다. 여기서, 난이도가 쉬운 이유는, 오른쪽 노드 조합에서 x가 꼭 앞에 오지 않아도 되기도 하고, 각각의 Linked List가 Sorting되지 않아도 되기 때문이다. 그림으로 한번 나타내보자. 작은 숫자들 리스트의 첫 노드가 될 dummy node와 큰 노드들의 리스트를 만들 dummy node를 만들어서, 해당하는 숫자를 그 뒤에 쭉 붙인 후, 원래 li..
-
CTCI | 중간 노드 삭제Algorithm/Linked List 2024. 4. 2. 23:18
Cracking the Coding Interview Linked List에서 중간 노드 하나를 삭제해라 중간노드를 삭제하는 방법은 여러가지가 있다. 먼저 중간값을 구해야 하는데, 어떻게 중간 노드를 파악할 수 있을까? 먼저, 가장 간단한 로직은, 처음부터 끝까지 한번 travel을 한 후, 노드 갯수를 count해서 2로 나누는 것이다. 그런데 그렇게 되면 다시한번 반절을 가서, 1.5N의 여행을 해야한다는 단점이 있다. 여기서 우리는, 이전 문제에서 사용했던 two pointer를 사용하게 되면, 조금 더 효율적으로 풀어볼 수 있다. slower pointer와 faster pointer를 사용해서, 한 포인터는 한칸씩, 한 포인터는 두칸씩 가게 되면, 빠른 걸음을 걷는 포인터가 맨 끝, null에 ..
-
Abstraction, Condition and More in Scratch | Harvard CS50 Week 0Computer Science/CS 50 Harvard 2021. 10. 31. 14:05
하버드 CS50 강의를 한글로 정리한것입니다. loop 위와같이 코드를 작성하면 고양이는 1초씩 간격을 두고 야옹~ 하고 우는 소리를 낸다. 하지만 이 코드에는 한가지 개선사항이 있다. 무엇일까? 지금은 3번만 울게끔 하기때문에 괜찮지만 만약 100번을 울게 하고싶다면? 코드가 아주 길어질것이다. 이럴때 사용할 수 있는것이 바로 loop이다. 마치 돌림노래처럼, 똑같은 부분을 반복하는것이다. repeat이라는 블럭을 사용해서 "울고 - 1초기다리기" 를 10번 반복 시키면, 위에 있는 코드와 같은 결과물을 만들어 낼수 있는데, 코드의 길이도 짧고, 개발자의 시간도 훨씬 절약된다. 만약 10번 반복을 이전과 같이 개발했다면 play sound 블록 10개, 1초기다리기 블록 10개, 총 20개의 블록이 필..
-
Algorithms | Harvard CS 50 Week 0Computer Science/CS 50 Harvard 2021. 10. 29. 12:48
모든 내용은 하버드의 CS50 수업을 한글로 정리한것입니다. 다시 처음으로 돌아가서, 1과 0, binary bits로 우리는 컴퓨터가 알아들을 수 있도록 input과 output을 나타낼 수 있게 되었다. 그게 색깔이 될수도, 숫자, 알파벳, 한글, 음악, 이미지 또는 영상이 될 수 있다. 그렇다면, 이것들을 처리하는것은 무엇인가? 바로 알고리즘이다. Contacts 핸드폰의 전화번호찾는 Contacts기능을 생각해보자. 한글 또는 영문 순서대로 이름이 정렬되어있고, 각각의 이름에는 전화번호와 또다른 저장된 정보들을 볼 수 있다. 예전에는 어땠을까? 어렸을때 기억을 해보면 전화번호부라는것을 사용해서 번호를 찾았었던적이 있었다 (지금도 상호명등을 볼 수 있는 전화본호부가 존재하는것으로 보인다). 전화번호..