백준108

• 

  [백준 6593번 / C++ ] 상범 빌딩 BFS 문제이다 . 코드가 상당히 길다. #접근 방법 상범이가 빌딩에 갇히고 말았다. 왜 갇혔는지 모르겠다. 평범한 BFS 문제보다 조금 까다로운 문제이다. 왜냐하면 평소에 풀던 문제는 상하좌우만 살피면 되는데 이 문제는 윗층과 아랫층도 비교해줘야한다. 근데 그것 말고는 큰 차이가 없다. 단지, 층(layer)을 나타내는 값과 이동할 때 추가되는 누적시간을 저장하는 큐를 하나 더 생성했을 뿐이다. 일반적인 BFS문제와 동일하지만 층의 범위까지 고려해서 풀어보자. #include #include #include #include #include using namespace std; int l, m, n; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; vector.. 백준/DFS BFS 2022. 3. 21.

• 

  [백준 14888번 / C++] 연산자 끼워넣기 완전탐색으로 dfs를 활용해서 풀면된다. +, -, * , / 연산자를 차례대로 넣어보는 것이다. 예를 들어, 1 3 5 라는 숫자가 주어졌고 각 연산자를 하나씩 대입해보자. 1 + 3 = 4 1 - 3 = -2 1 * 3 = 3 1 / 3 = 0 그리고 연산값이 4부터 다시 dfs를 호출해서 연산하면 된다. 4 + 5 = 9 4 - 5 = -1 4 * 3 = 12 4 / 5 = 0 이후에 연산값이 -2 부터 다시 dfs 를 호출해서 연산한다. 이렇게 dfs를 활용해서 완전탐색으로 풀면된다. #include #include #include using namespace std; #define INF 987654321; bool check[123456 * 2+1]; vector v; int result_ma.. 백준/완전 탐색 2022. 3. 17.

• 

  [백준 4948번 / C++] 베르트랑 공준 대표적인 소수 2, 3, 5, 7 이 있는데 각 소수의 배수는 모두 소수가 아니다. 예를 들어, 소수 2의 배수는 4 6 8 ..... 22222222가 있는데 모두 2로 나누어 떨어지니까 소수가 아니다 소수 3의 배수는 6 9 12 ....33333333이 있는데 모두 3으로 나누어 떨어지니가 소수가 아니다. 즉, 소수를 만나면 해당 소수의 배수를 모두 소수가 아니라고 체크를 해준다. check = true; #접근방법 1. 소수인지 아닌지 판별하는 check라는 배열을 123456*2 만큼 생성한다. 2. 2부터 1234567까지 반복문을 돌리면서 소수를 만나면 해당 소수의 배수들을 check에 true로 설정 3. 이후 입력값 n을 받았을 때 n+1 부터 2*n 까지 check 배열에 false로 .. 백준/구현 2022. 3. 17.

• 

  [백준 9934번 / C++] 완전 이진 트리 dfs 문제이다. * 중위 순회의 흐름 차순은 L - Root - R 순이다. #접근방법 답을 저장할 이차원 벡터와 데이터를 저장할 일차원 벡터 생성. 시작 포인터와 끝 포인터를 지정하여 그 중간점을 매개변수로 전달하여 왼쪽 자식 노드의 끝까지 들어간다. level 이 입력받은 깊이의 수와 동일하다면 return. 해당 레벨에 위치의 이차원벡터에 현재 담고있는 데이터의 값을 담아준다. 우측 자식 노드로 재귀함수를 호출한다. #include #include using namespace std; int n; vector v; void dfs(int s, int e, int level, vector& data) { if (level==n) return; int mid = (s + e) / 2; dfs(s, m.. 백준/DFS BFS 2022. 3. 17.

• 

  [백준 11404번 / C++ / 플로이드-와샬] 플로이드 이 문제는 플로이드 와샬 알고리즘을 활용해서 풀면 된다. 플로이드 와샬 알고리즘을 모르는 분은 아래 링크에 들어가서 개념을 보고 오길 권한다. 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com #접근방법 info 이차원 배열에 큰 수로 모두 초기화 한다. 도시 a에서 a로 가는 정보는 0으로 초기화 한다. 도시 a에서 도시 b로 가는 비용을 info[a][b]에 담는다. 도시 a에서 도시 b로 가는 비용과 도시 a에서 도시 k를 거쳤다가 도시 b로 가는 비용을 비교해서 작은값을 info[a][b]에 담는다. 출력 #include #include using n.. 백준/그래프 2022. 3. 16.

• 

  [백준 15486번 / C++] 퇴사 2 dp를 활용한 문제이다 #접근방법 본인이 생성한 dp 배열의 의미는 해당 인덱스 값에 받을 수 있는 최댓값이다. 즉, dp[3] = 4 라는 것은 3일에 받을 수 있는 최댓값이다. 이 문제의 핵심은 1일에 상담을 시작하면 3일이 걸리니 받을 수 있는 금액은 4일에 받을 수 있다는 것이다. 다시 말해서, 1일에는 아직 금액을 받지 못하고 1일+3일 후에야 P1의 비용을 받을 수 있다. 즉, dp[1] 은 0이고 dp[4] = 10 이 되는 것이다. dp[2] = 0 이고, dp[7] = 20 dp[3] = 0 이고, dp[4] = 10이다. 이때, dp[4] 는 day가 1일일 때 dp[day(1일)+T1(3일)] = 10 라는 값이 세팅 되어 있으므로, dp[i+Ti] = max(dp[i+Ti], 현재까.. 백준/DP 2022. 3. 16.

• 

  [백준 11722번 / C++] 가장 긴 감소하는 부분 수열 dp 배열을 활용해서 풀면된다. #접근방법 본인은 증가수열이 매우 익숙해서 reverse 함수를 통해서 벡터의 순서를 바꿔주고 LIS(최장증가수열)를 통해 문제를 풀었다. dp 배열 1로 초기화, v 배열 데이터값 저장. v 배열 인덱스 1부터 n-1까지 돌면서 dp를 확인한다. 인덱스 i에 위치한 v 벡터의 데이터값과 인덱스값이 j (for (j.. 백준/DP 2022. 3. 15.

• 

  [백준 2573번 / C++] 빙산 이 문제는 bfs를 활용해서 풀면 된다. #접근방법 bfs를 적용한 문제를 얼마나 많이 풀어봤냐에 따라서 해당 문제가 쉽게 느껴질 수 있고 어렵게 느껴질 수 있을거라고 생각한다. 빙산의 크기 map에 담고 map크기 만큼 temp라는 이차원배열을 생성한다. ( 갱신된 내용 temp에 저장.) 빙산 주변에 인접한 0의 개수(바다) 만큼 map의 값에서 빼준 후 결과 값을 temp 에 넣어준다. temp 이차원 배열에는 갱신된 내용이 담겨져 있고 해당 데이터를 토대로 덩어리를 계산해준다. 즉, bfs를 호출한 개수가 덩어리 개수이다. ( bfs는 서로 인접한 데이터에 값이 있으면 퍼지면서 탐색 하기 때문) 덩어리의 개수가 2개 이상이 아니면 다시 2번부터 반복한다. #include #include #incl.. 백준/DFS BFS 2022. 3. 14.

• 

  [백준 16953번 / C++] A → B dfs 문제이다 #접근방법 현재 값 current 변수에서 1. 곱하기 2를 해서 dfs를 호출. 2. 곱하기 10을 한 후 +1 을 dfs로 호출 이 두가지 경우를 dfs 함수 안에 두고 current 값이 B와 동일하다면 cnt값이 큰 것을 고른다. 즉, 위의 조건에서 1번을 통해 B값을 도출할 수 있고 2번을 통해 B값을 도출할 수 있으니 재귀호출한 횟수를 세어주는 cnt값을 비교해서 작은 값을 answer값에 저장시켜준다. #include #include using namespace std; long long a, b; long long answer = 987654321; void dfs(long long cur, long long cnt) { if (cur == b) { answer = min(.. 백준/DFS BFS 2022. 3. 14.

• 

  [백준 14719번 / C++] 빗물 투 포인터를 활용해서 풀었다. 간단하게 그림을 그려서 설명하겠다. 위의 그림처럼 Start 인덱스에서 물이 채워지는 양은 Start 인덱스 기준으로 왼쪽 블락과 오른쪽 블락을 확인해야 한다. 즉, 현재 블럭의 높이보다 큰 값중에 왼쪽에서의 블락의 최댓값과 오른쪽에서의 블락의 최댓값을 구해서 빼주면 되는것이다. result += min(L_max, R_max) - v[Start] * 물이 넘치게 되면 작은 블락을 넘기기 때문에 양쪽 블락 중 작은 값을 구한다. #include #include #include using namespace std; int main() { int m, n; cin >> m >> n; vector v; for (int i = 0; i >.. 백준/증가수열 & 투포인터 2022. 3. 10.