Algorithm66 [백준] 1764 듣보잡 백준 10815번 문제의 문자열버전이다. 풀이가 비슷하므로 아래 문제풀이를 참고해도 될거같다. https://everydayyy.tistory.com/44 [백준] 10815 숫자카드 이중 for문을 사용할 시 500000*500000의 엄청난 크기가 나와서 이진탐색으로 풀어야 한다. 간단한 이진탐색이기 때문에 큰 어려움은 없었지만 까먹어서 구현하는데 오래걸렸다,, *********까먹지 않기 everydayyy.tistory.com 이진탐색으로 해당문자열이 있는지 탐색하고, 있다면 answer 벡터에 저장해서, 마지막에 정렬하여 출력하면 끝!! 숫자에 이어서 영문자열의 경우 또한 STL의 std::sort()함수로 처리가 가능하다는 것을 보여준 문제같다. void sort(T start, T end, .. 2022. 4. 19. [백준] 10815 숫자카드 이중 for문을 사용할 시 500000*500000의 엄청난 크기가 나와서 이진탐색으로 풀어야 한다. 간단한 이진탐색이기 때문에 큰 어려움은 없었지만 까먹어서 구현하는데 오래걸렸다,, *********까먹지 않기 위해 개인적으로 정리할 예정!!!***********8 이외에도 시간초과가 계속 뜨는 바람에 계속 수정을 했다.. 수정한내용은 다음과 같다. 1. 입/출력에 시간을 많이 잡아먹어서 ios::sync_with_stdio(false); cin.tie(0); 추가 2. 기존에 쓰던 벡터에서 일반배열로 수정 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40.. 2022. 4. 19. [백준] 14889 스타트와 링크 dfs(백트래킹)을 이용해서 만들 수 있는 모든 조합의 경우를 다 따지는 문제이다. 처음엔 조합을 이용한 브루트포스이겠거니 생각했지만 조합을 어떻게 구현하는지 생각이 안났다.. 해서 dfs을 가지고 순열 및 조합을 구현하는 코드를 공부 한 후에 다시 문제를 풀었다. stl라이브러리 중 next_permutation으로 구할 수 있었지만, 시간복잡도가 너무 크기 때문에 직접 재귀로 구현하는 것이 낫다고 한다. 아래사이트를 참고해서 공부했다. https://paris-in-the-rain.tistory.com/35 순열, 조합 알고리즘 - DFS로 구하기(백트래킹), C++, Python 순열, 조합은 정말정말 많이 나오는데 cpp의 stl 라이브러리 중 next_permutation으로 구할 수 있다. 하.. 2022. 2. 24. [백준] 13460 구슬 탈출 2 생각하는 과정 1. R과 B가 동시에 한쪽으로 완전히 이동해야 한다. -> R과 B의 좌표와 기울인 횟수를 담은 Queue를 하나 만들자. -> 좌표의 4방향을 탐색하는 for문에서 방향 i를 공유하여 R과 B를 이동시킬 수 있을 때까지 이동시킨다. 2. 한쪽으로 기울였을 때 R과 B가 겹치는 상황이 발생한다. -> R과 B가 움직인 거리를 비교해서 움직인거리가 적은 구슬의 좌표를 증가(혹은 감소)시킨다. 3. 2번을 잘 해결했다면 방문체크를 한 후에(아직 방문을 안했다면) next좌표를 push해준다. (이때 count증가) 이렇게 되면 R,B를 R이 0을 찾을때까지 한쪽으로 계속 기울여 가면서 최소의 count를 얻어낸다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16.. 2022. 2. 22. [백준] 11055 가장 큰 증가 부분수열 [가장 긴 증가하는 부분수열] 문제와 매우 비슷한(거의 같음) 유형이다. https://www.acmicpc.net/problem/11053 가장 긴 증가하는 부분수열을 찾을 때에는 앞의 원소보다 지금원소가 크다면 길이를 1씩 더해가면서 풀었다면, 가장 큰 증가 부분수열을 찾을 때에는 합을 구해가면서 찾는다. 풀이 예시 {1, 10, 2, 5, 20}이런 수열이 있을 때, 1에서 출발한다. 자기자신이므로 합은 1이다. --> dp[1] = 1 10에 도착했다. 10>1을 만족하므로 합은 11이다. --> dp[2] = 11 2에 도착했다. 2와 앞의 원소를 하나씩다 비교하여 최댓값을 골라낸다. 2>1을 만족하므로 합은 dp[1]+2 = 3 --> dp[3] = 3 5에 도착했다. 5와 앞의 원소를 하나씩.. 2022. 2. 19. [백준] 2293 동전1 c++ 그리디알고리즘을 사용한 동전0문제와는 달리 동전1문제는 다이나믹 알고리즘을 사용한다. 점화식 생각이 도저히 안나서 풀이를 참고했는데, 봐도 봐도 헷갈리는 개념이었다. 핵심은 이거다. n번째 동전을 한번 쓴 경우 + n번째 동전을 사용하지 않은 경우 예를 들어서 1, 2, 5원짜리 동전으로 10원을 만들려고 할 때, 5원짜리를 1번 써서 10원을 만든 경우와 5원짜리를 쓰지 않고 10원을 만든 경우로 나눌 수 있다. 이런식으로 계속 내부적으로 나누게 되면 결국 모든 가짓수를 구할 수 있다. 아래 표는 동전단위에 대한 경우의 수를 나타낸 것이다. 그림출처 https://wtg-study.tistory.com/67 Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 .. 2022. 2. 18. 이전 1 ··· 6 7 8 9 10 11 다음
