목록PS (52)
컴공댕이 공부일지
[ C++/cpp ] 백준 (9095 1, 2, 3 더하기) ⭐DP
백준 9095번 1, 2, 3 더하기(실버 3) 문제링크 https://www.acmicpc.net/problem/9095 (정답 코드)#include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, t; int dp[12]; dp[1]=1; dp[2]=2; dp[3]=4; cin >> t; while(t--) { cin >> n; for(int i=4; i 📖 풀이 이전까지의 값들이 뭔가 메모리제이션되면서 중첩되어 최종 답을 구하게 되는 느낌 == 전형적인 dp 문제다. i-1, i-2, i-3의 값들에 +1, ..
백준 1463번 1로 만들기(실버 3) 문제링크 https://www.acmicpc.net/problem/1463 1️⃣ BFS로 풀기 → N부터 1까지 순회. 3가지 연산 각각을 큐에 넣고 1이 되면 종료.#include #include #include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); queue q; vector vis(1000001, -1); // 방문여부 체크 int n; cin >> n; q.push(n); vis[n] = 0; // BFS while(!q.empty()) { ..
[ C++/cpp ] 백준 (2630 색종이 만들이) ⭐재귀
BOJ 2630번 색종이 만들이(실버 2) 문제링크 https://www.acmicpc.net/problem/2630 (정답 코드)#include using namespace std;int n, white, blue;int map[128][128];bool isSameColor(int x, int y, int size, int color) { for(int i=x; i> n; for(int i=0; i> map[i][j]; } } func(0, 0, n); cout 📖 풀이 요약 만약 아직 색종이가 완성되지 않았다면 또 4등분하고, 그래도 아직 색이 섞여있다면 또 4등분하고..이런식으로 재귀로 풀어야하는 문제이다. 재귀의 틀만 생각해낸다면 구현..
[실전 알고리즘] 0x0C강 | 백트래킹 (Backtracking) - 이론 & 예제문제 풀이 / next_permutation 함수의 활용
🔎 백트래킹이란? 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘가능한 모든 선택지를 다 플레이해보는 것 ! 이렇게만 보면 브루트포스랑 뭐가 다른가 싶은데,브루트포스는 별도의 조건을 고려하지 않고, 단순히 모~든 조합을 싹 다 고려한다. 반면, 백트래킹은 가능한 경로만을 탐색하며,특정 조건을 만족하지 않는 경우는 더 이상 진행하지 않고 이전으로 BACK한다. 이번 글에서는 바킹독 선생님의 강의를 기반으로, 백트래킹 연습 문제를 풀이해볼 것이다.BFS 문제와 비슷하게, 기본적인 코드 형태만 익혀두면 응용할 부분은 잘 없는 유형이라 할 만 할거라고 ..! 📝 백트레킹 예제 (1) - N과 M (1) 백준 15649번 N과 M (1) (https://www.acmicpc.ne..
[실전 알고리즘] 0x0B강 | 재귀 (Recursion) - 이론부터 예제 문제풀이까지, 재귀 문제의 구조 완벽 익히기 😎
🔎 재귀(Recursion)란? 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘.재귀가 낯설고 어렵게 느껴지는 이유는 우리가 기존에 생각하던 "절차지향적 사고"를 탈피해야하기 때문. 절차 지향적 사고 vs 귀납적 사고도미노로 예시를 들면, - 절차 지향적 사고1번 도미노, 2번째 도미노, 3번째 도미노 ... 이렇게 순차적으로 쓰러져서 모든 도미노가 쓰러진다 ! => (각 단계가 순차적으로 실행) - 귀납적 사고- 1번 도미노가 쓰러진다.- k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.=> 모든 도미노가 쓰러진다 ! 는 결론에 도달. 이번 글에서는 바킹독 선생님의 강의를 기반으로, 재귀의 기본 개념을 정리하고, 예제 문제를 풀이해볼 것이다. 📝 재귀 함수의 조건특정 입력..
[실전 알고리즘] 0x0A강 | 깊이 우선 탐색 (DFS) - 스택으로 DFS 구현하기 / DFS와 BFS의 차이?
🔎 DFS란? BFS와 DFS를 쉽게 설명하자면,가까운 이웃부터 좀좀따리 파면서 탐색. 한 단계씩 나아가며 가까운 정점들을 다 방문함 - 큐로 구현드라마 정주행하듯 끝까지 깊이 탐색. 더이상 못 파면 이전으로 돌아가 다른 경로 탐색. - 스택과 재귀로 구현 BFS: 가까운 것부터 차례대로 탐색 → 큐 사용 → 최단 경로 탐색에 유리DFS: 깊게 탐색 후 되돌아감 → 스택 또는 재귀 사용 → 경로를 깊이 있게 탐색 지난 글에서 BFS를 다루며 언급했던 내용이다. DFS는 BFS와 크게 다를 것 없지만, 스택을 사용해 구현한다. BFS는 FIFO인 큐를 사용해서, 인접한 노드들을 우선적으로 처리하며 점차 퍼져나갔다면, DFS는 LIFO인 스택을 사용하기에 가장 최근에 들어갔던 마지막 노드가 우선 처리되므..
[실전 알고리즘] 0x09강 | 너비 우선 탐색 (BFS) - 응용 문제 유형별로 풀어보기 📝
🔎 BFS란? BFS와 DFS를 쉽게 설명하자면, 가까운 이웃부터 좀좀따리 파면서 탐색. 한 단계씩 나아가며 가까운 정점들을 다 방문함 - 큐로 구현드라마 정주행하듯 끝까지 깊이 탐색. 더이상 못 파면 이전으로 돌아가 다른 경로 탐색. - 스택과 재귀로 구현 BFS: 가까운 것부터 차례대로 탐색 → 큐 사용 → 최단 경로 탐색에 유리DFS: 깊게 탐색 후 되돌아감 → 스택 또는 재귀 사용 → 경로를 깊이 있게 탐색 이번 글에서는 바킹독 선생님의 강의를 기반으로, BFS의 문제 유형 여러 가지를 풀이해볼 것이다. 📝 BFS 기초 예제 백준 1926번 그림 - 영역 탐색. 2차원 배열에서 가장 넓은 영역 면적 찾기. BFS의 기본 예제 !https://www.acmicpc.net/probl..
[실전 알고리즘] 0x01강 - 🔎 정수 및 실수 자료형의 특징 / 2의 보수법
[ 정수 자료형 ]short (2byte) int (4byte) - 최댓값 21억 long long (8byte) - 최대 19자리 (2^63-1)[ 실수 자료형 ]float (4byte) : 1 + 8 + 32bitdouble (8byte) : 1 + 11 + 52bit부호 + 지수(exponent) + 유효숫자(fraction) 필드로 실수를 저장함 ex) -6.75의 이진수 표현 부호 : 1 정수 : 6 = 110 소수 : .75 = 0.5 + 0.25 = .11 -> 110.11 -> 1.1011 * 2^2 [ ⭐ 실수 자료형의 특징 ]1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다..컴퓨터는 실수를 근사값으로 저장함 ! => 실수가 필요하다면 가능한 오차 범위가 훨씬 더 ..