알고리즘5 자료구조 : 연결리스트 (Linked list) 자료를 저장하는 방법 중 크게 배열과 연결리스트가 있습니다. 그럼 언제 배열을 사용하고 언제 연결리스트를 쓸까요? 먼저 두 자료구조의 장, 단점에 대해 알아보겠습니다. 표1 배열, 연결리스트 장점 및 단점 배열은 접근이 빠르고 간단합니다. n번째 인덱스에 접근할 경우 arr[n]을 사용하면 빠른 시간에 접근할 수 있습니다. 그러나 배열을 사용하기 위해서는 처음에 배열의 크기를 선언해야 하고 크기의 수정이 불가능하기 때문에 메모리 사용이 비효율적입니다. 또한 중간 데이터를 삭제 했을때 빈 배열을 처리하는 것이 번거롭습니다..( 자료구조를 공부해보신 분이라면 이해하실 겁니다ㅠ) 그러나 연결리스트는 위의 단점을 해결할 수 있습니다. 필요할때마다 데이터를 생성하여 연결하면 되기 때문에 메모리를 효율적으로 사용가.. 2017. 11. 8. 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘(Dijkstra Algorithm) 그래프 내에서 최단경로를 정하는 알고리즘은 여러가지가 있습니다. 그 중 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구할 때 사용됩니다.또한 모든 간선의 가중치가 양의 가중치를 가지고 있을 때 사용할 수 있습니다. 다익스트라의 기본적인 원리는 한 정점에서 갈 수 있는 다른 정점 중, 작은 가중치 간선을 우선적으로 탐색하는 방법입니다. 현재 정점을 A라 하고, A와 연결된 가선이 B라고 가정해 봅시다. A까지 이동하는 비용을 a , B까지 이동하는 비용을 b , A에서 B로 이동할 때 발생하는 비용 x 라 할 때a+x < b 라면B까지 가는 비용을 a+x로 갱신할 수 있습니다. 아래 예제를 통해 더 자세히 알아보겠습니다. 위와 같은 .. 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 다음 반응형
