IT recording...

Segment Tree(세그먼트 트리) 부분합을 선형 계산을 통해 구하려면 O(N)의 시간이 걸린다. 그 후 특정 부분합을 구하려면 O(1) But, 노드의 값이 빈번히 update된다면 어떨까? → 원소의 개수가 N개인 배열이 있을 때 첫번째 값이 M번 변경된다면 O(MN) 번의 시간복잡도가 필요하다. ⇒ Segment Tree를 이용하면 O(logN)의 시간 복잡도 내에 부분합을 구할 수 있다. : 이진 트리를 바탕으로 트리를 구성하며, update를 해야 할 부분만 업데이트 할 수 있다. leaf 노드는 배열이 가지는 값을 가지게 된다. 이외의 노드들은 부분합 등 특정 조건을 만족하는 조건으로 이루어진다. 트리의 최대 노드 개수 def segmentation_size(node): height = i..

Spring을 사용한 프로젝트를 할 때 API를 하나하나 적는 것은 많은 시간과 노력을 요구한다. 이에 자동화 된 API 툴을 제공하는데 그 중 Swagger를 연결하는 방법을 알아보겠다. (+마주했던 오류와 함께) gradle 설정 // implementation group: 'io.springfox', name: 'springfox-swagger-ui', version: '2.9.2' // implementation group: 'io.springfox', name: 'springfox-swagger2', version: '2.9.2' gradle 설정을 먼저 진행한다. https://mvnrepository.com/artifact/io.springfox/springfox-swagger-ui 에서 맞..

풀이 문제를 보자마자 stack을 사용해서 append시키고 pop시키고 해서 풀어야 할 것을 직감했다. 근데 계산된 결과를 어찌할 지 감을 못잡고 있다가 풀이를 보고 stck에 함께 넣어 관리하기로 하였다. 올바른 괄호가 아닌 경우를 먼제 제외하고 시작한다. (] 의 경우, [)의 경우, 그리고 ()끼리,[]끼리 개수가 같지 않을 경우가 있다.(쌍을 이루지 않는 경우) 들어온 것이 여는 괄호면 ( [ → stck에 그대로 append한다. ⇒ 여는 괄호는 스택에 넣어두고, 닫는 괄호가 나왔을 때 바로 앞에 있는 것과 짝이 맞을 때 진행한다. ⇒ 스택에 숫자를 함께 넣으므로 바로 앞에 있는 것이 숫자인 경우(그 앞의 부호를 다시 확인하여야 한다.), 여는 괄호인 경우를 나누어 진행한다. ⇒ 바로 앞이 숫..

풀이 - 들어오는 간선이 하나도 없는 root 노드가 '단 한 개 ' 존재해야 한다. - 루트를 제외한 모든 노드는 반드시 '단 하나의' 들어오는 간선이 존재한다. - 노드가 존재하지 않는 것도 트리이다. - Node = Edge + 1 입력을 받아 각 테스트 케이스들을 treeList에 저장해 놓는다. 각 tree는 u가 key로, v가 value 리스트형으로 구성되어 있다. ex) { 1:[3], 4:[2,5] } 나가는 엣지 노드들 U → keys() , 들어오는 엣지 노드들 V → values()로 리스트화 해둔다. keyList = list(aTree.keys()) #나가는 엣지 노드들 (u) valueList = list(aTree.values()) #들어오는 엣지 노드들 (v) #들어오는 엣..

최종 코드 import sys def input(): return sys.stdin.readline().rstrip() N = int(input()) #트리구성 -> key : root, value : [left,right] tree = {} for _ in range(N): root,left,right = input().split(" ") tree[root] = [left,right] def preorder(root): if root != '.': print(root, end='') #root preorder(tree[root][0]) #left preorder(tree[root][1]) #right def inorder(root): if root != '.': inorder(tree[root][0])..

더보기 최종 코드 import sys def input(): return sys.stdin.readline().rstrip() N = int(input()) stck = [] for _ in range(N): line = input().split(" ") if line[0] == "push": #stack에 하나씩 넣기 stck.append(line[1]) elif line[0] == "pop": #stack가장 위에 있는 정수 빼고 출력(Last In First Out) if len(stck) 0: print(0) else: print(1) elif line[0] == "top": #stack가장 위에 있는 정수 출력 = 가장 마지막에 넣은 정수 출력 if len(stck)

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 list를 이용하면 시간 초과가 난다. 왜 그런지는 모르겠음... if문 검사하는 것도 시간이 많이 걸리나..? 몇번째 애를 가지고 했는지는 중요하지 않고, 그냥 걔가 몇 번 쓰였는지만 중요한 문제라면 dictionary를 사용하자. O(n^4)의 시간복잡도로는 딱 봐도 풀 수 없는 문제이므로 AB,CD를 나누어 생각한다. AB를 더해서 dict에 넣어 놓는다. 이 때 값이..

2143번: 두 배열의 합 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 부동소수점 문제 때문에 int(Y/X100)으로 풀면 안되고, int((Y100)/X) 로 풀어야 한다. /는 소수점까지, //는 몫, %는 나머지! while문 다 돌리면서로 해봤지만 X무시무시하게 크기 때문에, 추가로 이긴 횟수를 변수로 이진탐색을 한다. start,end = 0,1000000000로 설정한다. start≤end 일 때까지 수행하며..

2143번: 두 배열의 합 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 처음에는 아무것도 없으면 0 출력 하라는 말에 다 해보는 문제인줄 알았다. A,B가 1000개밖에 없어서 다 해도 될 줄.. 근데 아니나다를까 시간초과 → 부분합 사용했는데도 왜 시간초과지,,하고 측정했는데 세상에 7초 떴당 부분합이 어디서부터 어디까지인지를 기억할 필요는 없다 → dictionary사용 list합은 sum으로 사용 가능 aList의 ..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 처음에는 모든 루트를 다 도는 dfs로 생각했다. 모든 경우를 다 거쳐야 최소,최대 값을 얻을 수 있다고 생각했기 때문 또, dp 테이블을 이용해야겠다고 생각했을 때 dp테이블을 (맵의 크기)인 (3*N) 크기로 만들어서 진행했었는데, 옳지 않은 생각이었다. (물론 메모리부족이 뜨기도 했겠지만 N이 100,000 이기 때문에) → 각 맵의 줄에서 아래로 내려오면서 최소,최대를 만드는 문제인데 dfs방식으로..