C++ 문제풀이/백준 문제풀이 (20) 썸네일형 리스트형 [백준문제풀이] 1260. DFS와 BFS 문제내용 깊이우선 탐색인 DFS와 BFS를 이용해 해결하는 문제 풀이 DFS와 BFS는 알고리즘 문제에서 굉장히 자주나오는 문제이다. 길찾기에 보통 많이 쓰인다. 그리고 내가 약한 부분이라고 생각한다. 풀어도 풀어도 귀신같이 까먹고 어떻게 활용해야할지 모르겠는 문제다. 깊이 우선탐색과 너비우선탐색의 장단점이 있는데 이건 검색을 해보자. 깊이우선탐색 같은경우 스택이나 재귀를 이용하면 풀수 있고 너비우선탐색 같은경우는 큐를 사용하면 된다. 아래는 예시 코드다. #include #include #include #include #include using namespace std; vector graph; vector visit; void dfs(int x) { visit[x] = true; cout m >> v.. [백준문제풀이/정수론 및 조합론] 11051.이항계수 2 문제 내용 전에 풀은 이항계수를 10007로 나눈 나머지를 출력하라. 문제 풀이 이게 무슨 개꿀 문제인가! 전에 풀었던 내용에 % 10007 만 붙이면되는거아님?ㅋㅋ 근데 왜이렇게 정답률이 낮지? 했는데...역시나 생각보다 어려운문제다. #include using namespace std; int main() { ios_base::sync_with_stdio(false); cout.tie(0);cin.tie(0); int n, k; cin >> n >> k; int up = 1; for (int i = 0; i < k; i++) { up *= n; n--; } int down = 1; int down_k = k; for (int i = 0; i < down_k; i++) { down *= k; k--; .. [백준문제풀이 / 정수론 및 조합론] 11050. 이항 계수1 문제 내용 N K 를 입력받고 이항 계수를 구하는 문제 풀이 이..이항계수가 뭔가요!!! 해서 찾아봤더니 https://namu.wiki/w/%EC%9D%B4%ED%95%AD%EC%A0%95%EB%A6%AC 이항정리 - 나무위키 이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 및 삽화 제외) 기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권 namu.wiki 그냥 고등학생때 배운 확률 문제인것 같다. 5, 2 를 입력받았으면 로 되는, 이게 그 다섯개중 두개 선택했을 경우의 수였나..? 아무튼 조합이라는데 이게 국제법으로는 위의 표현으로 더 많이 쓴다고 한다. ( 처음 알았다. 교육과정이 새로 바꼈을지도? ).. [백준문제풀이 / 정수론 및 조합론] 3036.링 문제내용 링들의 반지름을 입력 받고, 첫번째 링이 돌아갔을 때 나머지 링들이 몇바퀴가 도는지 구하는 문제이다. 풀이 나는 문제가 머리에 바로 들어오지 않을 때 예제 입력과 출력을 본다. 그러면 가끔씩 그 문제에 대한 규칙과 해법이 나올때가 있다. 이 문제가 그랬다. 8 4 2 라는 링들의 반지름을 입력받았을 때 나오는 답인 2/1 , 4/1 즉 8/4 와 8/2 라는 것!!! 다른 예제 입력과 결과를 봐도 마찬가지다 ! 12/3 -> 4/1 12/8 -> 3/2 12/4 -> 3/1 가설은 완료되었다. 이제 이걸 어떻게 풀어내느냐인데, 단순히 나누기로 한다면 원하는 형태의 값을 뽑아내기가 어렵다. 왜냐면 컴퓨터는 알아서 약분을 해주지 않기 때문이다. 이걸 어떻게 풀어낼까 했더니 요새 자주 풀었던 최대공약.. [백준 문제풀이/정수론 및 조합론] 2981.검문 문제내용 숫자들을 입력받고, 그 숫자들을 어떤 수 m 으로 나누었을 때 나머지가 같게 나오는 m 들을 모두 구하는 문제이다. 풀이 정답률이 20%일 정도로 낮은 어려운 문제이다. 처음엔 숫자들을 입력받고 , 그 숫자들의 최솟값까지 반복해서 모든 숫자들을 검사하는 방법으로 했는데 당연히 시간 초과가 뜬다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector v; for (int i = 0; i > temp; v.push_back(temp); } .. [백준 문제풀이 / 동적계획법] 1912.연속합 문제 내용 숫자를 입력받고 , 연속 된 숫자의 합이 제일 큰 수를 찾는 문제. 문제 풀이 이번 문제.. 내가 생각해도 좀 잘풀었다 싶다. 왠일로 빨리 좀 떠올랐다. 일단 처음 생각은 입력받은 숫자들을 저장하고, 또 각 숫자마다 반복하며 최대값을 구해야 하나 싶었는데, 아무리 생각해도 시간복잡도가 너무 높아보였다. 그리고 구현하는 난이도도 은근 까다롭고.. 결국 연속된 숫자의 합이 큰 걸 구해야 하는 거니, 따로 숫자들을 저장 할 필요 없이 숫자가 입력받을 때 마다 합을 구해주고 그 때마다 최대값 계산을 같이 해주면 되지 않을까? 그렇게 해서 처음엔 연속 된 숫자에서 음수가 포함되면 무조건 최대값이 될 수 없다 생각하여 풀었으나 몇몇 케이스 , 3 -1 3 4 같은 상황에 연속 됐지만 적은 음수값을 가진 .. [백준 문제풀이 / 동적계획법 1] 24416. 알고리즘 수업 - 피보나치 수 1 문제 내용 피보나치 수열문제를 재귀로 풀었을 때, 동적프로그래밍으로 풀었을 때 실행 횟수의 차이를 구하는 문제. 문제 풀이 사실 풀이는 없다. 수도 코드를 C++ 스타일로 바꿔서 실행횟수를 출력해주기만 하면 된다. 하지만 올리는 이유는 피보나치 함수의 재귀와 동적 프로그래밍의 어떻게 동작 하는지 차이를 직관적으로 볼 수 있기 때문이다. #include using namespace std; int f[41]; int playCnt1 = 1; int playCnt2 = 0; int fib(int n) { if (n == 1 || n == 2) { return 1; //# 코드1 } else { playCnt1++; return (fib(n - 1) + fib(n - 2)); } } int fibonacci(.. [백준 문제풀이 / 정수론 및 조합론 ] 1934. 최소공배수 문제 내용 문제 풀이 이전글과 풀이는 같다. 최대공약수를 구하고 a x b = G x L 을 이용한다. 최대공약수를 구할 때 쓰는 방법 : 유클리드 알고리즘, 호제법 https://terms.naver.com/entry.naver?docId=3338353&cid=47324&categoryId=47324 호제법 유클리드 호제법(互除法)은 두 개 이상의 양의 정수의 최대공약수를 구하는 방법으로, 유클리드 알고리즘(Euclidean algorithm)이라고 하기도 한다. 호제법이라는 이름은, 주어진 두 정수의 최대공약 terms.naver.com #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cou.. 이전 1 2 3 다음
