코딩정비소 코딩정비소

BFS란? BFS(Breadth-First Search, 너비 우선 탐색 )은 그래프 탐색 알고리즘이다. 시작 정점에서 가장 가까운 정점을 방문하고 멀리 떨어진 정점을 나중에 방문하는 방식으로 탐색한다 BFS 탐색 과정? A를 탐색하고 B와 C를 탐색 리스트에 넣는다. 탐색 리스트 = [B, C] 탐색리스트에서 첫 번째 요소 B를 탐색하고 D를 탐색 리스트에 넣는다. = [ C, D ] 탐색리스트에서 첫번째 요소 C를 탐색하고 E를 탐색 리스트에 넣는다. = [ D, E ] 탐색리스트에서 첫번째 요소 D를 탐색하고 탐색 결과가 없어서 넘어간다. = [ E ] 탐색리스트에서 첫번째 요소 E를 탐색하고 탐색 결과가 없어서 넘어간다. = [] BFS의 등장 배경 A에서 E까지 가는 최단 경로를 찾고 싶다면 어..

목표 나머지 연산에 대해 알아보자 나머지 연산을 이용한 문제 풀이 나머지 연산의 등장 배경 31 mod 4는 무엇일까? 너무 쉽다. '3'! 3^31 mod 12는 무엇일까? 😓 계산기를 두드려서라도 구해보자. 3^31는 617673396283947이다. 이 숫자의 mod 12는? 머리의 한계가 온다. 컴퓨터의 도움을 받아보자 3^200 mod 12는 무엇일까? 😒 장난하나 너무 큰 숫자다. 이렇게 큰 나머지 숫자를 어떻게 구 할 수있을까? 나머지 연산 나머지 연산은 3가지 특징을 가진다. 나머지 연산의 특징을 활용하여 문제를 해결해 보자. 3^200 mod 12 = ( 3^200 mod 12 ) * ( 3^200 mod 12 ) mod 12 = ( 3^100 mod 12 ) * ( 3^100 mod 1..

목표 순열에 대해 알아보자 순열을 이용한 문제 풀이 순열 배경 다양한 조합 문제를 해결하기 위해 등장 요소들의 배열과 선택에 대한 방법의 필요성 순열이란? 수학적 관점 - 순서대로 나열 한 것, 나열한 경우의 수 알고리즘 관점 - 서로 다른 요소들을 모든 가능한 방법으로 배열 예를 들면 "ABC"의 경우 가능한 순열은 "ABC, ACB, BAC, BCA, CAB, CBA" 이다. 즉 ABC의 모든 조합, 경우의 수를 알 수 잇음 순열 활용하기 다양한 모든 순서를 고려해보고 싶다면. 순열을 활용해보자. 다양한 모든 순서가 몇번인지가 궁금하면 수학적으로 접근해보자. n P c = n! / (n - c)! n은 총 개수 c는 선택할 요소의 수 !는 팩토리얼 "ABC"의 순열의 수는 3P2 즉 3! / ( 3 ..

알고리즘 직사각형를 좌표를 받아서 배열에 그려주기 dfs 탐색 할때마다 탐색 횟수를 저장 2.에서 저장된 탐색 횟수를 오름차순 후 출력 코드 #include using namespace std; int m, n, k, _x1, _y1, _x2, _y2, cnt; int a[101][101]; const int dx[] = {0, -1, 0, 1}; const int dy[] = {-1, 0, 1, 0}; bool visited[101][101]; vector ret; int dfs(int y, int x){ visited[y][x] = 1; int ret = 1; for(int i = 0 ; i < 4; i++){ int nx = x + dx[i]; int ny = y + dy[i]; if( nx < 0..

문제 이해하기 크로스워드 퍼즐을 출력 하자. 크로스워드 퍼즐은 #.#.이 반복되는 구조이다 알고리즘 홀수 번째 줄에 짝수번째는 '#', 홀수번째는 '.' 짝수 번째 줄에 짝수번째는 '.', 홀수번째는 '#' 크로스워드의 시작점은 왼쪽(L개) + 위(U)개에서부터, M번째까지 코드 #include using namespace std; int m, n, u,l,r,d; string s[11]; char a[100][100]; int main(){ cin >> m >> n >> u >> l >> r >> d; for(int i = 0 ; i > s[i]; } for(int i = 0 ; i < m + u + d ; i++){ for(int j = 0 ; j < n + l + r ;..

문제 이해하기 A를 B번 곱한 수를 C로 나눈 나머지의 값을 어떻게 알 수 있을까? 이때 각 숫자의 크기는 2,147,483,674 라는 매우 큰수이다. 예제 입력으로 이해하기 A :10 B :11 C: 12 10^11 % 12 = 10^5 * 10^5 * 10 % 12 = (10^2 * 10^2 * 10 ) * (10^2 * 10^2 * 10 ) % 12 = ((10*10) * (10*10) * 10 ) * ((10*10) * (10*10) * 10 ) % 12 알고리즘 각 변수의 크기가 크기 때문에 long long 타입으로 선언하자 재귀 함수를 이용해서 문제를 쪼개서 풀수 있다. cal(10, 11) = cal(10, 5) * cal(10, 5) * 10 % 12 B가 홀수인 경우에는 cal(A, ..

문제 이해하기 영어 문자열을 받아서 팰린드롬으로 바꿔야 한다 예제 입력으로 문제 이해하기 입력 : AABB 출력 : ABBA A : 2개 B : 2개 BB ABBA 입력 : AAABB 출력 : ABABA A : 3개 B : 2개 BB ABABA 알고리즘 알파벳의 개수를 찾는다 알파벳의 개수가 홀수인 알파벳이 2개 이상인 경우는 불가능 한 경우이다. 사전순으로 앞서는 것을 출력해야 하므로 Z > A 순으로 데이터를 앞뒤로 붙여준다. 알파벳의 개수가 홀수가 1개 있었던 경우 문자열의 중간에 넣어준다. 코드 #include using namespace std; string s, ret; char mid; int cnt[200], flag; int main(){ cin >> s; // step 1 : 알파벳의 ..

문제 이해하기 0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요. 데이터 추상화 0 ~ 9 까지 들어있는 배열을 만들어 선택되지 않는 값이 무엇인지 발견하도록 하자. let list = [0,1,2,3,4,5,6,7,8,9]; 알고리즘 정수 배열 numbers를 순환하면서 list의 선택된 값은 0을 할당 list 값을 더한 값을 리턴한다. function solution(numbers) { let list = [0,1,2,3,4,5,6,7,8,9] var answer = 0; numbers.forEach( ele => { list[..