전체 글

오늘의 학습 키워드DFS백준 24479(알고리즘 수업 - 깊이 우선 탐색 1) 공부한 내용DFS 개념그래프에서 깊이를 우선으로 탐색하는 알고리즘시작 정점에서 다음 분기로 넘어가기 전에, 해당 분기를 완벽하게 탐색해야 함접근 방법DFS의 핵심인 visited를 활용. 현재 정점을 방문 처리 하고 -> 다른 정점을 확인, 그리고 방문 수서 숫자를 늘려주는 것이 핵심핵심 로직 설명visited 배열로 방문 순서 관리인접 리스트를 그래프로 표현(graph = [[] for _ in range(N+1)]0부터 계산하는 것이 아니니까 N+1오름차순 방문을 해야하기 때문에 그래프를 만들고 sort로 정렬재귀를 통해서 DFS를 구현재귀 깊이 제한을 늘려야지 RuntimeError가 발생하지 않음!import syssy..

오늘의 학습 키워드이분탐색프로그래머스 입국심사공부한 내용문제 이해n명의 사람이 입국심사를 받아야 함각 심사관마다 심사하는데 걸리는 시간이 다름모든 사람이 심사를 받는데 걸리는 최소 시간을 구해야 함접근 방법이분탐색을 통해 최적의 시간을 찾아가는 방식 사용탐색 범위최소 시간(left): 1최대 시간(right): 가장 긴 심사시간 × 인원수핵심 로직 설명중간값(mid) 시간 동안 처리할 수 있는 총 인원 계산각 심사관별로 주어진 시간 동안 처리 가능한 인원을 합산처리 가능 인원이 목표 인원보다 많으면 시간을 줄임처리 가능 인원이 목표 인원보다 적으면 시간을 늘림# 항해 99 Day 3# 프로그래머스 입국심사# 이분탐색을 통해서 총 걸리는 시간을 점점 좁혀나가는 형식으로 푸는 문제def solution(n,..

오늘의 학습 키워드이분탐색백준 11561번 징검다리공부한 내용문제의 핵심각 점프마다 이전 점프보다 최소 1 이상 긴 거리를 뛰어야 함마지막 N번 징검다리는 반드시 밟아야 함최대한 많은 징검다리를 밟는 것이 목표해결 방법이분탐색을 통해 가능한 최대 점프 횟수를 찾음k번 점프할 때 필요한 최소 거리는 1 + 2 + 3 + ... + k = k(k+1)/2이 거리가 N보다 작거나 같아야 하며, N번 징검다리까지 도달 가능해야 함코드 원리start와 end로 탐색 범위 설정mid값으로 가능한 점프 횟수 계산등차수열의 합 공식 활용하여 필요한 최소 거리 계산이분탐색으로 최적값 도출정답 코드T = int(input())for _ in range(T): N = int(input()) start = 0 ..

99클럽 코테 스터디 0일차 TIL + 이분탐색오늘의 학습 내용이분탐색을 활용한 알고리즘 구현시간 초과 문제 해결 방법백준 1072번 '게임'공부한 내용처음에는 단순하게 게임 한판 씩 추가로 수행하며 변화하는 승률을 비교하는 방식을 사용하였습니다. 그러나 입력 값이 큰 경우에는 시간 초과 문제가 발생하였습니다.초기 시간 초과 코드문제점:한 판씩 확인하는 방식으로 시간복잡도가 O(N)입력값이 큰 경우 실행 시간이 매우 길어짐메모리 사용량도 비효율적X, Y = map(int, input().split())Z = (Y * 100) // X # 승률이 99%이상이면 절대 바뀔 수 없음if Z >= 99: print(-1)else: result = 0 while True: # 게임 ..

숫자가 가장 큰 인접한 곳으로 동시에 이동문제https://www.codetree.ai/missions/2/problems/move-to-max-adjacent-cell-simultaneously?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 코드위치 저장을 위해서 딕셔너리 사용max_value를 사용해 가장 큰 값이 있는 곳으로 이동새로운 위치로 구슬을 업데이트하고, 하나만 존재할 수 있도록 구현n, m, t = map(int, input().split())graph = [list(m..