알고리즘/문제풀이4 BOJ 1753 최단경로 BOJ 1753 최단경로[https://www.acmicpc.net/problem/1753] 다익스트라를 적용할 수 있는 기본문제입니다. 아래 주소에 다익스트라에 관한 설명과 본 문제의 테스트케이스를 이용한 예제를 확인할 수 있습니다.[http://sycho-lego.tistory.com/7] 우선순위 큐를 이용하여 다익스트라를 구현하였습니다. 정답코드는 아래 주소에서 확인할 수 있습니다.[https://github.com/choseungyoon/Algorithm/blob/master/BOJ/1753_%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C.cpp] 2017. 10. 6. BOJ 11811 데스스타 BOJ 11811 데스스타 [https://www.acmicpc.net/problem/11811] 비트연산을 이용하는 문제입니다. 모든 행렬의 값은 각 행 , 열의 and연산으로 이루어져 있기 때문에 각 행의 모든 값을 or연산하면 답을 유추할 수 있음을 쉽게 알 수 있습니다. 모든 j에 대해서ans[i] = ans[i] | arr[i][j] 아래 주소에서 정답코드를 확인할 수 있습니다.[https://github.com/choseungyoon/Algorithm/blob/master/BOJ/11811_%EB%8D%B0%EC%8A%A4%EC%8A%A4%ED%83%80.cpp] 2017. 10. 4. BOJ 1525 퍼즐 BOJ 1525 퍼즐[https://www.acmicpc.net/problem/1525] BFS를 이용한 완전탐색 문제입니다. 빈칸을 옮겨가며 모든 경우의 수를 확인해보면 되는데문제는 방문체크를 하는 것입니다. 3x3 행렬을 다음과 같이 정수를 변환시켜 보겠습니다. 1 2 3 0 4 5 6 7 8 위 행렬은 123045678 와 같은 정수로 변환할 수 있습니다. STL의 set을 이용하여 변환된 정수를 Key값으로 사용하면 방문체크를 할 수 있습니다. 방문체크를 제외하고는 BFS 알고리즘을 그대로 구현하시면 됩니다. 아래 주소에서 정답코드 확인가능합니다.[https://github.com/choseungyoon/Algorithm/blob/master/1525.cpp] 설명이 잘못 되었거나 이해가 안되시는.. 2017. 9. 25. BOJ 2533 사회망 서비스(SNS) 2533 사회망 서비스(SNS) [https://www.acmicpc.net/problem/2533] 문제를 읽어보시면 친구와의 관계는 Tree로 표현될 수 있다는 것을 알 수 있습니다. 이 문제는 트리 탐색과 메모리제이션을 동시에 하면서 해결 할 수 있습니다. 아래와 같은 친구관계를 가지고 있는 트리를 이용해 설명하겠습니다. 메모리제이션을 이용할 dp테이블은 다음과 같습니다 dp[i][state] : i번째 정점을 root로 가지고 있는 Subtree 에서의 최소 얼리어답터 수 : state == 0 -> 정점 i가 얼리어답터가 아닌 경우 : state == 1 -> 정점 i가 얼리어답터인 경우 우선 루트노드(1번 노드)부터 Leaf 노드까지 탐색합니다. 제일 첫번째 방문하는 Leaf 노드는 5번 노드.. 2017. 9. 24. 이전 1 다음 반응형
