반응형 코딩테스트 준비/자료구조 & 알고리즘42 C# - DFS/BFS 둘 중 어느것을 사용해서 문제를 풀어야 할까? DFS/BFS 둘 중 어느것을 사용해서 문제를 풀어야 할까? BFS / DFS 그래프의 모든 정점을 방문하는 문제 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다. DFS 01 특정 경로를 찾는 경우 A부터 B까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제 등 각각의 경로마다 특징을 저장해야 할때는 DFS사용한다. BFS는 경로의 특징을 가지지 못한다. 02 백트래킹 모든 가능성을 찾아 현재 시점에서 더 이상 진행할 수 없는 경우 이전 단계로 돌아가 다른 가능성을 탐색할 때 사용된다. 03 사이클 검출 그래프에서 사이클이 존재하는지 검출하는 문제 04 트리 구조 검색 트리에서 특정 노드를 찾거나 특정 조건을 만족하는 .. 2023. 12. 16. 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# - 완전 탐색(Brute force, 백트래킹,순열 조합,비트 마스크) 완점 탐색 모든 가능한 경우의 수를 탐색하여 최적의 결과를 찾는 방법이다. 01 브루트 포스(Brute force) 모든 가능한 결우를 순차적으로 나열하면서 원하는 결과를 찾는 방법이다. 예시 : 비밀번호 02 순열(Permutation) 선택 순서가 결과에 영향을 미치는 경우에 사용하는 방법이다. 03 조합(Combination) 선택 순서가 결과에 영향을 주지 않는 경우에 사용하는 방법이다. 04 백트래킹(BackTracking) 현재 상태에서 가능한 후부군으로 가지를 치며 탐색하는 알고리즘이다. 해가 될 것 같지 않은 경로는 더 이상 탐색하지 않고 되돌아간다. 예시 : 스도쿠 05 비트 마스크(Bit Mask) 이진수의 각 비트를 사용하여 경우의 수를 줄여가며 탐색하는 방법이다. 예시 : 부분 집합.. 2023. 12. 8. C# - 모듈러 연산(나머지 분배 법칙) 백준에서 DP관련 문제를 풀때 출력 부분에 큰 수로 나눈 나머지를 구하라는 부분이 계속 있어서 이부분이 왜 필요한지 자세히 알고 싶어졌다. 모듈러(Modulo) 나눗셈의 나머지를 계산하는 연산이다. 일반적으로 mod 혹은 %기호료 표시된다. a mod b = r a = 나눠지는수, b = 나누는 수, r 나머지 모듈러 연산과 분배법칙 어떤 수 m으로 나누었을 때 나머지는 덧셈에 대해 분배된다. ( a + b ) mod m = (( a mod m )+( b mod m )) mod m 예시 ( 7 + 5 ) mod 3=(( 7 mod 3 )+( 5 mod 3 )) mod 3 12 mod 3 = ( 1 + 2 ) mod 3 0 = 3 mod 3 DP에서 왜 모듈러 연산을 사용할까? 중간에 발생하는 값들이 매우.. 2023. 12. 4. C# - 퀵 정렬(Quick Sort) 퀵정렬(Quick Sort) 퀵 정렬에서는 피벗(Pivot)을 기준으로 배열을 분할하고, 각 부분 배열에 대해 정렬 작업을 수행하지만 피벗을 다시 처리하는 부분 문제는 호출하지 않는다. 한 번 피벗의 위치가 정해지면 해당 피벗은 정렬이 완료된 것으로 취급되어 중복 계산이 발생하지 않는다. 핵심 : 키 값을 잡아 더 큰것과 더 작은것 바꾸기 01 피벗 선택 퀵 정렬의 핵심은 피벗(pivot)을 선택하는 것이다. 피벗은 배열의 원소 중에서 하나를 선택한다. 피벗 선택의 효율성이 정렬 속도에 영향을 미친다. 02 분할 선택된 피벗을 기준으로 배열을 두 부분으로 분할한다. 피벗보다 작은 값은 피벗의 왼쪽으로, 큰 값은 피벗의 오른쪽으로 배치된다. 분할 과정 후에는 피벗의 위치가 최종적으로 결정된다. 03 정복 .. 2023. 11. 27. C# - PadLeft, PadRight메서드 사용해서 문자열 특정길이로 만드는 법 String.PadLeft 메서드 public string PadLeft(int totalWidth); 매개변수 totalWidth : 최종적으로 가져야 할 문자열의 전체 길이 코드 예제 string original = "Piggy"; string paddedLeft = original.PadLeft(10); Console.WriteLine(paddedLeft); // " Piggy" public string PadLeft(int totalWidth, char paddingChar); 매개변수 totalWidth : 최종적으로 가져야 할 문자열의 전체 길이 paddingChar : 패딩에 사용될 문자열 코드 예제 string original = "Piggy"; string paddedLeft = orig.. 2023. 11. 21. 이전 1 2 3 4 5 ··· 7 다음 반응형
