본문 바로가기
반응형

코딩테스트 준비211

백준 C# - 7562 +) 풀이 문제에서 최소부분이 있으면 BFS를 이용해야 한다. 앞서 BFS문제들을 풀어봤을때 큰 틀은 비슷한 것을 알 수 있다. 이 문제에서 크게 다른 점이 있다면 나이트의 움직임이다. 직접 좌표를 찍어보자 그러면 이를 각각의 배열들로 표현하면 아래와 같이 나온다. static int[] dirX = { 2, 1, -1, -2, -2, -1, 1, 2 }; static int[] dirY = { 1, 2, 2, 1, -1 , -2 , -2, -1 }; BFS 알고리즘 static void BFS(int x , int y, int n) { Queue queue = new Queue(); queue.Enqueue(new Tuple(x,y)); while (queue.Count>0) { Tuple now = queue... 2023. 12. 20.
백준 C# - 7576 +) 풀이 문제에 최소가 들어가면 BFS와 관련된 확률이 높다. 들어가기 앞서 주의! 01 그래프 (0,0)부터 입력받기 DFS, BFS문제에서 음수가 되는 경우를 배제하기 위해서 그래프값을 (1,1)을 넣으면서 진행하였는데 여기서는 그렇게 하면 안된다. 원인이 이거인지 모르고 열심히 그리다가 시간을 많이 소모하였다.. 하ㅏㅎㅏ.. 앞으로 (0,0)에 넣고 조건문을 넣어 푸는게 좋을 것 같다는 생각이 들었다. 02 string에 어떤 값이 들어가는지 꼭 확인하기 string문을 입력받으면 띄어쓰기 까지 입력이 받아진다. string s = Console.ReadLine() 그래서 Replace를 사용해서 띄어쓰기를 삭제했다. string s = Console.ReadLine().Replace(" ",""); 그랬더.. 2023. 12. 19.
백준 C# - 4963 +) 풀이 우리가 앞서 풀었던 문제는 상하좌우만 움직이는 문제이다. 하지만 이번 문제는 대각선까지 움직이는 것이 추가되었다. 이부분만 다르지 나머지 부분은 똑같다. 나머지 부분에 대한 설명은 아래 문제 참조 백준 C# - 2667 +) 풀이 이 문제를 풀기 앞서 아래 문제를 풀고 오는 것을 추천한다. 2667이 아래 문제의 심화버전이다. 백준 C# - 1012 백준 C# - 1012 +) 풀이 먼저 문제 이해부터 해보자 문제에서 배추 흰지렁이가 한 배추의 code-piggy.tistory.com 대각선 + 상하좌우 움직이는 방법 대각선과 상하좌우로 움직이는 경우의수를 구하면 아래와 같이 9가지가 나온다. 01 상하좌우 코드 상하좌우를 확인하면서 구하는 코드는 아래와 같이 구했었다. static int[] dirX .. 2023. 12. 18.
백준 C# - 2178 +) 풀이 최단거리 문제는 BFS를 사용하는 것이 좋다. 101111 101010 101011 111011 먼저 BFS의 최단 경로 과정을 보면 아래와 같이 진행된다. 해당 깊이에 갈 수 있는 주변 칸을 탐색하고 다음 깊이로 넘어가는 것을 확인할 수 있다. BFS가 진행됨에 따라 칸의 값 갱신 BFS를 진행하면서 현재 칸을 방문할때 이전의 방문했던 칸에 1을 더한 값을 현재 셀에 저장하여 몇 번째 방문한 것인지 를 저장하면 마지막 칸에 최단 경로가 저장된다. graph[newX, newY] = graph[now.Item1, now.Item2] + 1; BFS 알고리즘 짜기 01 큐 초기화 및 시작 지점 추가하기 Queue queue = new Queue(); // 시작 좌표값 queue에 추가 queue.Enque.. 2023. 12. 16.
C# - DFS/BFS 둘 중 어느것을 사용해서 문제를 풀어야 할까? DFS/BFS 둘 중 어느것을 사용해서 문제를 풀어야 할까? BFS / DFS 그래프의 모든 정점을 방문하는 문제 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다. DFS 01 특정 경로를 찾는 경우 A부터 B까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제 등 각각의 경로마다 특징을 저장해야 할때는 DFS사용한다. BFS는 경로의 특징을 가지지 못한다. 02 백트래킹 모든 가능성을 찾아 현재 시점에서 더 이상 진행할 수 없는 경우 이전 단계로 돌아가 다른 가능성을 탐색할 때 사용된다. 03 사이클 검출 그래프에서 사이클이 존재하는지 검출하는 문제 04 트리 구조 검색 트리에서 특정 노드를 찾거나 특정 조건을 만족하는 .. 2023. 12. 16.
프로그래머스 C# - 다음 큰 숫자 문제를 이해하면 쉽게 이해할 수 있는 문제이다. 간단히 설명하자면 주어진 숫자에서 1의 갯수와 같은 다음 숫자를 구하면 된다. C#에서 Convert.ToString을 이용하면 쉽게 진법변환을 할 수 있다. (자세한 내용은 아래 게시글 참조) C# - Convert.ToString 메서드로 진수 변환(10진수를 2진수, 8진수, 16진수로) Convert.ToString 메서드 정수,실수,날짜등 다양한 데이터 유형을 문자열로 변환한다. public static string ToString(int value, int toBase); 매개변수 value : 변환할 32비트 부호 있는 정수 toBase : 변환 값의 진수로 code-piggy.tistory.com 문제 푸는 순서 01 n을 2진수로 바꾼 다음.. 2023. 12. 15.
반응형

티스토리툴바