[목차]310 [백준 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. [백준 11048번 / C++] 이동하기 dp와 dfs를 활용한 문제이다. 이와 비슷한 문제를 아래에 dp 카테고리에 추가한 적이 있어서 이번엔 dfs 카테고리에 집어넣겠다. = n || ny = m)continue; res=max(dfs(ny, nx)+map[y][x],res); } return res; } int main() { cin >> m >> n; for (int i = 0; i > map[i][j]; cost[i][j] = -1; } } cout 백준/DFS BFS 2022. 3. 10. [백준 11057 / C++] 오르막 수 dp 배열을 이용해서 풀면된다. [dp이차원 배열 ] 길이/끝자릿수 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 2 1 2 3 4 5 6 7 8 9 10 3 1 3 6 10 15 21 28 36 45 55 예를 한번 들어보자. 만약 길이가 3인 오르막수를 구하라고 하면 어떻게 체크를 해야할까? 먼저 위의 표를 보면 길이를 나타내는 컬럼과 1~9까지의 자릿 수의 컬럼을 만들었다. 각 길이의 해당 끝자릿 수의 경우의 수는 현재 길이의 이전 끝자릿 수의 경우의 수 + 이전 길이의 같은 끝자릿수의 경우의 수이다. 즉, 위의 표에서 길이가 2이고 끝자릿 수가 1인 값은 2 이고, (01,11) 길이가 3이고 끝자릿 수가 0인 값은 1 라는 것을 알 수 있다. (000) 그렇다면 길이.. 백준/DP 2022. 3. 10. [백준 11403번 / C++/ 플로이드-와샬] 경로 찾기 플로이드-와샬 문제이다. 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com 플로이드 와샬 알고리즘을 모르시는 분은 위의 링크에 들어가서 개념을 숙지하고 오길 추천한다. #접근 방법 노드 1에서 노드 3으로 연결된 길이 있는지 물어봤다면? 노드 1에서 노드 2를 거쳤다가 노드 3으로 가는 길이 있는지. 노드 1에서 노드 4를 거쳤다가 노드 3으로 가는 길이 있는지. 이러한 방식으로 확인해보면서 그래프 값을 갱신해주는 것이다. #include using namespace std; int g[101][101]; int main() { int n; cin >> n;.. 백준/그래프 2022. 3. 10. [백준 4811번 / C++] 알약 dp배열을 생성하여 탑다운 방식으로 접근하면 된다. 탑다운 방식이란 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식 #접근방법 Test Case를 적당한 숫자를 예를 들어서 풀어보는 것을 연습해야한다. 본인은 숫자 3을 예를 들어서 풀어보았다. WWWHHH WWHWHH WWHHWH WHWWHH WHWHWH 이렇게 총 5가지가 나오는 것을 알 수 있다. DP를 어떻게 활용하냐? DFS를 수행할 때 두가지로 나뉘어서 재귀호출을 한다. 1. W인 알약을 집었을 때 W의 개수를 -1 해주고 H의 개수를 +1 해준다. 2. H인 알약을 집었을 때 H의 개수만 -1 해준다. 이 두가지 재귀 호출을 해서 받아온 리턴값을 더해서 DP 배열에 저장해준다. 리턴해주는 조건문은 H의 개수가 -1이 되었을 때. (경우의 .. 백준/DP 2022. 3. 8. [백준 16194 / C++] 카드 구매하기 2 [백준 11052번 / C++] 카드 구매하기 DP를 활용한 문제이다. #접근방법 예를 들어 카드 3개를 사려고 한다. DP 배열의 인덱스 번호의 의미는 카드의 개수를 나타내고 카드의 개수만큼 살 수 있는 최댓값을 가지고 있다. 그렇다면 dp[3] baebalja.tistory.com 위의 문제와 똑같은 문제이지만 최솟값을 찾는 문제이다. 다른점은 dp의 초기 세팅을 cost로 해주는 점과 max 알고리즘 대신에 min으로 바꿔줬다. 11052번 문제를 풀지 않았다면 위의 링크를 들어가서 풀고나서 이 문제를 풀기를 추천한다. #include #include #include using namespace std; int main() { int n; cin >> n; vector cost(n + 1); vec.. 백준/DP 2022. 3. 8. [백준 11052번 / C++] 카드 구매하기 DP를 활용한 문제이다. #접근방법 예를 들어 카드 3개를 사려고 한다. DP 배열의 인덱스 번호의 의미는 카드의 개수를 나타내고 카드의 개수만큼 살 수 있는 최댓값을 가지고 있다. 그렇다면 dp[3] 에는 카드 3개를 살 수 있는 최대 비용이라고 이해하면 된다. 1. dp[2] (두개를 샀을 때 최댓값) + cost[1] (카드 한장 묶음 비용) 2. dp[1] (한개를 샀을 때 최댓값) + cost[2] (카드 두장 묶음 비용) 3. dp[0] (0개를 샀을 때 최댓값) + cost[3] (카드 세장 묶음 비용) 즉 이 3가지의 최댓값을 dp[3]에 갱신해주면 된다. 점화식은 아래와 같다. " DP[i] =max( DP[i] , (DP[i-j] + cost[j])) " #include #include.. 백준/DP 2022. 3. 8. [운영체제 3편] 뮤텍스가 무엇인가 지난 시간에 스레드에 대해서 알아봤었죠?! 그리고 멀티 스레드 환경에서는 서로 공유하는 영역이 있기 때문에 같은 데이터에 접근하는 경우 문제가 발생할 수 있다고 설명드렸어요~ 그래서 제가 "동기화 작업"이 필요하다고 했었죠?? 자! 그럼 동기화가 뭔데?! 한번 들어가봅시다 :) 저번 시간에 예시를 들면서 설명 잠깐 했어요 스레드 "배씨"가 공유자원인 도화지에 사자의 얼굴을 그리다가 다른 스레드 "이씨"가 들어와서 호랑이로 바꿨잖아요?? 그렇게 된다면 스레드 "배씨" 가 계획했던 목표가 바뀌면서 나아갈 수 없는 상황이 되겠죠. 이처럼 프로세스/스레드는 같은 데이터에 접근해야하는 경우가 있어요! 이때 일정한 규칙없이 데이터 수정을 허용하게 된다면 데이터의 신뢰성이 사라지겠죠?? 그렇기때문에 데이터의 일관성을.. 남이 읽는 CS/운영체제 2022. 3. 8. [백준 2631번 / C++] 줄세우기 LIS 문제이다. 수열이 만약 "3, 5, 8, 10, 1, 4" 으로 주어졌다면 직관적으로 1과 4를 앞에다가 놓으면 되는거 아닌가? 라는 생각이 들면 된다. 그렇다면 그 기준이 뭘까? 위의 수열에서 보면 3 1 > n; vector v(n+1); for (int i = 1.. 백준/증가수열 & 투포인터 2022. 3. 7. [운영체제 2편] 스레드란 무엇인가 안녕하세요! 운영체제의 두번째 게시글이에요ㅎㅎ :) 첫번째 게시글에서 프로세스에 대한 기본적인 개념에 대해서 설명을 드렸어요 저번시간에 언급드렸듯이 오늘은 "스레드"에 대해서 배워볼까 합니다!! 스레...드..? 뭘 쓰래..? ㅎㅎ 자! 여러분들이 Zoom 이라는 화상회의 프로그램을 실행시키고 유튜브를 켜서 유튜브 영상을 보고있다고 가정할게요! 저번 시간에 설명했던 프로세스 기억나시나요?! 그쵸! Zoom이 하나의 프로세스이고, 유튜브도 하나의 프로세스가 되겠죠?! 그렇다면 Zoom을 한번 살펴볼게요~ Zoom에서 상대가 공유한 화면만 볼 수 있나요? 아니죠! 다른 사람들의 얼굴과 자신의 얼굴이 보여지는 창도 있을거에요! 그리고 서로 소통을 할 수 있는 채팅창까지 활용할 수 있죠. 이처럼 하나의 프로세스.. 남이 읽는 CS/운영체제 2022. 3. 5. 이전 1 ··· 14 15 16 17 18 19 20 ··· 31 다음 반응형