DOTY

오늘 처음 알게 된 DP 에서 중요한거 같은 Memoization!!! 메모이제이션이야 ....? 아니면 메모아이제이션이야....? 쩃든,,,, 코드 두개를 비교 하면서 설명! ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ fibo(int n) { if(n == 1 || n == 2) return 1; return (fibo(n-1) + ribo(n-2)); } fibo(int n) { if(Memoization[n] == 0) Memoization[n] = fibo(n-1) + fibo(n-2); return Memoization[n]; } 처음에는 무슨 차이지... 싶었다. 코드 1은 그냥 한거고, 코드 2는 배열을 사용한것이다. 그런데 잘 생각해보면 ..

소수를 찾는 알고리즘이다. 이렇게 빠를줄은 생각도 안하고 있었는데.... 엄청 빠르다 int prime_Num(int n) { int cnt = 0; vector check(n+1, 1); for(int i = 2; i

https://programmers.co.kr/learn/courses/30/lessons/42588?language=cpp ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ #include #include using namespace std; vector solution(vector heights) { vector answer; for(int i = 0; i = 0; j--) { if(heights[j] > heights[i]){ answer.push_back(j+1); break; } if(j == 0) { answer.push_back(0); } } } return answer; ..

https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ #include #include using namespace std; vector solution(vector prices) { vector answer; for(int i = 0; i < prices.size(); i++) {..

https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 �� programmers.co.kr ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ #include #include using namespace std; vector solution(int brown, int yellow) { int col, row; for(int i = 1; i

처음으로 풀어본 골드4(sloved.ac)문제. 기분이 좋다 ㅎㅎㅎㅎㅎ 느낌상 이건 BFS로 풀어야 할 것 같았다. https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net #include #include #include using namespace std; char map[101][101]; bool check[101][101] = {0, }; int N, H; int cnt = 0; void bfs(int x, int y) { queue q..

이번에는 BFS에 대해서 공부하기 위해 뱀과 사다리 게임을 풀어봤다. (Solved.ac기준 실버 3) 처음에는 어떤 방식으로 풀어야 할지 역시 막막했음 ㅠ 그런데 숨바꼭질(1697)을 풀어보니 대충 어떤 느낌인지 감 잡을 수 있었다. 간단 요약을 하자면 큐에 넣고 큐 사이즈만큼 for문 돌리고!!!! 큐에서 빼고!!!! 계속 큐에 넣고!!!!! https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net #i..

DFS를 공부했으니 DFS를 써보고 싶었다. 근데 역시나 여러운것......ㅎㅎ.... 그냥 일단 해보자는 식으로 했다. ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 보통 예제 입출력을 보고 종이에다 끄적여보는데 정말 .....ㅜㅜㅜㅜㅜㅜ 그동안 너무 대충 공부한거 같았다 ㅜㅜ (반성......) 일단 첫번째 코드는 다음과 같다. (15649번) #include #define MAX 9 using namespace std; int n,m; int arr[MAX] = {0,}; bool visited[MAX] = {0,}; void dfs(int cnt) { if(cnt == m) { for(int i = 0; i < m; i++) cout m; dfs(0); } 1부..

이건 BFS 와는 다르게 깊이 우선 탐색이다. BFS라면 1, 2, 3.... 순이겠지만, DFS는 1, 2, 4..... 순이다. 코드는 다음과 같다. void dfs(int num) { if(check[num]) return; check[num] = true; cout

BFS는 너비 우선 탐색이다. 이걸 위해서 직접 만들었다. 역시 대단해 ㅎㅎㅎㅎㅎㅎ 본론으로 BFS는 너비 탐색으로 말 그대로 넓게 퍼져가면서 탐색한다 생각하면 된다. 과정은 간단하다. 큐(Queue)에 하나하나 넣어서 대기 시키는 느낌이랄까... 코드는 다음과 같다. void bfs(int num) { queue q; q.push(num); check[num] = true; int x, y; while(!q.empty()) { x = q.front(); q.pop(); cout