읽기 편한 코드 VS 이해하는데 시간이 걸리지만 빠른 코드 나는 제 3자가 읽어도 개념적 구조를 무리 없이 이해할 수 있게 “무엇을 넣고, 어떤 것이 기대하는지” 신경을 쓰며 코드를 작성한다. 그러나 백준 온라인 저지의 문제를 매일 최소 한문제씩 풀고, 23시에 회고를 하는 “데일리 백준” 모임에 참여하게 되면서 이런 취향에서 어느 정도까지 타협을 해야 될지 고민하고 있다. 제 3자가 무리 없이 개념적 구조를 이해할 수 있는가? ‘무리 없이’라는 것은 코드 자체가 컴퓨터에서 느릴 수 있지만, 사람에게 ‘구문’으로서 쉽게 이해할 수 있다는 나의 주관적인 가치이다. 그렇지만 무리가 좀 있어도 구현체가 충분히 빠르고, 테스트 또는 문서의 도움으로 개념적 구조를 이해할 수 있으면 클린 코드라 부를 자격이 있어 보인다고 최근의 경험을 통해 생각이 바뀌였다. ...
문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. ...
위 글은 2020년 03월 20일에 발행되었습니다. 비슷한 주제의 포스팅을 연속적으로 나열하고자 위해 1년 앞당긴 점 양해 부탁드립니다. 🙇 문제 <그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. ...
참고한 문서 Iterative Preorder Traversal - GeeksforGeeks Inorder Tree Traversal without Recursion - GeeksforGeeks Inorder Tree Traversal without recursion and without stack! - GeeksforGeeks Iterative Postorder Traversal | Set 2 (Using One Stack) - GeeksforGeeks 전위탐색 루트를 방문한다. 왼쪽 서브트리를 방문한다. 오른쪽 서브트리를 방문한다. 재귀적인 함수 호출을 막을려면 효율적인 순회 처리가 필요하다. 순회되는 객체를 즉시 사용하는 방법으로 스택을 사용했습니다. def preorder(self): stack = [self.root] # 1 while len(stack) > 0: # 2 item = stack.pop() # 2-1 print(item.value, end=' ') if item.right: # 2-2 stack.append(item.right) if item.left: # 2-2 stack.append(item.left) 루트 객체를 스택에 할당한다. 스택 요소가 존재하는 동안 아래 절차를 반복한다. 스택의 한 요소를 빼내고 출력한다. 빼낸 요소가 가리키는 오른쪽 노드를 스택에 집어넣는다. 빼낸 요소가 가리키는 왼쪽 노드를 스택에 집어넣는다. 재귀 구현체와 달리1 우선적으로 넣는 노드의 left, right 순서가 반대인데, 마지막으로 넣은 요소가 먼저 출력되는 스택의 특성 때문이다. ...
오른쪽으로 배열 회전하기 배열 arr[]에서 위치 s, t 사이로 1만큼 오른쪽으로 회전시켜보자. 단, arr[t]의 경우, arr[s]로 복사하면 된다. 풀이 순서 i = t : 뒤부터 탐색을 시작하자. arr[i] = arr[i - 1] : 1 만큼 왼쪽으로 이동. arr[s] 에 이르선 arr[s - 1] 이 더 이상 없는 문제가 있음. 사전에 arr[t] 를 last 에 저장하여 arr[s] 에 대입한다. 코드 풀이 void right_rotate(int arr[], int s, int t) { int i, last; last = arr[t]; for (i = t; i > s; i--) arr[i] = arr[i - 1]; arr[s] = last; } N 만큼 이동하기 1만큼 이동하는 함수를 k 번 반복하면 되지만 이 방법은 O(n^k), (n은 s , t 사이의 거리)로 느린 문제가 있다. ...
위 예시 문제와 비슷한 유형은 시간복잡도(Big-O)와 기백을 잘 응용해보면 쉽게 풀어볼 수 있습니다. 하지만 기백을 잘 못해서(..) 승산이 있을지 걱정이 되었습니다. 그래도 경험 상 시험을 치르는게 좋을 것 같아 가기로 했었고, 오전 9:30분까지 고사장 입실을 해야 되서 전날 아침에 미리 서울로 올라갔습니다. 남은 시간동안 카페에서 녹차를 마시면서 예시 문제와 비슷한 알고리즘을 풀었습니다. 잠을 푹 잘려고 했지만 제가 카페인에 약한 체질이라 잠을 충분히 자질 못했습니다. 7시쯤에 일어나 8시 쯤에 지하철을 꾸벅 꾸벅 졸면서 타다가 동대 입구역에 내렸는데 시험을 보러온 학생들의 인파가 정말 많았었습니다. ...