본문 바로가기
반응형

전체 글553

백준 C# - 1707 +) 풀이 이분 그래프 그래프의 모든 정점을 서로 다른 두가지 색으로 칠할 수 있는 그래프이다. 그래프의 정점을 두 그룹으로 나누었을때 같은 그룹에 속한 정점들 간에는 간선으로 연괼되어 있지 않고 서로 다른 그룹에 속한 정점들 간에만 간선으로 연결되어 있다. 이분 그래프 알고리즘 주로 DFS나 BFS를 이용해서 구현한다. 01 그래프의 시작 정점을 색을 칠한다. 02 다음 정점은 현재 정점과 다른 색으로 칠한다. 03 만약 이미 색이 칠해져 있는데 현재 정점과 인접한 정점의 색이 같다면 이는 이분 그래프가 아니다. 문제를 풀어보자 DFS을 이용하자 static void DFS(int now, int group) { visited[now] = group; foreach(int next in graph[now]) { .. 2023. 12. 10.
백준 C# - 11724 +) 풀이 연결 요소(Connected Component)수 구하기 그래프에서 각 노드가 서로 연결된 갯수를 구하면 된다. 이는 한 노드를 잡고 DFS를 통해 그 노드에 연결된 모든 노드들을 방문한다. 이를 count를 증가시키면서 방문이 되지 않는 노드가 없을때까지 반복하면된다. 01 DFS public static void dfs(int now) { visited[now] = true; foreach (int next in graph[now]) { if (visited[next]) continue; dfs(next); } } 02 그래프 입력받기 int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse); int n = input[0]; int .. 2023. 12. 10.
Effective C# - Item 21 타입 매개 변수가 IDisposable을 구현한 경우를 대비하여 제네릭 클래스를 작성하라 제약 조건은 두 가지 역할을 한다. 1. 런타임 오류가 발생할 가능성이 있는 부분을 컴파일 타임 오류로 대체 2. 타입 매개변수로 사용할 수 있는 타입을 명확히 규정하여 사용자에게 도움 제약 조건은 해당 타입이 특정 인터페이스를 구현하는 등의 특성을 지정할 수 있지만 해당 타입이 특정 작업을 수행하도록 강제하지는 않는다. 예를 들어 IDisposable을 구현하는 타입이라면 특별한 추가 작업이 필요하다고 설명했지만 제약 조건 자체는 해당 타입이 IDisposable을 구현하는지 여부만 확인할 뿐 실제로 IDisposable에서 요구하는 작업을 강제하지는 않는디. 제네릭 메서드 내에서 타입 매개 변수로 주어지는 타입을 이용하여 인스턴스를 생성하는 경우 발생 T가 IDisposable을 구현한 타입을 경우 .. 2023. 12. 10.
Effective C# - Item20 IComparable<T>와 IComparer<T>를 이용하여 객체의 선후 관계를 정의하라 객체의 값 비교(정렬 등)정의하는 인터페이스 두 가지 IComparable과 IComparer 1. IComparable 타입의 기본적인 선후 관계 정의 CompareTo(Object) public int CompareTo (object? obj); 매개변수 obj : 비교할 대상 객체 반환 음수 : 현재 객체가 대상 객체보다 작은 경우 0 : 현재 객체가 대상 객체와 같은 경우 양수 : 현재 객체가 대상 객체보다 큰 경우 01 (제네릭 버전) IComparable public class Piggy : IComparable { public string Name { get; set; } public int Age { get; set; } public int CompareTo(Piggy other) { re.. 2023. 12. 10.
Effective C# - Item19 런타임에 타입을 확인하여 최적의 알고리즘을 사용하라 만약 어떤 알고리즘이 특정 타입에 대해 더 효율적으로 동작한다고 생각된다면 그냥 그 타입을 이용하도록 코드를 작성하자. 이를 위해 제약 조건을 설정하는 것은 항상 효과적인 방법은 아니다. 제네릭의 인스턴스화는 런타임의 타입을 고려하지 않으며 컴파일타임의 타입만을 고려한다. 효율적인 코드를 작성하려면 이러한 사실을 반드시 알고있어야 한다. 컴파일 타임(Compile Time) 컴파일러에 의해 소스코드에서 목적코드(기계어 또는 중간코드)로 변환되는 동안을 가리킨다. 컴파일 타임에는 코드의 구문분석, 타입검사, 최적화등이 이루어진다. 제네릭의 인스턴스화는 주로 컴파일 타임에 이루어진다. 코드가 실행되기 전에 컴파일러는 제네릭 코드를 실제 타입으로 변환하고 최적환한다. public class MyPiggy { .. 2023. 12. 10.
백준C# - 1260 +) 풀이 DFS와 BFS를 구현하는 문제이다. 1. 초기 설정 01 graph와 visited 변수 설정 graph는 그래프를 표현하기 위한 인접리스트이고 vistied는 정점의 방문 여부를 나타내는 배열이다. static List[] graph; static bool[] visited; 02 입력 받기 int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse); int N = input[0]; // 정점 int M = input[1]; // 간선 int V = input[2]; // 탐색을 시작할 정점의 번호 03 그래프 초기화 graph = new List[N + 1]; for (int i = 1; i 0) { int now = queue.De.. 2023. 12. 9.
반응형

티스토리툴바