본문 바로가기

Algorithms and Languages

 (50)
[Python/DailyAlgo] 63. 미로 찾기 2 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기DFS/BFShttps://dailyalgo.kr/ko/problems/63풀이DFS 풀이 -> 시간초과# DFS 풀이def solution(maze): # 직전 칸까지의 거리도 넣어줘야함. def dfs(x, y, distance): for i in range(4): nx, ny = x + dx[i], y + dy[i] if 0 BFS 풀이# BFS 풀이from collections import dequedef solution(maze): # 얘는 재귀가 아니고 한 번만 호출되니까, def bfs(): #..
[Python/DailyAlgo] 62. 미로 찾기 1 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기DFS/BFShttps://dailyalgo.kr/ko/problems/62풀이DFS 풀이# DFS# 코테 수준에서는, 재귀 호출 깊이를 1000을 초과하지 않게 냄.# 왜냐면 자바나 C++은 걍 초과해버려서. # 근데 이런 백준 이런건 이렇게 재취 깊이가 1000이 넘어가는 문제를 내기도 함.# 따라서, 그냥 풀면 `Recursionerror`가 나옴.import syssys.setrecursionlimit(10**6)def solution(maze): def dfs(x, y): # 3. 이동하기 for i in range(4): nx, ny..
[Python/백준] 2606. 바이러스 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기더보기https://www.acmicpc.net/problem/2606풀이import sysinput = sys.stdin.readline# 그래프 탐색 알고리즘 기본 문제.n = int(input())m = int(input())graph = [[] for _ in range(n + 1)]for _ in range(m): s, e = map(int, input().split()) graph[s].append(e) graph[e].append(s)def dfs(node): # 2. 재귀하며 현재 정점 action 실행 global counts counts += ..
[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..

티스토리툴바