분류 전체보기
[백준/BOJ]#9935:문자열 폭발[문자열/스택/파이썬/python]
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 처음에 보고 단순히 문자열 sequential search로 풀으니 시간초과가 났다! 역시 골드문제는 한큐에 풀리지 않지 분류를 보니 스택인 걸 보고 스택으로 바꾸었는데 또 시간초과! 반복문을 하나 줄이려면 뒤에서부터 탐색하면 된다는 걸 깨달았다. 그리고 마지막 res join문을 반복문안에서 하고 앉아있었다는 걸 깨닫구 코드를 수정하니 맞았다. 시간초과 코드(단순 순차탐색) #99..
[백준/BOJ]#2263:트리의 순회 [트리/분할정복/파이썬/python]
https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 인오더와 포스트오더 (inorder, postorder)를 입력으로 받으면 preorder(프리오더)를 출력해주는 문제다. 트리의 순회방법_ 전위, 중위, 후위 순회 방식이다. 위의 트리 예시들을 읽어보면 대략적으로 그림이 그려진다. Preorder는 맨처음에 루트(부모)가 들어오고, postorder는 맨마지막에 들어온다. 이를 이용하여 처음에 루트를 구한다. Inorder는 왼쪽부터 쭉 순서대로 순회한다는 것을 알 수 ..
07 분할정복
시간복잡도:fastsum()과 recursivesum()이 종료하는 데 걸리는 시간은 함수 호출 횟수에 비례. 즉, recursivesum()은 n번의 함수호출fastsum()은 호출될때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어든다.따라서 두 값의 상한은 모두 logn이므로 O(logn)! 부적절한 경우) 절반으로 나누는 알고리즘이 큰 효율 저하 불러오는 이유:여러 번 중복되어 계산되면서 시간 소모 (=overlapping subproblems)(→ 이런 경우는 8장 동적계획법으로 해결) 대표적 예제) 병합 정렬 Merge SortMerge Sort (평균/최악:O(nlogn) 7.2 문제: 쿼드 트리 뒤집기(QUADTREE, 하)algospot.com :: QUADTREE쿼드 트리 뒤집기 문..
[백준/BOJ/종만북/알고스팟]#1922:쿼드트리/QUADTREE [분할정복/파이썬/python]
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 재귀와 분할정복(divide and conquer)을 이용하여 푼다. #1992_쿼드트리 n=int(input()) graph=[list(map(int,input())) for i in range(n)] res="" def quad(y,x,n): global res arr=graph[y][x] notsame=False for i in range(y,y+n): brk=False for ..
[백준/BOJ/종만북/알고스팟]#1922:쿼드트리/QUADTREE [분할정복/파이썬/python/C++]
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 재귀와 분할정복(divide and conquer)을 이용하여 푼다. #1992_쿼드트리 n=int(input()) graph=[list(map(int,input())) for i in range(n)] res="" def quad(y,x,n): global res arr=graph[y][x] notsame=False for i in range(y,y+n): brk=False for ..
[백준/BOJ]#1629:곱셈 [분할정복/수학/파이썬/python]
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할정복 divide n conquer 과 수학 문제다. 수학의 분배법칙을 분할정복에 적용하여 재귀로 풀어나가면 된다. 호기심에 재귀 호출 순서가 궁금해서 프린트문을 여러번 찍어보았는데 마지막 홀수인 경우, ..(10^1)%12 x 10) %12 x 10이 마지막으로 호출된다. 그러므로 12로 다 나누면 남는 건 10 * 10 숫자만 남아서 결론적으론 답이 4가 나온다. #1629_곱셈 a,b,c=map(int,input().split()) ''' 수학의 분배법..
[백준/BOJ]#1780: 종이의 개수 [분할정복/재귀/파이썬/python]
https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 분할정복과 재귀를 이용하여 푸는 문제다. dfs bfs가 생각났는데 분류가 분할정복으로 되어있고 9개로 종이개수가 정해져있으므로 for문으로 돌리고 재귀를 해서 체크하면 된다. #1780_종이의개수_dividenconquer n=int(input()) paper = [list(map(int,input().split())) for _ in range(n)] res1=0 res0=0 res..
[백준/BOJ]#17413: 단어 뒤집기 2 [문자열/파이썬/python]
https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 쉬운 문제라고 생각하고 후딱 풀려고 했는데.. 스톤헤드..!!! 은근히 오래 걸렸다.... delimiter(bracket) 기준으로 처음에 인덱스를 기준으로 뽑아내다가 리스트와 char 데이터타입의 충돌로 또 애먹다가.. 뒤엎고 다시 짜고.. 하다가 완성했다 결국. bracket안에서만 문자열이 뒤집히지 않으므로 신경써주고 나머지는 플래그를 두어서 그외의 경우에 ..
[LeetCode] #106. Construct Binary Tree from Inorder and Postorder Traversal [트리/해쉬/분할정복/파이썬/python]
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ Construct Binary Tree from Inorder and Postorder Traversal - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 전위순회(inorder traversal)와 후위순회(postorder traversal)에 대한 개념을 아는지, 그것을 활용하여 재귀를 통해 bin..
[통계학]Confidence Interval(신뢰구간)/t-value/p-value
(가설검정) 전체 표본집단에서, random samples를 사용하여 test한다. ex) 대표적 예시는 소금물의 온도다. > -가설(Hypothesis): 소금물의 어는점은 0이 아니다. > -표본집단(Whole Population): 어는 소금물 > -Random samples: 어는 소금물의 실험 Hypothesis Test Null Hypothesis: H0: 어는점=0, 소금물의 어는 점은 0이다.(Null distribution: Null hypothesis가 참이면 해당 표본집단) Alternative Hypothesis: HA: 어는점≠0, 소금물의 어는점은 0이 아니다. null hypothesis에 따라서 reject or not-reject 한다. Significance Level: ..
[LeetCode/리트코드]#441: Arranging Coins[python/파이썬/이분탐색/수학]
https://leetcode.com/problems/arranging-coins/ Arranging Coins - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1+2+3...+k = k(k+1)/2 라는 공식이 있다. 이를 이용하여 이분탐색이나 수학 알고리즘으로 구현할 수 있다. 접근법 1) 이분탐색 _Binary Search 시간복잡도 O(log N) class Solution(object): def arrangeCoins(self, n): """ :typ..
[LeetCode/리트코드]#668:Kth Smallest Number in Multiplication Table[파이썬/python/이분탐색/Binary Search]
https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/ Kth Smallest Number in Multiplication Table - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 브루트포스(완전탐색)이나 힙을 이용하여 구현하면 시간초과가 뜬다. 처음에 힙을 이용하여 구현했다가 시간초과를 받았다. 각 n줄에 대하여 가장 작은 사용안한 원소를 힙에서 pop하는 알고리즘 시간초과 코드..
[LeetCode/리트코드]#368. Largest Divisible Subset[파이썬/python/수학]
https://leetcode.com/problems/largest-divisible-subset/ class Solution: def largestDivisibleSubset(self, nums: List[int]) -> List[int]: ans=[] max_ind=0 divcnt=[0 for i in range(len(nums))] prev=[-1 for i in range(len(nums))] nums.sort() idx=-1 for i in range(len(nums)): for j in range(i): if nums[i]%nums[j]==0: if divcnt[i] < divcnt[j]+1 : divcnt[i]=divcnt[j]+1 prev[i]=j if divcnt[max_ind] < di..
[LeetCode/리트코드]#1286. Iterator for Combination[파이썬/python/문자열/String]
https://leetcode.com/problems/iterator-for-combination/ class CombinationIterator(object): def __init__(self, characters, combinationLength): """ :type characters: str :type combinationLength: int """ self.len = len(characters) self.characters = characters self.pointers = [i for i in range(combinationLength)] self.pointers[-1] -= 1 self.thres = [i for i in range(self.len -len(self.pointers), sel..
[LeetCode/리트코드]#739:Daily Temperatures [파이썬/python/배열/array]
https://leetcode.com/problems/daily-temperatures/ 온도 list를 받으면 각 날에 대해 - 현재날짜보다 다음날짜가 따뜻한 날짜의 개수(number of days)를 구하는 것이다. 브루트포스 문제로 완전탐색을 하면된다. 각 온도의 날짜를 모두 돌면 O(N^2)의 시간복잡도다. 비효율적인 완전탐색보다 좀 더 빠르게 짤 수 없을까? 배열을 사용하여 구현해보자. N(온도길이)만큼 iterate하면 시간복잡도는 O(N)이다. 공간복잡도 또한 O(N)이다. class Solution(object): def dailyTemperatures(self, temperatures): """ :type temperatures: List[int] :rtype: List[int] """ ..
[LeetCode/리트코드] #203. Remove Linked List Elements [큐/queue/python/파이썬]
https://leetcode.com/problems/remove-linked-list-elements/ Remove Linked List Elements - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution..
[LeetCode/리트코드] #1413. Minimum Value to Get Positive Step by Step Sum [Prefix Sum/파이썬/python]
https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/ Minimum Value to Get Positive Step by Step Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com class Solution: def minStartValue(self, nums: List[int]) -> int: start=1 while True: total = start is_valid..
[백준/BOJ] #1967: 트리의 지름 [트리/BFS/python/파이썬]
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #1967_트리의 지름 from collections import deque n = int(input()) tree = [[] for _ in range(n+1)] for _ in range(1,n): parent, child, weight = map(int, input().split()) tree[parent].append([weight, child]) tree[child]...
[자료구조] 비트마스크(BitMask) 알고리즘
비트마스크는 정수의 이진수 표현을 자료구조로 쓰는 기법이다. 이진수 즉, 0과 1만을 이용하므로 하나의 비트는 참/거짓을 의미한다. 시간 복잡도(수행시간)가 O(1)이라는 엄청난 장점이 있다. 공간 복잡도(메모리 사용량) 또한 적다. bit가 10개라면 2^10까지의 표현이 가능한 것이다. 그래서 DP같은 다이나믹 프로그래밍에 매우 적절하다. 논리회로 등을 공부해보신 분이라면 논리연산자들에 익숙할 것인데 비트마스크에서도 이러한 논리연산자들을 사용한다. 1. AND 연산 : & A와 B 둘다 참 ex) 1 & 1 => 1 2. OR 연산 : | A나 B 하나라도 참 ex) 0 & 1 =>1 3. XOR 연산 : ^ 둘 중 하나만 참 ex) 1 & 1 => 0 4. NOT 연산: ~ 참이면 거짓으로, 거짓이..