코딩 소양 (24) 썸네일형 리스트형 [DP & GA] Dynamic Programming & Greedy Algorithm 이번에는 Dynamic Programming에 대해서 알아보겠습니다.해석하면 동적 프로그래밍이라고 하지만.. 절대 동적이지 않습니다.. Dynamic Programming은 각 경우에 대한 table을 만들어서 점화식을 도출해내는 방식을 말하는데 간단한 문제에 대해서 알아봅시다. 풀어볼 문제는 백준 알고리즘의 1003번 문제입니다! https://www.acmicpc.net/problem/1003 문제는 간단한 피보나치 수열에 대해서 fibonacci(n)이라고 했을 때 fibonacci(N)을 호출하면 fibonacci(0), fibonacci(1)을 얼마나 불러오는지구하는 문제입니다. 문제에 보면 피보나치 수열에 대한 함수를 줬는데, int fibonacci(int n) { if (n == 0) { .. [Shortest Path] Dijkstra Algorithm 이번에 준비한 알고리즘은 Shortest Path를 찾는 알고리즘인 Dijkstra Algorithm입니다!! 옛날에 처음 다익스트라 알고리즘 배웠을 때는 좀 노가다스럽게 배워서 엄청 어렵고 짜증난 알고리즘이었는데, 다시 공부하니까 참 쉽네요... 역시 가르치는 사람이 잘 해야하는건가.. 아무튼! Dijkstra Algorithm은 BFS기반으로 Shortest Path를 찾는 알고리즘입니다. 절차를 설명하자면! 탐색되지 않은 노드가 담긴 우선순위 큐로부터 다음 탐색 노드를 pop한다. 탐색 노드의 주변 연결된 노드들에 대해서 거리를 비교해본다. 여기서 비교란 기준 노드 탐색 노드 연결 노드의 거리값이 현재 연결 노드에 설정된 거리값보다 작은지 비교하는 것이다. 작다면 연결 노드의 거리값을 재설정해준다... [MST - 3] Prim Algorithm 다음으로 볼 알고리즘은 MST를 구하는 두 번째 알고리즘인 Prim Algorithm입니다. 일전에 MST랑 Krustal Algorithm 에 대해서 알아보았는데, 이번에는 다른 MST를 찾는 Algorithm입니다!! Prim Algorithm의 특징은 이러합니다. 어떠한 vertex로 시작해도 결과는 똑같다. 방향성을 가진다. BFS처럼 주변을 먼저 살핀다. Krustal Algorithm은 Find, Union 구동 방식을 사용하지만, Prim Algorithm의 경우는 vertex의 주변 vertex를 탐색하는 방법으로 MST를 찾습니다. Prim Algorithm의 핵심은 key값이 있다는 것인데, Krustal Algorithm의 대표값이랑 비슷하면서도 다른 사용 방법을 가지고 있습니다. K.. [MST - 2] Kruskal Algorithm MST를 알아보았고, 이번에는 MST를 구하는 첫 번째 알고리즘인 Krustal Algorithm에 대해서 알아봅시다. 저번 포스트(MST - 1)에서 MST에서 사용되는 여러 용어들에 대해서 알아보았는데, Krustal Algorithm에서는safe edge에 대한 개념이 사용됩니다. 기본적으로 Krustal Algorithm은 Find, Union의 구동 방식을 찾는데, 이에 대해서 먼저 알아봅시다. find : Vertex(정점)의 집합인 Cut의 대표값이 다른지 검색하는 단계union : 대표값이 다른 Cut 두 개를 합치는 단계 그림으로 보니까 이해가 되시나요?? Krustal Algorithm은 이게 전부입니다. 조금 유식하게 Krustal Algorithm을 표현해보면~ safe edge에 .. [MST - 1] Minumum Spanning Tree 이번에는 MST(Minumum Spanning Tree)에 관해서 알아봅시다. 한국어로는 최소 신장 트리라고하는데, MST를 보기 전에 먼저 Spanning Treed에 대해서 봅시다. Spanning Tree ? graph의 최소 연결 부분으로 나타낸 Tree 최소 연결 부분이라는 것이 안 와닿을 수 있는데, n개의 정점을 가지는 graph에서 간선의 수가 최소로해서 나타내는 것입니다. 간선의 수가 최소가 된다는 거는 정점은 일대일로 연결이 되어 있다는 것이겠네요!이런 경우 반드시 Tree의 형태가 되기 때문에 Spanning Tree라고 한다는 군요. 그림으로 보면 바로 이해가 될 것입니다. 이제 MST를 살펴봅시다. 결국 Minumum Spanning Tree라는 것은 Spanning Tree 중 .. [백준 알고리즘] 14891번 톱니바퀴(삼성 기출) 이번엔 삼성 SW역량 테스트 기출문제 14891번 톱니바퀴를 준비해보았습니다!!! 문제가 꽤 기네요!!! 문제를 간략하게 보면 톱니바퀴 4개를 돌릴 껀데 다 돌려서 최종 결과를 수치화 해서 보여주시오. 이것입니다. 먼저 문제를 설계하기 위한 여러가지를 생각해봅시다. 톱니바퀴 정보를 저장할 변수 등 여러가지 변수 함수 설계 사용할 알고리즘(배경) 톱니바퀴를 돌리고, 영향을 받는다고 할때 어떻게 돌아갈까? 간략하게 3개 정도 볼 수 있겠네요. 전 먼저 배경이 될 알고리즘으로는 BFS를 생각하였습니다. BFS는 주변을 먼저 살피자 라는 느낌이 있으니까용ㅎㅎ 그러면 사용할 변수들을 생각해봅시다. 톱니바퀴는 4개 고정, 8개의 톱니를 가지니까 4개의 톱니바퀴 배열(길이는 8)로 생각할 수 있죠. 저는 접근에 용이.. [백준 알고리즘] 3053번 택시 기하학(기하) 이번엔 조금 색다른 문제를 준비해보았습니다. 제가 도형, 기하학에 약해서.. 기하 문제를 준비해봤는데, 신기한 문제네요!! 3053번: 택시 기하학 문제를 보면 택시 기하학이라는 내용이 나오네요!!! 우리가 지금까지 배웠던 유클리드 기하학이 아닌 새로운 기하학으로 거리를 계산하는 방법이 특이하네요!! 이렇게 나오네요!! 물론 택시 기하학에 관해서 더 특이한 내용이 많겠지만, 이 문제를 풀때는 이 개념만 알면 금방 풀리네요ㅎㅎ 먼저 이 문제를 풀기 위해서는 원의 개념적 정의에 대해서 알아야할 필요가 있습니다. 저 어릴땐 선생님이 수학은 정의에서 다 끝난다고해서 전 다 외웠는데..ㅋㅋㅋㅋ못 외우면 혼났음 ㅠㅠ 원 : 한 점(중심점)을 기준으로 같은 거리에 있는 점들의 모임 자 그럼 유클리드, 택시 거리 공식.. [백준 알고리즘] 2667번 단지번호붙이기(BFS) 이번에는 BFS, DFS를 활용할 수 있는 문제를 풀어봅시다. 먼저 간단하게 탐색만 진행할 수 있는 문제를 준비해보았습니다. 2667번 단지번호붙이기 이 문제입니다!!! 문제는 다음과 같습니다. 저는 BFS로 접근해보았습니다. 풀이 방식은 매우 간단하게 BFS의 이론적인 내용을 그~대로 사용하였습니다. BFS의 활용이라고 보면 되겠네요!!! 먼저 main 코드부터 살펴보겠습니다!! #include #include #include #include #include using namespace std; int N; int map[25][25]; int multiplex[700] = {0,}; int amountOfMultiplex; int main() { cin>>N; amountOfMultiplex = 3;.. 이전 1 2 3 다음
