오뚝이개발자

문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 나의 풀이 처음엔 그냥 2중 for문을 써서 각 시작점마다 보석 종류를 모두 포함하는 끝지점을 검출하면 break하고 다음 시작점부터 탐색하는 알고리즘을 짰는데 역시나 시간초과에 걸렸다. 개선한 풀이는 다음과 같다. start, end의 투포인터를 사용한다. 처음엔 둘다 0번째 인덱스로 초기화 한다. start부터 end까지의 보석이 전체 보석 종류를 포함하면 start를 증가시키고, 모자라면 end를 증..

문제 https://programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 나의 풀이 n(총 버스 수)과 t(버스 간격)를 사용해 버스가 정차하는 시간 저장 timetable의 시간 모두 분으로 변환 후 오름차순으로 정렬 m(버스 수용 가능 최대 인원)을 이용해 각 버스가 정차하는 시간마다 탈 수 있는 사람 저장 가장 늦..

dfs, bfs, 백트래킹 문제들을 풀 때 기존의 2차원 리스트를 변경하고 원상태로 다시 되돌려야 할 때가 있다.(예컨대, 방문한 곳의 값을 변경한다거나, 특정 조건에 따른 위치의 값을 변경한다거나) 이 때 만약 처음의 상태를 arr에 저장해두었다고 하고, 이를 복사해 탐색하는 함수(예컨대, dfs나 bfs)의 인자로 넘겨 그래프 탐색을 한다고 하자. 만약 arr를 그대로 함수의 인자로 넘겨버리면 arr의 값이 변경된 채로 다음 탐색을 이어가기 때문에 이를 재사용할 경우에 문제가 된다. 이럴 때 사용할 수 있는 것이 바로 deep copy다. deep copy는 copy라는 모듈을 import해서 사용할 수 있다. >>> import copy >>> a = [[1,2],[3,4]] >>> b = copy..

텍스트 파일의 행수를 알아야 할 때가 있다. 물론, 단순히 해당 파일을 열어 마지막 행수를 보면 된다. 하지만 해당 파일이 대용량의 데이터를 담고 있다면 선뜻 열어보기가 쉽지 않다. 그만큼 많은 메모리를 순간적으로 잡아먹기에 컴퓨터가 다운될 수도 있다. 그럴 땐 리눅스의 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..