본문 바로가기

분류 전체보기

 (43)
그래프 DFS 그래프 노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(vertex)라고도 합니다. 간선(Edge): 노드 간의 관계를 선으로 표시한 선입니다. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) DFS (Depth First Search) 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다. 실행 과정 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다. 위 과정을 반복한다. 구현 코드 graph = { 1: [2, 3, 4], 2: [5], 3: [5], 4: [], 5: [6, 7], 6: [], 7: [3], } def dfs_recursive(n..
상위 k 빈도수 - 해시 상위 k 빈도수 상위 k번 등장하는 요소를 추출하라. 입력 : nums=[1,1,1,2,2,3], k=2 출력 : [1,2] #내가 푼 풀이 from collections import Counter import heapq def Solution(num,k): answer=[] freqs=Counter(num) freqs_heap=[] for i in freqs: heapq.heappush(freqs_heap,(-freqs[i],i)) for i in range(k): answer.append(heapq.heappop(freqs_heap)[1]) return answer Counter를 사용하여 문자열의 빈도수로 딕셔너리 생성하여준다음 상위 k개를 뽑아주면 된다. 힙은 키순서대로 정렬 되기 때문에 빈도수를..
중복 문자 없는 가장 긴 부분 문자열 - 해시 중복 문자 없는 가장 긴 부분 문자열 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라. 입력:"abcabcbb 출력:3 설명 : 정답은 abc로 길이는 3이다. 내가 푼 코드 import heapq from collections import deque def solution(a): temp=[] temp=deque(temp) answer=[] for i in a: # 들어온 문자열을 돌아간다 if i not in temp: #들어온 문자열이 temp에 없다면 temp.append(i) #삽입 else: #중복이 된다면 q =(''.join(temp)) #들어오기 전까지의 문자열로 묶음 heapq.heappush(answer,(-len(q),q)) #answer에 문자열길이를 음수로..
보석과 돌 - 해시 보석과 돌 J는 보석이며 S는 갖고 있는 돌이다. S에는 보석이 몇 개나 있을까? 대소문자는 구분한다. 입력 : J="aA" S="aAAbbbb 출력 : 3 from collections import Counter J='aA' s="aAAbbbb" s=(Counter(s)) #counter를 이용하여 s={'b': 4, 'A': 2, 'a': 1}로 저장 answer=0 for i in J: # stone안에 보석이 있으면 answer+=보석수 answer+=s[i] print(answer) 문제풀이 간단한 문제였다. s를 Counter을 이용하여 빈도수가 나오는 딕셔너리로 저장한후 보석인것을 찾아 answer에 더해주면서 해결. 알게된 것 파이썬에서 제공하는 collections 모듈의 Counter클..
스택을 이용한 큐 구현 - 큐 Implement Queue Using Stack 스택을 이용해 다음 연산을 지원하는 큐를 구현하라. push(x): 요소x를 큐 마지막에 삽입한다. pop(): 큐처음에 있는 요소를 제거한다. peek(): 큐 처음에 있는 요소를 조회한다. empty(): 큐가 비어있는지 여부를 조회한다. class MyQueue: def __init__(self): self.input = [] self.output = [] def push(self, x: int) -> None: self.input.append(x) def pop(self) -> int: self.peek() return self.output.pop() def peek(self) -> int: if not self.output: while self...
프린터 큐 - 큐 백준_프린터큐 백준 프린터큐 from collections import deque import sys a= int(input()) for i in range(a): num,cur = map(int, input().split()) important=[] important =list(map(int, sys.stdin.readline().split())) # 중요도 queue=deque(important) count=0 while queue: best = max(queue) #가장 중요한일 front =queue.popleft() #가장 처음있는 일을 뺴본다. cur-=1 #하나 뺴니까 인덱스를 왼쪽으로 이동 if(best==front): #가장 중요한게 맨처음 count +=1 #일을 처리한 횟수1더해주기 ..
카드2 - 큐 스택수열 백준 스택 수열. stack =[] answer =[] n = int(input()) # 8 (입력 개수) arr = [int(input()) for _ in range(n)] # [4, 3, 6, 8, 7, 5, 2, 1] (입력 배열) index = 0 for i in range(1,n+1): # 1 2 3 4 5 6 7 8 stack.append(i) # 스택이 비어있으면 안되서 answer.append('+') while stack and stack[-1] == arr[index]: # 스택이 안비어있고 스택의 마지막이 배열의 인덱스와 같으면 stack.pop() answer.append('-') index+=1 #인덱스 올려주기 if stack: print(..
스택 수열 - 스택 스택수열 백준 스택 수열. stack =[] answer =[] n = int(input()) # 8 (입력 개수) arr = [int(input()) for _ in range(n)] # [4, 3, 6, 8, 7, 5, 2, 1] (입력 배열) index = 0 for i in range(1,n+1): # 1 2 3 4 5 6 7 8 stack.append(i) # 스택이 비어있으면 안되서 answer.append('+') while stack and stack[-1] == arr[index]: # 스택이 안비어있고 스택의 마지막이 배열의 인덱스와 같으면 stack.pop() answer.append('-') index+=1 #인덱스 올려주기 if stack: print(..

티스토리툴바