분류 전체보기275 이분 그래프와 관련 알고리즘 이분 그래프는 노드를 두 그룹으로 나눌 수 있으며, 같은 그룹 내의 노드끼리는 간선이 연결되지 않는 그래프다. 이분 그래프와 알고리즘이분 그래프는 정점 집합을 두 개의 그룹(U, V)으로 나눌 수 있으며, 모든 간선이 서로 다른 그룹에 속한 정점들 사이에만 존재하는 그래프이다. 이분 그래프의 성질과 관련 알고리즘은 그래프 이론과 네트워크 문제에서 중요한 도구로 사용된다.이분 그래프의 정의와 특징두 정점 집합(U, V) 사이에만 간선이 존재하며, 같은 집합 내에는 간선이 없다.모든 사이클은 짝수 길이를 가진다.이분 그래프는 2-색칠 가능하다. 즉, 두 가지 색으로 모든 정점을 색칠할 때, 서로 연결된 정점이 다른 색을 가지도록 할 수 있다.이분 그래프 관련 알고리즘1. 이분 그래프 판별 알고리.. 2024. 11. 17. Python 표준 라이브러리: 꼭 알아야 할 핵심 모듈 1. Python 내장 함수Python은 다양한 작업을 쉽게 수행할 수 있도록 많은 내장 함수를 제공합니다. 대표적인 예로 print(), len(), sorted()와 같은 함수들이 있습니다. 이 함수들은 기본적인 작업을 편리하게 수행할 수 있게 해줍니다.더보기Python 내장 함수 주요 예시Python 내장 함수는 별도의 모듈 임포트 없이도 사용 가능한 도구들입니다. 다음은 자주 사용되는 몇 가지 함수와 그 활용 예시입니다.print()출력을 위한 함수로, 콘솔에 값을 출력합니다.print("Hello, Python!") # Hello, Python!len()데이터의 길이나 크기를 반환합니다.data = [1, 2, 3, 4]print(len(data)) # 4sorted()리스트나 반복 가능한 .. 2024. 11. 17. 백준2206🐨벽 부수고 이동하기 벽 부수고 이동하기 알고리즘 & 메모리 시각화 Reset Step Play/Pause Status: Ready Memory State: 2024. 11. 16. 백준6359🐨만취한 상범-파이썬 문제요약- n개의 방, n 라운드- 배수들의 중첩? 약수의 개수?- 에라스토테네스 체?상황 재현(문이 열린 것은 1)약수의 개수가 짝수면 열었다가 닫게 된다.못닫으려면 약수가 홀수 개. = 완전제곱수n까지의 완전제곱수의 개수찾기!=최대 완전제곱수의 루트.n,*r=map(int,open(0).read().split())print('\n'.join(f"{int(x**.5)}" for x in r))Rmx. 2024. 11. 16. 백준10809🐨알파벳 찾기 알파벳 찾기시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초256 MB24510413175810837853.396%문제알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.입력첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.출력각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다.만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다.예제 입력.. 2024. 11. 15. 두 배낭 문제 두 개의 배낭 문제시간 제한메모리 제한제출정답맞힌 사람정답 비율1초1024 MB202948948955.280%문제승형이와 원빈이는 배낭여행을 가기 위해 두 개의 배낭을 준비했다. 각 배낭에는 \(N\)개의 물건이 들어있으며:• 첫 번째 배낭에는 \(A_1, A_2, \dots, A_N\)의 무게를 가진 물건들이 아래에서 위로 순서대로 쌓여 있다. \(A_N\)이 맨 위에 있는 물건의 무게이다.• 두 번째 배낭에는 \(B_1, B_2, \dots, B_N\)의 무게를 가진 물건들이 아래에서 위로 순서대로 쌓여 있다. \(B_N\)이 맨 위에 있는 물건의 무게이다.배낭의 무게는 배낭 안에 남아있는 물건들의 무게의 합으로 정의된다. 원빈이는 최대 \(K\)번 두 배낭 중 하나를 선택하여 맨 위에 있는 물건을 .. 2024. 11. 15. 트리 구조 시각화 이진 트리의 종류와 특징 1. 기본 이진 트리 (Basic Binary Tree) 각 노드가 최대 2개의 자식을 가질 수 있는 가장 기본적인 트리 구조 자식이 없거나 1개만 있어도 됨 (불규칙한 형태 가능) 레벨별로 노드 수의 제한이 없음 .. 2024. 11. 14. 세그먼트-트리와-lazy-propagation을-이용한-구간-합-구하기 세그먼트 트리와 Lazy Propagation을 이용한 구간 합 구하기1. 문제 상황과 해결 전략문제의 핵심 요구사항긴 수열에서 구간 합을 구해야 함특정 구간의 모든 수를 갱신하는 연산이 빈번함두 연산이 번갈아가며 실행됨왜 일반적인 방법으로는 해결이 어려운가?배열을 직접 수정하는 경우: 구간 업데이트에 O(N)일반 세그먼트 트리: 구간 업데이트에 여전히 O(N)누적 합 배열: 한 값이 변경되면 모든 누적 합을 다시 계산해야 함해결 전략: Lazy Propagation이 적용된 세그먼트 트리구간 업데이트를 지연시켜 실제 필요할 때만 수행각 연산의 시간 복잡도를 O(logN)으로 최적화2. 알고리즘 상세 설명세그먼트 트리 기본 구조노드가 담당하는 정보구간 [start, end]의 합lazy 값 (지연된 업데.. 2024. 11. 14. 백준16928🐨뱀과 사다리 게임 https://www.acmicpc.net/problem/16928문제 분석뱀과 사다리 게임은 각 칸이 1부터 100까지 번호가 매겨진 보드에서 진행되며, 주사위를 굴려 나온 숫자만큼 이동한다. 도중에 사다리를 만나면 사다리를 타고 올라가고, 뱀을 만나면 뱀을 타고 내려간다. 목표는 최소한의 주사위 굴림 횟수로 100번 칸에 도착하는 것이다.BFS를 사용하는 이유는 BFS가 최단 경로 문제를 푸는 데 적합하기 때문이다. BFS는 그래프의 각 정점을 같은 깊이 순으로 탐색하며, 주사위를 굴리는 과정에서 각 칸을 노드로 보고 그래프 탐색을 진행할 수 있다.BFS 개념 설명너비 우선 탐색(BFS)은 시작 정점에서부터 인접한 모든 정점을 탐색한 후, 그 다음 깊이의 정점들을 탐색하는 방식이다. 일반적으로 큐(Q.. 2024. 11. 14. 기록 2024. 11. 14. 기록하기 2024. 11. 11. 백준27627🐨문자열을 두 개의 팰린드롬으로 분할하기 https://www.acmicpc.net/problem/27627문자열을 두 개의 팰린드롬으로 분할하기📌 문제 설명주어진 문자열을 두 개의 팰린드롬으로 분할할 수 있는지 확인하고, 가능하다면 그 분할 지점을 찾는 문제입니다. 예를 들어, "abaaba"라는 문자열이 주어졌다면 "aba aba"로 분할할 수 있습니다.def s(): s=open(0).read().strip() n=len(s) for i in range(1,n): a,b=s[:i],s[i:] if a==a[::-1]and b==b[::-1]:print(a,b);return print('NO')s()def s(): import os r=os.read(0,os.fstat(0).st_s.. 2024. 11. 9. 이전 1 2 3 4 5 6 ··· 23 다음
