Study

2023년 8월 3일 알고리즘 문제풀이 백준 1991 문제 링크 1차 시도 나의 생각 왼쪽 자식이 존재하면 재귀를 통해 들어가고, 없을 때 오른쪽 자식도 확인하는 과정을 거쳤다. 정답을 위한 배열에 왼쪽 자식과 부모, 오른쪽 자식을 어느 타이밍에 추가해야할 지 헷갈렸고 이로 인해 코드를 완성하지 못했다. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import sys arr = [] n = int(sys.stdin.readline()) for _ in range(n): p, l, r = sys.stdin.readline().rstrip().split() arr.append([p, l, r]) front = ['A'] mid = [] back = [] def search_front(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': ans.append(x[1]) search_front(x, arr, ans) if x[2] != '.': ans.append(x[2]) search_front(x, arr, ans) def search_mid(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': search_mid(x, arr, ans) else: ans.append(x[0]) if x[2] != '.': search_mid(x, arr, ans) break def search_back(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': search_back(x, arr, ans) else: ans.append(node) if x[2] != '.': search_back(x, arr, ans) ans.append(x) ans.append(node[0]) search_front(arr[0], arr, front) search_mid(arr[0], arr, mid) search_back(arr[0], arr, back) print(front) print(mid) print(back) 2차 시도 나의 생각 정답을 위한 배열에는 항상 부모만 넣는다는 기준을 세웠다. 또 왼쪽자식과 오른쪽 자식의 탐색을 if-else 조건문을 사용하였는데 별개로 하였다. 즉 왼쪽 자식을 먼저 탐색해 존재하면 재귀를 통해 최대한 깊숙히 들어간 후 더이상 왼쪽자식이 존재하지 않을 때 그 때의 부모노드를 배열에 추가하면 전체 트리에서 가장 왼쪽에 있는 노드를 배열에 추가한 것으로 구현된다는 것을 깨달았다. 순회의 방식에 따라 왼쪽 자식 탐색, 부모노드 삽입, 오른쪽 자식 탐색의 순서만 변경해주었다. ...

1. 컴퓨터 네트워크와 인터넷 1.1 인터넷이란 무엇인가? 구성요소를 기술하거나 분산 애플레키에션에 서비스를 제공하는 networking infrastructure 관점으로 기술할 수 있다. 공부를 시작하기 전의 나라면 수 많은 사람들의 컴퓨터가 연결되어 있는 연결망 이라고 대답할 것 같다. 1.1.1 구성요소로 본 인터넷 인터넷은 수 많은 컴퓨팅 장치를 연결하는 컴퓨터 네트워크이다. 이전에는 데스크톱 PC, 서버뿐이었지만 스마트폰과 태블릿을 넘어 가전제품, 자동차 등 다양하게 연결되는 중! 인터넷에 연결된 모든 장치를 호스트(host) 혹은 **종단 시스템(end system)**이라고 부른다. end system : **통신 링크(communication link)**와 **패킷 스위치(packet switch)**의 네트워크로 연결된다. ...

책너두 5기 3일차 로버트 C.마틴의 클린코드 p.13 ~ p.23 내용 정리 론 제프리스 모든 테스트를 통과한다. 중복이 없다. 시스템 내 모든 설계 아이디어를 표현한다. 클래스, 메서드, 함수 등을 최대한 줄인다. 중복을 줄이고 한 기능만 수행하며 표현력을 높여라. 작게 추상화하라. 워드 커닝햄 코드를 읽으면서 짐작했던 기능을 각 루틴이 그대로 수행한다면 깨끗한 코드다. 코드가 그 문제를 풀기 위한 언어처럼 보인다면 아름다운 코드다. 코드를 독해하느라 고민해야할 필요가 없어야 한다. 언어를 단순하게 보이도록 만드는 책임은 우리에게 있다. 저자의 생각 이 책은 저자와 동료들이 옳다고 믿고 있는 깨끗한 코드에 대해 설명한다. 무조건 진리이니 받아들인다는 자세는 곤란하지만 고민하고 생각하고 공부하면 좋은 결과를 낼 수 있을 것이다. 또한 이 책과 다른 의견도 마땅히 수용해야 한다. ...

2023년 8월 2일 알고리즘 문제풀이 백준 11000 문제 링크 1차 시도 나의 생각 각 수업을 시작하는 시간을 기준으로 정렬하되, 끝나는 시간을 heap에 넣는다. 반복문으로 순회하며 지금 시작할 수업의 시간이 배열에 들어있는 수업 중 끝나는 시간이 가장 빠른 수업의 종료 시간과 비교하였다. 종료 한 후 시작되면 추가적인 강의실이 필요 없다. 하지만 수업이 끝나지 않은 채 다음 수업이 시작된다면 새로운 강의실이 필요하다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import sys from heapq import heappush, heappop, heappushpop n = int(sys.stdin.readline()) classes = [] for _ in range(n): s,t = map(int,sys.stdin.readline().split()) classes.append([s,t]) classes.sort() heap = [] cnt = 1 for i in range(n): now_class = classes[i] if not heap: heappush(heap,now_class[1]) else: while heap: end_time = heap[0] if now_class[0] >= end_time: heappop(heap) else: break heappush(heap,now_class[1]) cnt = max(cnt,len(heap)) print(cnt)

4. 분할정복 Divide : 문제를 같지만 더 작은 단위로 나눈다. Conquer : 분할된 작은 문제들을 해결한다. Combine : 작은 문제에 대한 해결책을 본래의 문제로 조합하여 대입한다. Recursive case : 분할된 소문제들이 재귀적으로 풀 만큼 충분히 크면 Recursive case라고 부른다. 소문제들을 풀다보면 원래 문제와 동일하지 않을 때도 있는데, 이 떄는 Combine 단계의 일부이다. Recurrences 재귀식을 푸는 세 가지 방법 : 점근적인 Θ 또는 O 상한을 얻는 방법 Substitution method : 수학적 귀납법을 통해 추측을 증명 ...

책너두 5기 2일차 로버트 C.마틴의 클린코드 내용 정리 추천사 (James O. Coplien) 덴마크의 속담에는 ‘사소한 곳에서 발휘하는 정직은 사소하지않다.’ 라는 말이 있다. 이 책을 읽을 때 가져야 하는 자세를 말해준다. 소프트웨어 개발에서 아키텍쳐가 중요하다는 것은 누구나 동의한다. 책임 있는 전문가라면 프로젝트를 시작할 때 생각하고 계획할 시간을 확보해야 한다. 세세함의 주의를 기울이는 태도는 당연하지만 두 가지 이유로 중요하다. 큰 실무에서 실력을 쌓고 신뢰를 얻으려는 전문가는 먼저 작은 실무부터 실력을 쌓고 신뢰를 얻어야 하기 때문 꼭 맞게 닫히지 않는 문이나 비뚤어진 바닥 타일이나 지저분한 책상 등 아주 사소한 것들이 전체의 매력을 깎아먹기 때문 대다수의 활동은 제조가 아닌 유지보수와 관련되어 있다. 과거 일본에서 나타난 TPM(Total Productive Management)이라는 품질관리론이 있다. 여기의 5S 원칙이 Lean의 토대가 되었다. ...

책너두 5기 1일차 책 : 로버트 C.마틴의 클린코드 주제 로버트 C. 마틴이 쓴 클린 코드는 제목 그대로 ‘깨끗한 코드’를 지향한다. 함수를 생성하는 것, 주석을 작성하는 것, 전체적인 구조 등 코드를 작성할 때 필요한 가이드이다. 가독성에서, 지속적인 유지 및 보수와 확장에서, 팀의 협업에서 필요한 덕목이다. 중반부에선 현존하는 코드를 어떻게 바꿀것인가를 다양한 사례를 통해 보여준다. 종반부에선 위와 같은 노력끝에 나타나는 결과들을 보여준다. 이 책 은 끊임없이 왜 코드를 깔끔하게 작성해야 하는가를 설득하고 그 방법을 말해준다. ...

2023년 7월 30일 알고리즘 문제풀이 백준 5904번 문제 링크 1차 시도 나의 생각 재귀 함수를 통해 각 문자열을 구할 수 있었다. 또한 그 문자열의 길이도 규칙적이므로 몇번째 재귀에서 n번째 문자열이 등장하는지를 알아내어 그 문자열의 index를 통해 구하였다. 하지만 메모리 초과와 시간 초과로 인하여 오답처리 되었다. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys sys.setrecursionlimit(10**6) n = int(sys.stdin.readline()) def moo(k): if k == 0: return 'moo' return moo(k-1)+'m'+'o'*(k+2)+moo(k-1) i = -1 while True: i += 1 tmp = moo(i) if len(tmp) >= n: print(tmp[n-1]) break 2차 시도 나의 생각 문자열을 구하면 안된다고 생각하였다. 다음 문자열이 이전 차례의 문자열 두개에 하나의 규칙적인 문자가 껴있는 형태라는 사실에 집중하였다. 예를 들어 S(10)의 몇번째 문자열인지는 S(9)의 문자열을 통해 알 수 있다. 원리는 다음과 같다. ...

2023년 7월 29일 알고리즘 문제풀이 백준 13334번 문제 링크 1차 시도 나의 생각 사람들의 사무실 과 집 둘 중 좌표가 작은 것을 먼저 오게 한 후, 그것을 오름차순으로 배열에 정리하였다. 각 지점을 철로의 시작점으로 삼아 모든 case를 검사하며 최댓값을 업데이트했다. 다 검사해버리니 당연히 시간초과… 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys from heapq import heappop, heappush n = int(sys.stdin.readline()) people = [] for _ in range(n): h,o = map(int,sys.stdin.readline().split()) if h <= o: heappush(people,[h,o]) else: heappush(people,[o,h]) d = int(sys.stdin.readline()) ans = 0 while people: cnt = 0 x = people[0][0] for person in people: if person[0] >= x and person[1] <= x+d: cnt += 1 ans = max(ans,cnt) heappop(people) print(ans) 2차 시도 나의 생각 어떤 사람의 집과 사무실의 거리는 철로의 길이인 d보다 멀 수도있다. 이 사람은 철로를 어디에 설정하든 이용할 수 없다. 따라서 입력을 받을 때 이런 케이스를 지우려고 했다. 또한 정렬을 해버린 만큼 굳이 필요하지 않은 조건들도 제거하였다. 하지만 예외케이스가 있는지 오답처리되었다. ...

2023년 7월 28일 알고리즘 문제풀이 백준 1655번 문제 링크 1차 시도 나의 생각 양 끝과 중간이라는 생각에 deque을 사용하면 어떨까 생각하고 코드를 작성했다. 생각해보니 중간과 끝 사이에 새로운 숫자를 집어넣어야 하는데… 다행히 우선순위 큐, 최소 heap이 생각났지만 너무 늦게 생각나서 코드 작성을 못했다. 다음 시도에선 해봐야지. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys from heapq import heappop, heappush, heappushpop n = int(sys.stdin.readline()) big = [] mid = [] small = [] for _ in range(n): num = int(sys.stdin.readline()) if not mid: mid.append(num) print(num) continue if num >= mid: tmp = heappushpop(big,num) mid.append(tmp) print(mid[0]) else: tmp = heappushpop(small,-num) mid.append(-tmp) mid.sort() print(mid[0]) 2차 시도 나의 생각 heap을 사용하였다. 가운데 값을 기준으로 크냐 작냐에 따라 경우가 나눠질거라고 생각해서 가운뎃값보다 작은 heap, 가운뎃값을 담은 heap, 더 큰 heap 세개로 나누어서 생각했다. 하지만 문제에서 나왔듯 가운데 값이 전체 숫자의 갯수에 따라 2개일 수도 한 개 일수도 있어서 가운데를 담는 배열을 1로 유지해야할지, 혹은 큰 배열과 작은 배열의 수를 갖게 유지해야할 지 여러모로 헷갈렸다. 차라리 하나를 우직하게 했으면 정답은 나왔으려나.. 여러 생각에 헤메다가 시간만 허비하고 코드를 완성하지 못했다. ...