알고리즘
[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..
[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 연산: ~ 참이면 거짓으로, 거짓이..
[백준/알고리즘] #5554:심부름 가는 길[파이썬(python)/수학]
https://www.acmicpc.net/problem/5554 5554번: 심부름 가는 길 승균이는 매일 학교, PC방, 학원에 다닌다. 반복되는 일상에 익숙해진 승균이는 이동시간을 단축해서 PC방에 더 오래 머물고 싶었다. 그래서 스톱워치를 들고 이동할 때마다 기록을 잰 후 집 www.acmicpc.net #5554_심부름가는길 total=0 for _ in range(1,5): total+=int(input()) x=total//60 y=total%60 print(x) print(y)
[LeetCode/리트코드] #1178. Number of Valid Words for Each Puzzle[파이썬(python)/Bitmask/비트마스크]
https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/ Number of Valid Words for Each Puzzle - 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 findNumOfValidWords(self, words: List[str], ..
[LeetCode/리트코드] #96. Unique Binary Search Trees[파이썬(python)/C++/BST]
https://leetcode.com/problems/unique-binary-search-trees/ Unique Binary Search Trees - 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 BST(Binary Search Tree)는 root노드의 왼쪽으로는 더 작은 값, 오른쪽으로는 더 큰 값을 가지는 트리다. 그래서 탐색 순회하기 효율적인 자료구조를 가진다. 노드의 개수를 입력으로 받았을 때 만들 수 있는 BST의 개수를 출력으로 하면 된다. 점..
[백준/알고리즘] #9663:N-Queen[파이썬(python)/백트래킹]
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에 문제 힌트에 퀸 노래 있는 거보고 무슨 문제지 대체..? 싶었다 체스의 퀸을 뜻하는 것이었다. N-Queen 이 문제는 백트래킹에서 대표적인 문제라고 한다. 체스판에서 퀸은 중요한 아이로! 가로 세로 대각선 거리제한 없이 쭉 쭉 뻗어 이동할 수 있는 아이입니다. 퀸 N개가 서로 공격할 수 없는 경우라 하면 가로 세로 대각선에 퀸이 겹치지 않게 하는 경우겠지요 그걸 백트래킹으로 구현해봅니다. 백트래킹은 조건..
[백준/알고리즘] #16212:정열적인 정렬 [파이썬(python)/정렬]
https://www.acmicpc.net/problem/16212 16212번: 정열적인 정렬 형준이는 수열을 하나 가지고 있다. 형준이는 수열을 정열적으로 정렬해보려 한다. 과연, 정렬할 수 있을까? www.acmicpc.net 25점을 받은 코드.. 100점 받은 코드는 어떻게 짜야하는지... #16212_정열적인 정렬 N = input() a = list(map(int, input().split())) a.sort() for i in a: print(i,end=' ')
[백준/알고리즘] #10709: 기상캐스터 [파이썬(python)/구현]
https://www.acmicpc.net/problem/10709 10709번: 기상캐스터 출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시 www.acmicpc.net 이런 구현문제는 계속 그려보거나 시뮬레이션하면서 풀면 된다. #10709_기상캐스터 H, W = map(int, input().split()) Wstring = [] for _ in range(H): Wstring.append(list(input())) sky=[[-1]*W for _ in range(1,H+1)] cnt=W for k in range(0,W+1)..
[백준/알고리즘] #1330: 두 수 비교하기[파이썬(python)/수학]
https://www.acmicpc.net/problem/1330 A,B = map(int,input().split()) print('>') if A > B else print('
[백준/알고리즘] #16953: A → B [파이썬(python)/그래프/DFS]
https://www.acmicpc.net/problem/16953 #16953_A->B from collections import deque A, B= map(int, input().split()) def dfs(x,y): q=deque([(x,y)]) while q: num, cnt = q.popleft() if num == B: return cnt if num * 2
[백준/알고리즘] #1316: 그룹단어체커 [파이썬(python)/문자열]
https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net #1316_그룹단어체커 N = int(input()) word=[] cnt=N for _ in range(N): word=input() for i in range(0, len(word)-1): if word[i] in word[i+1:]: if word[i]!=word[i+1]: cnt-=1 continue print(cnt) 처음엔 플래그를 두어 참거짓으로 두려고..
[백준/알고리즘] #17609: 회문 [파이썬(python)/문자열]
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net #17609_회문 import sys T=int(input()) def similar(word, start, end): while start < end: if word[start]==word[end]: start+=1 end-=1 else: return 2 return 1 def palindrome(word,start,end): while start