본문 바로가기

Algorithms & Languages

 (78)
[알고리즘 코딩캠프 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, ..
[Python/백준] 20920. 영단어 암기는 괴로워 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기더보기정렬https://www.acmicpc.net/problem/209201차 풀이import sysinput = sys.stdin.readlinefrom collections import Counter# 우선순위1: 자주 나오는 단어일수록 앞에 배치한다.# 우선순위2: 해당 단어의 길이가 길수록 앞에 배치한다.# 우선순위3: 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다# 입력 : 단어의 개수 N과 외울 단어의 길이 기준이 되는 M# 길이가 M 이상인 단어만 선택할 거임.# 출력 : 단어장에 들어갈 단어 우선순위 따라 순서대로 출력n, m = map(int, input().spli..

티스토리툴바