본문 바로가기

Project31

[기초 알고리즘] 그래프(기초Ⅲ) 그래프 강한 연결과 강한 연결 요소 강한 연결(Strongly connected) 방향성 그래프에서 정점의 각 쌍이 서로 도달 가능하다면 강하게 연결무방향성 그래프에서는 방향에 관계 없기 때문에 방향성 그래프에서는 이렇게 표현한다.강한 연결 요소방향성 그래프에서 최대한 많은 정점을 강하게 연결한 하위 그래프 완전 그래프(A complete graph)무방향 그래프에서 모든 정점의 쌍이 서로 인접한 경우Q) 정점이 n 개라면 간선은 몇개 일까? A) #1은 1개 / #2는 3개 / #3는 6개 포레스트(Forest)순환하지 않는 무방향성 그래프어떤 정점 두 곳을 정해 경로를 만들었을 때 시작점과 도착점이 같지 않는 것을 말합니다. 트리(Tree)포레스트가 연결되어 있는경우즉, 연결된 비순환 무방향성 그래프.. 2017. 8. 10.
[기초 알고리즘] 그래프(기초Ⅱ) 그래프 인접(Adjacency)(U,V)라는 간선이 있으면, 정점 V와 정점 U가 인접하다 라고 합니다.하지만 여기에서 방향성과 무방향성의 표현이 다릅니다. 방향성 그래프정점 B는 정점 A에 인접한다. 하지만 정점 A는 정점 B에 인접하지 않는다.도착하는 정점에 맞춰서 이야기합니다.인접관계가 동일하지 않습니다. 무방향성 그래프정점 B는 정점 A에 인접한다. 그리고 정점 A도 정점 B에 인접한다.인점관계가 동일합니다. 차수(Degree)한 정점에 관하여 다른 정점이 얼마나 연결이 되어있는지를 표현하는 것입니다. 방향성 그래프방향이 있기 때문에 진출차수와 진입차수로 나눌 수 있습니다.정점 B의 진출 차수는 2이다.정점 B의 진입 차수는 1이다. 무방향성 그래프이 그래프는 진입/ 진출차수로 정의할 수 없기 때.. 2017. 8. 10.
[기초 알고리즘] 그래프(기초Ⅰ) 그래프 그래프는 우리가 중학교 때부터 많이 봐오던 익숙한 것입니다. 오늘 그래프에 대해 공부를 해 볼겁니다. 그래프는 기본적으로 정점(Vertex)와 간선(Edge)로 이루어져 있어요 이때 그래프 A/B를 정점이라고 부르고 A와 B를 잇는 선을 간선이라고 부릅니다 그리고 간선에는 두 가지 종류가 있습니다. 방향이 있는 것과 방향이 없는 것 방향성 그래프(Directed Graph) 정점(V)V = {A, B, C, D, E, F}간선(E)E = {(A,B), (A,C), (B,B), (B,C), (B,D), (C,D), (D,C), (E,F)} 방향성을 가지는 그래프이기 때문에 (C, D) 와 (D, C) 간선 모두 가집니다. 즉, 이 두 간선은 서로 다르다고 표현할 수 있습니다. 무방향성 그래프(An .. 2017. 8. 10.
[백준 알고리즘] 1057번(토너먼트) [백준 알고리즘] 1057 토너먼트 문제는 일단 이해가 쉽다. 우리 모두 알고 있는 토너먼트 형식이고 입력값으로 주어진 번호로 몇 번째에 서로 대결을 하는지 구하는 것입니다. 입력 값으로는 총 인원 / 김지민 번호 / 임한수 번호 가 주어집니다. 나머지는 누가 이기던 상관이 없으며 김씨와 임씨는 무조건 이긴다는 가정이 있습니다. 8번인 김씨와 9번인 임씨에 대한 규칙이 생깁니다.(12까지만 했습니다.) 김씨(빨) 8 > 4 > 2 > 1 > 대결임씨(파) 9 > 5 > 3 > 2 > 대결 그렇다면 짝수 홀수 모두 N = N/2 + N%2 라는 규칙이 생깁니다.(여기서 %는 나머지를 구하는 것입니다.) 이 규칙을 구하셨다면 금방 해결이 될겁니다. 여기까지 이해가 된다면 다 끝난겁니다. 12345678910.. 2017. 8. 8.
[백준 알고리즘] 1547(공) [백준 알고리즘] 쉬운 문제부터 모두 정복하고 점차 어려운 문제에 도전하기로 마음 먹었어요 이번 문제는 1547번 공 문제입니다. 야바위하는 알고리즘을 짜면 되는데요 쉬워서 금방 해결 하실 겁니다. 작성한 알고리즘을 이해하는 데에도 문제 없을 것입니다. 1234567891011121314151617181920212223242526272829import java.util.Scanner; public class Beak1547 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int[] list = {1,0,0}; int number1, number2; int tmp; whil.. 2017. 8. 8.

티스토리툴바