기록장

API 문서를 작성해보자. 나는 HTTP 프로토콜을 사용하는 REST API를 사용할 것이기 때문에 먼저 HTTP 프로토콜의 주요 개념과 REST API가 어떻게 동작하는지 먼저 간단히 정리하고 Swagger 설치하는 법을 알아보도록 하겠다. REST APIREST API 설계 원칙REST는 HTTP 기반으로 클라이언트가 서버의 리소스에 접근하는 방식을 규정한 아키텍처이다. REST한 방식으로 API를 설계하려면 원칙이 있다. 자원(URI), 행위(HTTP request method), 표현(payload)를 사용하기URI는 리소스를 표현리소스에 대한 행위는 HTTP request method로 표현. URI로 표헌하지 않기이런 이론적인 얘기를 먼저 하면 당연히 안 와닿을테니 예시를 보자. 회원 관리 시..

문제https://www.acmicpc.net/problem/5639이진 검색 트리를 전위 순회한 결과를 보고 후위 순회한 결과를 구하는 문제이다.풀이파이썬 EOF 입력 처리?eof (end of file) : 파일 입출력 시 끝날 때까지 읽어들이는 readline()과 같은 내장 함수를 쓸 때 사용되는 개념sys.stdin.readline()함수는 eof를 만났을 때 except가 아니라 빈 문자열("")을 반환함파이썬 내장 함수 input()은 eof를 만났을 때 except를 반환함입력값에 입력 종결 규칙이 없을 때, 아무 것도 입력하지 않은 경우 빠져나와야 하므로 readline()은 빈 문자열이 들어올 때, input()은 except가 발생했을 때 break 처리를 해주면 됨while True..

문제https://www.acmicpc.net/problem/1197풀이크루스칼 알고리즘을 사용해 최소 스패닝 트리를 만들었다. 시간 초과 원인?가중치가 가장 큰 간선에서 비로소 스패닝 트리가 만들어질 수도 있으므로, 어차피 최악의 경우에는 모든 간선을 확인해야 함시간 초과의 근본적인 원인은 union-find에 어떤 최적화도 적용되어 있지 않아 높이가 아주 높은 트리가 만들어질 수 있기 때문 해결 방법union 함수에서 parent 합치기# 시간 초과def union(a, b): a_ = find(a) b_ = find(b) if a_>b_: p[a_]=b_ else: p[b_]=a_rank = [1] * (v+1) # 트리의 랭크(높이) 저장def un..

전위, 중위, 후위 순회를 재귀로 푸는 문제이다.처음에 left, right 노드 저장 방식을 잘못 받아서 구현하는 데 애를 먹다가 옆자리 동료분한테 물어봤는데 정석 풀이가 있었다.root 노드를 아스키 코드로 변경한 숫자를 인덱스로 하는 곳에 left, right 노드를 저장하는 방법이다.해당 노드의 왼쪽 자식을 저장하는 l, 오른쪽 자식을 저장하는 r 리스트를 사용하면 재귀로 쉽게 풀 수 있다.import sysn = int(sys.stdin.readline())l = [None]*26r = [None]*26for _ in range(n): node, left, right = map(str, sys.stdin.readline().split()) if left != '.': l[ord(nod..

최소 스패닝 트리신장 트리 (Spanning Tree)그래프에서 일부 간선을 선택해 만든 트리최소 연결로 이루어짐 즉, 모든 노드가 가장 적은 간선 수로 이어져있는 경우에 해당정점이 n개일 때 간선이 n-1개이면 스패닝 트리BFS, DFS로 신장 트리 찾기 가능 (탐색 도중 사용한 간선을 모으면 됨)최소 비용 신장 트리 (Minimum Spanning Tree, MST)스패닝 트리 중 사용된 간선들의 가중치 합이 최소인 트리각 간선의 가중치가 동일하지 않을 경우, 단순히 적은 간선을 쓴다고 최소비용이 되는 건 아님사이클이 없어야 함구현 방법으로는 Kruskal, Prime 알고리즘이 있는데 둘 다 그리디한 방법임Kruskal Algorithm간선을 비용이 낮은 것부터 v-1개 선택하며 떨어져있던 노드를 ..

위상 정렬방향 그래프에서 간선으로 정점 간 선후관계가 주어졌을 때, 선후관계가 위배되지 않도록 나열하는 정렬하나의 그래프에 여러 개의 위상 정렬 결과가 있을 수 있음그래프 내에 사이클이 없어야 위상 정렬이 만들어질 수 있음 (사이클이 없는 방향 그래프: DAG(Directed Acyclic Graph)위상 정렬의 시간 복잡도는 O(V+E) -> 모든 정점을 큐에서 한 번씩 꺼내면서 연결된 간선을 제거함 O(V) + 각 간선을 한 번씩 탐색하면서 진입 차수를 감소시킴 O(E) -> 빠른 속도의 알고리즘구현 방법위상 정렬을 코드로 구현할 때 매번 정점과 간선을 지우면 매번 O(V^2)로 동작하게 될 것이다.대신 미리 indegree 값을 저장해뒀다가 매번 indegree값을 1씩 감소시키는 방법을 사용하면 ..

Rest API의 응답값을 넘기는 형식 중 하나데이터를 캡슐화하는 방법왜 필요한가?public class Member { private Long id; private String name; private int age;}{ "id" : 1, "username" : "홍길동", "age" : 15}Member라는 객체를 JSON형태로 표현하면 다음과 같다. [ { "id":1, "username":"홍길동", "age":15 },{ "id":2, "username":"아무개", "age":24 }, ... { "id":99, "username":"개똥이", ..

2주차 퀴즈를 치고 내 자신에 대해 실망했고 너무 속상했다.처음부터 우울한 소리를 한 것 같은데..! 지금은 괜찮다. 내 공부 방식이 잘못 된 것을 알았으니 다음 주부터 고치기로 했다. 다른 동료들의 답안과 비교해보니 내 답안이 너무 구체적이지 않았다.보면 아는 지식이었지만 백지 시험을 쳤을 때 스스로 서술형으로 적어내지 못하는 상태였다.공부한 지식들을 그냥 흘려보내지 말고 진짜 내 것으로 만드는 연습을 해야겠다. 그리고 1번 문제는 해시, 해시 충돌의 개념을 묻는 문제였는데 나는 퀴즈를 치기 전까지 백준 문제를 푸는 데 급급해서 큐, 해시, 힙의 개념을 아직 보지도 않은 상태였다. 그래서 1번을 쓰지 못했다. 현재 아는 데까지만 적어서 제출했어야 했는데 그런 노력도 하지 않았다. 왜 그랬는지 모르겠는데..

큐 관련 파이썬의 모듈PriorityQueue데이터를 추가한 순서대로 제거(FIFO, 선입 선출)되지 않음우선순위가 가장 작은 값 부터 제거됨 -> 내부적으로 데이터를 정렬된 상태로 보관한다는 의미, heap 모듈로 구현되어 있음from queue import PriorityQueueque = PriorityQueue(maxsize=8)que.put(4) # 원소 추가que.get() # 원소 삭제que.put((3, 'apple')) # (우선순위, 값)의 튜플 형태로 데이터를 넣으면 우선순위 기준으로 데이터가 정렬됨que.get()[1] # 값 반환 heapq 최소 힙(min heap) 형태가 유지되는 자료구조 -> 가장 작은 값은 언제나 인덱스 0 (이진트리의 root)에 위치함, 부모 노드는 항상..