본문 바로가기

전체 글

 (151)
[Python/DailyAlgo] 28. 그래프 탐색 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기DFS/BFShttps://dailyalgo.kr/ko/problems/28풀이DFS 풀이# counts 쓴 버전def solution(n, edges): def dfs(node): # 지금 있는 위치가 local인데, # 그 local보다 한 레이어 바깥에 있는, # 즉 nonlocal한 변수인 counts를 여기서 가져와 쓰겠다는 거 # 두 레이어 바깥에 있었다면 global을 썼어야 함. nonlocal counts counts += 1 # 우리는 dfs에 그 노드가 호출된 것 자체가 ..
[알고리즘 코딩캠프 5일차] 그래프 탐색 알고리즘: DFS, BFS 제가 재학 중인 대학교에서 열린 `파이썬 알고리즘 코딩캠프(25.02.03 ~ 25.02.14)` 수업을 듣고 정리한 글입니다.목차 :그래프 탐색 알고리즘DFSBFS그래프 탐색 알고리즘더보기코테 비율 40% 이상 유형 문제. 굉장히 중요한 유형임.거의 무조건 코테에 한 문제 이상씩은 나온다 보면 됨. 그래프 자료구조는 탐색 알고리즘에 사용됨.`그래프`라는 자료구조를 가지고, `그래프 탐색`이란 알고리즘을 설계할 것.`그래프 탐색 알고리즘` : 시작 정점에서 간선을 타고 이동할 수 있는 모든 정점을 찾는 알고리즘. 일종의 완전 탐색임.깊이우선탐색과 너비우선탐색은 스택과 큐의 개념이 같이 들어감.DFS : 스택(재귀) + 그래프BFS : 큐(덱) + 그래프DFS더보기모든 정점을 방문할 때 유리(사실 모든 정..
[Python/백준] 9012. 괄호 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기더보기스택https://www.acmicpc.net/problem/9012풀이import sysinput = sys.stdin.readline# 용어정리)# 괄호 문자열(Parenthesis String, PS)# : 두 개의 괄호 기호인 '('와 ')' 만으로 구성되어 있는 문자열.# 올바른 괄호 문자열(Valid PS, VPS)# : 괄호 문자열 중에서, 괄호의 모양이 바르게 구성된 문자열.# 기본 VPS# : 한 쌍의 괄호 기호도 된 '()' 문자열.# 만약 x가 VPS라면,# '(x)'도 VPS가 된다. (당연하지?)# 그리고 두 VPS x, y를 접합(concatenation)시킨# ..
[Python/백준] 2164. 카드2 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기더보기더보기더보기큐, 덱https://www.acmicpc.net/problem/2164풀이# 1차 풀이, 최적화 안됨from collections import dequeimport sysinput = sys.stdin.readline# 입력 : 카드 개수를 의미하는 정수 N (1 1 2 3 4# 2. 1 2 3 4 -> 2 3 4 1# 큐를 써서 풀어야 한다고 판단한 근거)# '제일 위에 있는 카드를 바닥에 버린다'# '제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다'# 와 같이, ""양 끝단에서 데이터의 삽입과 추출이 이루어지고 있기에???""# 따라서, 큐를 써서 풀어야겠다..
[Python/백준] 10773. 제로 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기더보기더보기스택https://www.acmicpc.net/problem/10773풀이import sysinput = sys.stdin.readline# 입력 : 첫 줄에 정수 K# 이후 K개의 줄에 0 ~ 100만 사이의 정수가 하나씩 주어짐.# 정수가 0 -> 가장 최근에 쓴 수 지우기# 아니면 -> 해당 수를 쓴다.# 이거 스택 문제네!!# 정수가 0이면 지울 수 있는게 보장되어 있음.stack = []K = int(input())for _ in range(K): num = int(input()) if num == 0: stack.pop() # conti..
[Python/DailyAlgo] 81. 스택, 82. 큐, 83. 덱 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기스택, 덱https://dailyalgo.kr/ko/problems/81https://dailyalgo.kr/ko/problems/82https://dailyalgo.kr/ko/problems/83 간단한 문제들. 모아서 짤막하게 정리했다.81. 스택# 강사님 풀이def solution(queries): stack = [] answer = [] for query in queries: # 'pop'일 경우를 먼저 걸러내는 게 좋다 if query == 'pop': # 'pop'일 경우 # empty stack 조건 ..
[Python/백준] 9291. 스도쿠 채점 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기더보기이차원리스트https://www.acmicpc.net/problem/92911차 풀이 - 이미 False인 경우도 계속 검사해 비효율적import sysinput = sys.stdin.readlinen = int(input())case = 0for _ in range(n): flag = True case += 1 sudoku = [list(map(int, input().split())) for _ in range(9)] # 중첩 반복문 들어가긴 하나, 스도쿠 판 크기 81밖에 안되니 괜찮아보임 # 단순 구현력 묻는 문제인듯. for i in range(9)..
[Python/DailyAlgo] 71. 이차원 배열의 델타 탐색 1 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기이차원리스트https://dailyalgo.kr/ko/problems/71풀이def solution(numbers, r, c): n = len(numbers) m = len(numbers[0]) # 여기서 주의!! r, c는 1 이상의 자연수임. # 즉, r과 c를 그대로 인덱스로 써버리면 1 차이가 남. # 따라서, 아래처럼 정의해주겠음. # 근데 그냥 내가 편한 걸로 정의해줬음. # 1. 기준점 잡기 x, y = r - 1, c - 1 # 2. 상 하 좌 우 델타값 정의 dx = [-1, 1, 0, 0] dy = [0, ..

티스토리툴바