오뚝이개발자

텍스트 파일의 행수를 알아야 할 때가 있다. 물론, 단순히 해당 파일을 열어 마지막 행수를 보면 된다. 하지만 해당 파일이 대용량의 데이터를 담고 있다면 선뜻 열어보기가 쉽지 않다. 그만큼 많은 메모리를 순간적으로 잡아먹기에 컴퓨터가 다운될 수도 있다. 그럴 땐 리눅스의 wc(word count) 명령어를 사용하면 된다. wc -l filename 옵션에는 아래와 같은 것들이 있다. -l : 행 수를 센다. -w : 단어 수를 센다. -c : 문자 수를 센다. -L : 가장 긴 라인의 길이를 출력한다.

트리를 순회하는 방법은 preorder, inorder, postorder로 크게 3가지가 있다. 여기서 소개하려고 하는 내용은 이러한 순회를 "어떻게" 구현하는지에 관한 것이다. 가장 보편적인 것은 물론 재귀를 이용하는 것이나, 반복문을 통해서도 얼마든지 구현 가능하다. 참고로 트리노드의 정의는 아래와 같다고 하자. # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right 편의상 inorder를 구현하는 것으로 한다. 재귀(Recursive)를 통한 구현 class Solution: # ..

파이썬에서 사전순으로 문자열들을 정렬하기는 쉽다. sort()를 사용하면 정렬이 된다. sorted()를 사용하면 원본 리스트를 변경하지 않고 정렬이 가능하다. a = ['cd', 'ef', 'ab'] a.sort() print(a)# ['ab', 'cd', 'ef'] 하지만 만약 문자열 자체를 정렬할 필요가 있는 경우 파이썬에서는 어떻게 해야할까? 예컨대, s="adfe"라는 문자열을 정렬해서 "adef"로 만들려고 한다. s = "adfe" s1 = s.sort()# wrong s2 = sorted(s)# ['a','d','e','f'] s3 = ''.join(sorted(s))# "adef" 먼저 그냥 s.sort()를 쓰면 안된다. - str type에 sort()라는 메소드가 없기 때문(이유는 ..

list와 tuple은 모두 순차자료형이다. A = [1, 2, 3]# list B = (1, 2, 3)# tuple 하지만 차이점은 리스트의 경우 원소를 바꿀 수 있으나(가변적), 튜플의 경우 원소의 값을 변경할 수 없다(불변적)는 점이다. 이 같은 차이가 왜 중요한 이유가 있다. 만약 아래와 같이 "리스트"를 key로 하는 딕셔너리를 만들고 싶다고 해보자. A = [1,2,3] B = [4,5,6] dictionary = {} dictionary[A] = 1 dictionary[B] = 2 안타깝지만, 위의 코드는 제대로 실행되지 않는다. 아마 실행해보면 TypeError: unhashable type: 'list'라는 에러 문구가 뜰 것이다. 이유는 파이썬에서 딕셔너리의 key값은 hash가 가능토..

linked list를 정렬하는데 추가적인 메모리를 쓰지 않고 O(nlogn)의 시간복잡도로 하기 위해선 어떻게 해야할까? 답은 merge sort를 쓰면 된다!!!! 그런데 조금 복잡한 부분이 일반적인 array의 경우 index로 분할하여 정렬하면 되는데 linked list의 경우 어떻게 나누어야 하는지이다. 이를 위해선 3개의 포인터를 쓰면 된다. 그 세 포인터를 각각 p,slow,fast라 해보자. p,slow,fast가 차례로 한 칸씩 전진하는데 p->slow->fast의 순서대로 나아간다. 이 때, fast가 None이거나 fast.next가 None이 되면 p.next를 None으로 만들어주고 p와 slow로 linked list를 분할한다. 그럼 p가 가리키는 연결리스트가 l이 되고, s..

nums=[1,2,1], target=3일 때, nums에서 원소의 합이 target인 부분집합은 몇 개일까? 답은 (1,2), (2,1)로 2개이다. 그렇다면 이를 구하기 위한 알고리즘은 무엇일까? 이러한 문제를 counting subsets with given sum이라 한다. 다른 문제에도 자주 이용되니 알아두자! 가능한 모든 경우를 파악해보면 된다. 그런데 이 때, 각 숫자는 합에 포함되거나 안되거나 둘 중 하나의 선택지를 갖는다. 그림으로 나타내면 아래와 같다. 이를 풀기 위해선 dp를 사용하면 된다. 위와 같이 dp를 모두 채운 뒤 dp[-1][-1]이 답이 된다. 관련 문제 leetcode.com/problems/target-sum/ Target Sum - LeetCode Level up y..

"abc"와 "bca"는 Anagram이다. anagram이란 이처럼 size가 같고, 같은 알파벳으로 이루어진 문자열을 말한다. 그럼 이러한 anagram을 찾으려면 어떠한 알고리즘을 써야할까? 가령 s="abcdebacb", p="cab"일 때, s에서 p와 anagram인 문자열의 인덱스를 찾는다고 해보자. 그럼 어떠한 것이 같아야 anagram이라고 할 수 있을까? size - p의 사이즈만큼 s를 slicing하면 되므로 간단!! 사용하는 알파벳 종류 등장하는 알파벳의 빈도수 이 땐, 2와 3을 비교하기 위해선 비트마스크를 사용하면 된다. 알파벳은 총 26개이므로 26개의 array를 만들고 각 알파벳의 등장 빈도수만큼 + 해준다. p="cab"이므로 p의 비트마스크 p_mask=[1,1,1,0..