본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm143

[동적계획법, 난이도 중상] 백준 1520번 내리막 길 이 문제는 동적계획법과 DFS를 동시에 적용해야 하는 문제이다. 백준 1890번 점프와 접근법은 비슷하다. https://kimcoder.tistory.com/47 [동적계획법, 난이도 상] 백준 1890번 점프 동적계획법과 DFS를 동시에 적용해야 하는 높은 난이도의 문제이다. 본인은 이제부터 DFS를 마주쳤다 싶으면 바로 그래프로 도식화해서 풀 것이라고 다짐했다. 이 문제는 두 스텝으로 나누어서 �� kimcoder.tistory.com 경로벡터를 이용하였으며 도착점부터 시작점까지 역으로 DFS를 수행하였다. 자세한 설명은 위 링크에 있는 백준 1890번 점프 풀이를 읽고오면 된다. 아래 그림도 백준 1890번 점프에서 도식화 했던 원리랑 똑같다. 문제에 따른 push_back 기준만 다를 뿐이다. .. 2020. 8. 17.
[동적계획법, 난이도 상] 백준 1890번 점프 동적계획법과 DFS를 동시에 적용해야 하는 높은 난이도의 문제이다. 본인은 이제부터 DFS를 마주쳤다 싶으면 바로 그래프로 도식화해서 풀 것이라고 다짐했다. 이 문제는 두 스텝으로 나누어서 해결했다. 1. 점프할 수 있는 좌표를 모두 경로벡터에 넣는다. 여기에서는 간선이라고 봐도 무방하다. 점프를 했을 때 맵 밖으로 벗어나는 경우도 신경 써줘야한다. 맵 밖으로 떨어진 좌표는 경로벡터에 넣지 않으면 된다. 오른쪽, 아래쪽만 점프 가능하다는 사실을 잊지말자. DFS를 도착점부터 역으로 수행할 것이기 때문에 간선 연결 방향은 반대로 했다. >> a[i+jump*dx[k]][j+jump*dy[k]].push_back(make_pair(i, j)); 이 과정이 끝나면 경로는 이렇게 된다. 맨 오른쪽 맨 아래 '0.. 2020. 8. 17.
[그리디, 난이도 중] 백준 1543번 문서 검색 문자열 매칭 알고리즘들중 라빈카프를 이용했다. 라빈카프 알고리즘은 문자열의 특정 해쉬값을 계산한 후 두 해쉬값이 일치할 경우, 문자열 매칭에 성공했다고 판단하는 알고리즘이다. 여기서 2차적으로 동일한 해쉬값을 가진 문자열에 대해서 확인차로 한번더 문자열 그 자체를 검사할 수도있다. 문자열의 해쉬값을 정하는 방법은 많지만 이 소스코드에서 해쉬값은 이렇게 정했다. 문자열 a의 size를 size라고 가정하면 문자열의 해쉬값 = a[0]*2^(size-1) + a[1]*2^(size-2) +a[2]*2^(size-3) + ... a[size-1]*2^0 https://www.youtube.com/watch?v=kJJQJDsjXc8 문자열 매칭 알고리즘은 동빈나 님의 강의로 배웠는데 여기서 동빈나님이 이용하신 .. 2020. 8. 17.
[DFS, 난이도 중] 백준 1389번 케빈 베이컨의 6단계 법칙 이 문제는 BFS로 푸는게 훨씬 간단하다. 왜냐하면 최단경로를 구해야 하는 문제이기 때문이다. DFS로 하면 꽤 신경써야될 것들이 있다. 깊이 매개변수를 추가해줘야하고 DFS를 다 돌면 방문처리를 해제해야한다. 본인은 DFS연습 차원으로 DFS로 풀었기 때문에 DFS이용 기준으로 난이도를 중으로 정했다. BFS로 풀었다면 중하~하 사이가 아닐까 싶다. 주어진 예제를 양방향 그래프로 도식화한 그림이다. dfs의 매개변수는 각각 (출발점,도착점,깊이) 이다. 출발점=도착점인 경우 깊이의 최솟값을 갱신하는 처리를 해준뒤 하나의 dfs함수를 종료한다. 노드n이 노드1~n까지 모두 탐색하여 구한 최단경로의 합은 kevin[n] 이다. kevin의 최솟값을 가지는 최초의 인덱스값을 출력하면 문제는 해결된다. BFS.. 2020. 8. 16.
[동적계획법, 난이도 중하] 백준 11726번 2xn 타일링 이 문제에 동적계획법을 적용시키면 2x1, 2x2, 2x3, ... 2x(n-1),2xn 이런식으로 차례대로 이전 값을 이용하여 계산해 나가면 된다. 이전 타일값에 1x2, 2x1 타일을 붙일 수 있는 경우의 수를 따져보자. 위의 전체 타일의 넓이는 2xn이다. 그리고 갈색 타일의 넓이는 1x2, 2x1이다. 이렇게 2x(n-1) 타일에 2x1 타일을 1개 추가하는 방법 -> 1가지 2x(n-2) 타일에 1x2 타일을 2개 추가하는 방법 -> 1가지 2x(n-2) 타일에 2x1 타일을 2개 추가하는 방법은 포함하지 않는다. 왜냐하면 이는 2x(n-1) 타일에 2x1 타일을 1개 추가하는 방법과 같은 경우이기 때문이다. 경우가 중복된다는 의미다. 즉 save[n]=save[n-1]+save[n-2] 라는 .. 2020. 8. 16.
[DFS, 난이도 중하] 백준 10026번 적록색약 (BFS, DFS 모두 사용) 제출번호 21761134가 DFS로, 제출번호 21760828이 BFS로 해결해서 정답처리된 소스코드이다. 맵의 모든 구역을 탐색하면서 탐색하지 않은 좌표에서 BFS/DFS를 호출하여 , 인접 색들을 만나면 전부 방문처리를 한다. BFS/DFS를 호출할 때마다 group 카운트를 늘려나가서 몇 개의 그룹으로 이루어져 있는지 계산하면 된다. 적록색약이 아닌사람에 대해서 map배열, visited배열, group변수를, 적록색약인 사람에 대해서 map2배열, visited2배열, group2변수를 썼다. 두 가지 경우에 대해 모두 수행해주었다. 적록색약인 사람인 경우 모든 초록색을 빨강색으로 인지하는 것으로 가정했다. 즉 map2에서는 R 혹은 B만 존재한다. 애초에 모든 G를 R로 바꾼 것이다. 이렇게 접.. 2020. 8. 15.
[동적계획법, 난이도 중하] 백준 1003번 피보나치 함수 피보나치 함수 fibonacci(n) 의 리턴값은 fibonacci(n-1)+fibonacci(n-2) 이다. fibonacci(0)은 0을 출력하므로 0이 1회 출현한다고 보고 fibonacci(1)은 1을 출력하므로 1이 1회 출현한다고 본다. 그렇다면 fibonacci(2)는 fibonacci(1)과 fibonacci(0)을 리턴하기 때문에 0,1이 1회씩 출현한다고 할 수 있다. fibonacci(3)까지 해보자. fibonacci(3)은 fibonacci(2)와 fibonacci(1)을 리턴하기 때문에 0은 1회, 1은 2회 출현한다고 할 수 있다. 자세히 나타내면 이렇다. fibonacci(2) -> 0 1회, 1 1회 fibonacci(1) -> 0 0회, 1 1회 fibonacch(3) 총.. 2020. 8. 15.
[동적계획법, 난이도 중하] 백준 9095번 1,2,3 더하기 1,2,3 이 3개의 정수의 덧셈으로 n을 표현해야 하기 때문에 1,2,3 을 표현하는 방법은 미리 구해놓자. 1 -> (1) 1가지 2 -> (1+1),(2) 2가지 3 -> (1+1+1), (2+1), (1+2) , (3) 4가지 n=4일때부터 순차적으로 DP를 진행해야 하는데 동적계획법은 이전에 계산 했던 값들을 가지고 현재 정보를 계산하는 알고리즘이다. 이전 값은 이렇게 응용하면 된다. 3을 1,2,3의 합으로 표현하는 방법은 -> (1+1+1), (2+1), (1+2) , (3) 총 4가지 인데 이 4가지 그룹에서 각각 1을 더해주면 4가 나오지 않을까? 그리고 2를 1,2,3의 합으로 표현하는 방법은 -> (1+1),(2) 총 2가지 인데 이 2가지 그룹에서 각각 2을 더해주면 4가 나오지 않.. 2020. 8. 15.
[SCC, 난이도 중상] 백준 9466번 텀 프로젝트 원래 알고리즘 분류상 DFS에 들어가 있던 문제인데, 강한 결합요소(SCC) 유형이라고 보는게 더 좋을 것 같아서 그래프 카테고리에 포스팅 한다. 강한 결합요소 알고리즘도 DFS를 쓴다. 강한 결합요소 알고리즘을 간단하게 설명하자면 이렇다. 일단 아래 그림은 9466번 예제에서 첫 번째 케이스를 도식화 한것이다. 3번은 자기 자신을 가리킨다는 의미로 동그라미로 감쌌다. 여기서 SCC는 5개다. (1번), (2번), (3번), (4번,6번,7번) , (5번) 여기서 (4번,6번,7번)은 사이클로 되어있으므로 하나의 SCC그룹이라고 하는 것이다. 아래 소스 코드에서 dfs함수가 SCC(강한결합요소) 알고리즘이다. 그런데 여기서 한가지 처리를 해줘야 한다. 서로 선택 받고 있는 그룹은 (3번),(4번,6번,7.. 2020. 8. 15.

티스토리툴바