Algorithm

백준 1629 곱셈 c++ // 재귀함수

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 1. 최대한 예시에서 일반식을 도출하라. ex) a^4%c = a^2%c * a^2 %c -> a^b%c = a^b%c * a^b %c ex) a^5%c = a^2%c * a^2 %c * a^1 %c -> a^b%c = a^b%c * a^b %c * a^1 %c 2. (공통부분을) 먼저계산 후 리턴하면된다. #include using namespace std; int a, b, c; using ll = long long; //함수정의 : a^b를 c로나눈 나머지..

백준 1074 Z C++ // 재귀

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 1. 왜 재귀로 푸나? 새로운 값을 구할때 이전의 값을 활용한다. 2. 함수정의 3. 기저사례 4. 재귀식 #include using namespace std; //2^n * 2^n 배열에서 , (r,c) 방문순서 반환 int func(int n, int r, int c) { //기저사례 : 1x1 칸의 번호는 0이다. if (n == 0) return 0; int half = 1 = h..

프로그래머스 하노이의 탑 c++ // 재귀함수

https://school.programmers.co.kr/learn/courses/30/lessons/12946# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 특징 : n==1일때만 answer에 푸쉬함. 나머지는 추상적으로 정의함. 기둥번호 : 1, 2, 3번 기둥번호 : a번, 6-a-b번, b번 할일(재귀식) : 1. a에서 6-a-b기둥으로 n-1개옮기기 2. a에서 b로 1개 옮기기 3.6-a-b에서 b로 n-1개 옮기기 n==1일때만 base condition처리. 임의(k개)일때는 재귀적으로 처리후 도미노가 쓰러지듯 알아서 처리된다. #i..

프로그래머스 섬 연결하기 c++ // 크러스칼 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 특이한 부분 재귀함수 //부모노드찾기 int get_parent(int node){ if(parent[node]==node) return node; return parent[node]=get_parent(parent[node]); } 2. 합집합 //같은집합으로 만드는함수 void union_parent(int node1, int node2){ int p1=get_parent(node1); ..

프로그래머스 네트워크 c++ // 인접행렬 dfs

https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 의사코드 for(nodes) if(visit) continue; dfs(node) answer++ DFS: 방문처리 for(연결된노드들) if(방문) continue if(연결되었음) dfs(there) 2. 전체코드 #include using namespace std; int answer; int v[204]; int N; //해당 노드(컴퓨터)dfs void dfs(int& n, vect..

프로그래머스 타겟넘버 c++ // dfs

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 의사코드 최악 : 2^20 == 1048576 < 1억 이므로 완탐가능하다. 모든넘버에대해 -, + 경우를 가정하고 dfs로 완탐한다. 2. 전체코드 #include #include using namespace std; int answer; void dfs(vector& numbers, int& target, int idx, int result){ if(idx==num..

백준 1926 c++ // bfs, 갯수카운팅

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net * 의사코드 큐에 넣을때마다(이동가능 일때) cnt 변수 1씩증가 => 1의 갯수카운팅 * 전체코드 #include using namespace std; int n, m, y, x, ny, nx, ret1,ret2; int a[504][504], v[504][504]; int dy[] = {1,0,-1,0}; int dx[] = {0,1,0,-1}; void bfs(int y, int x) { //co..

백준 2504 c++ // 스택응용

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net *의사코드 *요약 이해가잘안갔던 문제이다. ( ( ) 이면 num : 2 4 2 이고 sum에 4를 더해준다. 첫닫는과호를 만났을때 바깥괄호의 영향까지 포함해서 계산을 마치고 sum을 갱신하고, 이후 좌측괄호의 영향이 안가도록 num을 나눠준다 그리디 분류에도 속할것 같다. *전체코드 // Authored by : std-freejia // Co-authored by : Baaaaaaaaaa..