알고리즘/알고리즘 종류 설명7 알고리즘 풀 때, 주의할 점 Algorithm 풀 때 주의할 점 1. 문제에서 제시 된 행렬을 잘 판단 해야한다. 좌표가 m = 4, n = 3인 격자모양이 있을 때 행 : n, 열 : m이다. 이때, 잠긴 지역의 좌표를 담은 2차원 배열 puddles가 있을 때 puddles[i][j] i 는 열이다. j 는 행이다. 행렬 판단을 잘 해야 한다. 참고 자료 코딩테스트 연습 - 등굣길 | 프로그래머스 (programmers.co.kr) 2021. 8. 19. 완전 탐색이란 무엇인가? 완전 탐색 (Exhaustive Search) 모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘이다. 알고리즘을 풀 때 가장 강력하고 확실한 방법이지만 시간이 가장 오래 걸리는 탐색 기법이다. brute fore algorithm이라고도 불린다. 자원만 충족해준다면 항상 100%의 정확도가 보장된다. 0000 ~ 9999로 이루어진 임의의 비밀번호를 찾고 싶을 때, 가능한 모든 조합은 1만 개(10^4)이다. 완전탐색 기법의 종류 Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법 비트 마스크 : 이진수 표현을 자료구조 쓰는 기법 (AND, OR, XOR, SHIFT, NOT) 재귀함수 순열 : 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어 놓은 수.. 2021. 8. 18. Dijkstra 알고리즘이란 무엇인가? 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘 : 하나의 정점에서 다른 모든 정점들의 최단 경로를 구한다. 다익스트라 알고리즘의 기본 로직 : 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신하는 것이다. 정점을 잇기 전까지는 시작점을 제외한 정점들은 모두 무한 대 값을 가진다. 1. 다익스트라 알고리즘 기본 로직 시작점 : 5번 정점 5번 노드를 제외한 나머지 정점들이 가지는 최단 경로는 아직 연결되지 않았으므로 무한대이다. 1) 경로가 가장 짧은 정점을 고른다. 시작 점, 5번 노드와 연결되어 있는 노드는 2, 4번 노드이다. 2번 노드 dist[2] = min(dist[2], dist[5] + adj[5][2]) min(INF, 4) = 4 4번 .. 2021. 8. 15. Floyd 알고리즘이란 무엇인가? 플로이드(Floyd) 알고리즘 플로이드 알고리즘 : 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구한다. 다익스트라 알고리즘 : 한 시작점에서 다른 정점까지의 최단 거리를 구한다. 1) 경유점 a와 b로 연결되어 있는 간선의 비용 : 5 a와 c : 2, c 와 b : 2 => 4 a와 b로 가는데 c를 거쳐가는 것이 더 효율적이다. c와 같이 경로가 거쳐가는 정점이 경유점이라고 한다. 플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택하게 된다. 2) 구현 위 그래프가 있을 때, 모든 쌍의 최단거리는 어떻게 될까?🤔 다익스트라 알고리즘을 이용하여 모든 정점에 대해서 구할 수 있지지만, 플로이드 알고리즘을 쓰면 보다 쉽고 빠르게 구할 수 있.. 2021. 8. 14. Backtracking이란 무엇인가? 백트래킹(Backtracking) 일반적인 알고리즘이다. 백트래킹은 CSP(Constrain Staisfaction Problems)을 해결하기 위해 쓰인다. 백트래킹은 모든 조합의 수를 조건이 만족할 때 살펴본다. N-Queen문제에서 많이 사용된다. N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 4 * 4 기준으로 문제를 풀어보자. 퀸은 칸을 기준으로 오와 열, 대각선 이동이 가능하다. 첫 번째 퀸과 공격할 수 없게 배치할려면 2번째 줄은 3, 4번째 위치에 퀸을 놓아야 한다. 첫 번째 퀸의 위치를 (1, 1)로 하면 트리구조는 다음과 같다. 만약 이문제를 가지치기 하지않는 DFS로 풀이했다면 유망하지 .. 2021. 8. 4. DP란 무엇인가? 동적 계획법 동적 계획법(dynamic programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 1. 동적 계획법의 조건 1) 부분 반복 문제(Overlapping Subproblem) 동적 계획법의 등장은 피보나치 수열에서 시작되었다고 한다. 피보나치 수열을 재귀 함수로 표현할 시, 이와 같다. fib(1) = 1; fib(2) = 1; fib(n) = fib(n-1) + fib(n-2); // 메소드로 표현한 피보나치 수열 int fib(int n) { if (n 2021. 8. 4. 이전 1 2 다음
