IT recording...

풀이 문제를 보자마자 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방식으로..

1806번: 부분합 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 처음에는 0항부터 현재 항까지의 부분합을 구해놓은 후 이 차이를 이용하여 시간초과를 해결하려 하였다. 근데 그렇게 해도 될 것 같긴한데 어쨌든간에 최악의 경우 O(N*N) 시간이 걸린다는 점을 간과했다. 투포인터를 사용하여, start를 증가시키면서 한 번이라도 end가 N-1까지 간다면 S를 만들 수 없다는 점을 이용하자 start와 end를 증가시키며 진행하고, '연속된 수들의 합' 을 이용하는 것이므로 양 끝 값을 더..

2470번: 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 모든 조합의 수를 구한다는건 말도 안됨, 근데 모든 경우의 수를 다 하는 것 밖에 없는데 그렇다면 투 포인터 이용! 하나씩 포인터를 이동해가며 절댓값이 최소가되도록 하는 (양,음을 이용해서 판별) 포인터를 이동시키고, 그 들 중 최솟값을 저장하여 출력한다. 포인터를 이용할 것 이므로 리스트를 소팅한다. 여기서 투 포인터는 양쪽 liquid 인덱스이고, 판단 기준은 '절댓값이 최소가 된다' → '음,양 ..