본문 바로가기
반응형

코딩테스트 준비211

C# - Where와 Count를 사용해서 배열에 특정 요소의 개수 구하기 알고리즘 문제를 풀다보면 문제에서 특정 조건의 요소의 개수를 구할때가 나온다. Where와 Count를 이용하면 한줄로 간단히 표현할 수 있다. 배열에서 짝수 요소의 개수를 구한다고 해보자 01 기존 방법 int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int count = 0 for(int i = 0; i n % 2 == 0).Count(); Where를 통해 주어진 배열에서 짝.. 2023. 12. 15.
백준 C# - 2667 +) 풀이 이 문제를 풀기 앞서 아래 문제를 풀고 오는 것을 추천한다. 2667이 아래 문제의 심화버전이다. 백준 C# - 1012 백준 C# - 1012 +) 풀이 먼저 문제 이해부터 해보자 문제에서 배추 흰지렁이가 한 배추의 상하좌우로 다른 배추로 이동할 수 있다고 나와있다. 1) DFS를 이용해서 상하좌우로 이동할 수 있을때까지 이동하면서 확인해야 code-piggy.tistory.com 백준 C# - 1012를 풀었다는 전제하에 문제 풀이를 진행하겠다. 출력에 필요한 두 부분 01 총 그룹의 갯수 출력(1012 : 지렁이의 갯수) 이 부분은 원래 1012와 동일하게 출력하면 된다. 02 단지내 집의 수 오름차순으로 출력(1012 : 각 지렁이에 해당되는 배추들의 수) 각 단지내 집의 수는 DFS가 호출되는 .. 2023. 12. 14.
백준 C# - 1012 +) 풀이 먼저 문제 이해부터 해보자 문제에서 배추 흰지렁이가 한 배추의 상하좌우로 다른 배추로 이동할 수 있다고 나와있다. 1) DFS를 이용해서 상하좌우로 이동할 수 있을때까지 이동하면서 확인해야 한다. 2) 그 그룹의 끝에 다다랐으면 다음으로 배추가 심어진 곳을 찾아 배추가 심어진 곳이 없을때까지 이를 반복하면 된다. 상하좌우 탐색에서 -값이 나오는 경우를 먼저 살펴보자 1 5 3 6 0 2 1 2 2 2 3 2 4 2 4 0 문제를 표로 나타내면 아래와 이미지와 같다. 상하좌우 탐색 static int[] dirX = { 1, -1, 0, 0 }; static int[] dirY = { 0, 0, 1, -1 }; 만약 x가 0이고 y가 4인 경우 for (int i = 0; i < 4; i++) { int .. 2023. 12. 14.
백준 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.
백준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.
반응형

티스토리툴바