개발

그래프란? 그래프는 여러 개의 점(정점)과 선(간선)으로 이루어진 자료구조이다. 현실 세계에서 사람과 사람의 관계, 도로 지도, 지하철 노선도 등을 그래프로 표현할 수 있다. 간단히 말하면, “노드끼리 연결된 관계를 표현하는 자료구조”이다. 그래프 …

문제 링크 : https://www.acmicpc.net/problem/11742 문제 탐색하기 1) 문제 분석 정점(vertex) : N 간선(edge) : M M개 줄에 대한 양 끝점 : u, v 같은 간선은 1번만 2) 가능한 시간복잡도 (1)…

문제 링크 : https://www.acmicpc.net/problem/17204 문제 탐색하기 1) 문제 분석 N : 사람 수, K : 보성이 번호 줄마다 지목하고자 하는 사람의 수 (origin -> next) 게임 시작하는 사람은 0번 보성이가…

문제 링크 : https://www.acmicpc.net/problem/10451 문제 탐색하기 1) 문제 분석 순열 사이클이란?: 순열에서 특정 숫자를 따라가다가 다시 원래 숫자로 돌아오면 그것을 하나의 사이클로 본다. 문제 목표: 주어진 순열에서…

문제 링크 : https://www.acmicpc.net/problem/1463 문제 탐색하기 1) 문제 분석 X가 3의 배수면 3으로 나눈다. X가 2의 배수면 2로 나눈다. 두 가지 경우가 다 아니면 1을 뺀다. 연산을 사용하는 횟수의 최솟값을 …

문제 링크 : https://www.acmicpc.net/problem/1010 문제 탐색하기 1) 문제 분석 서쪽 사이트 N개 동쪽 사이트 M개 서쪽 사이트 개수만큼 다리를 지어야 하며, 한 사이트에는 최대 한 개의 다리만 연결 다리는 서로 겹칠 …

문제 링크 : https://www.acmicpc.net/problem/2775 문제 탐색하기 1) 문제 분석 a층의 b호 인원 수 = 자신의 아래층(a-1)층의 1호부터 b호까지 사람들의 수의 합 0층의 i호에는 i명이 산다. 3층 : 1 / 5 …

문제 링크 : https://www.acmicpc.net/problem/2748 문제 탐색하기 1) 문제 분석 비포나치 수는 0과 1로 시작. 2번째 부터는 바로 앞 두 비포나치 수의 합이 된다. 식 : Fn = Fn - 1 + Fn -2 ( n >…

문제 링크 : https://www.acmicpc.net/problem/2578 문제 탐색하기 1) 문제 분석 5*5 빙고판, 25개의 숫자 세 개의 선이 그어지면, 빙고 사회자가 몇 번째 수를 부르면 철수가 빙고를 외치는지 출력 2) 가능한 시간복…

DP란? Dynamic Programming(DP, 동적 프로그래밍)은 복잡한 문제를 하위 문제로 나누어 해결한 뒤, 그 결과를 저장하여 중복 계산을 피하는 알고리즘 기법이다. -> 간단히 말하면, "한 번 계산한 값은 다시 계산하지 않도록 저장해두…

문제 링크 : https://www.acmicpc.net/problem/2578 문제 탐색하기 1) 문제 분석 5*5 빙고판, 25개의 숫자 세 개의 선이 그어지면, 빙고 사회자가 몇 번째 수를 부르면 철수가 빙고를 외치는지 출력 2) 가능한 시간복…

문제 링크 : https://www.acmicpc.net/problem/7568 문제 탐색하기 1) 문제 분석 몸무게, 키 두 개의 값이 모두 커야 덩치가 크다고 얘기할 수 있다. 본인보다 덩치가 큰 사람의 수 + 1 값이 등수가 된다. 같은 덩치 …