본문 바로가기
My Image
반응형

분류 전체보기228

[Algorithm] JAVA 중복 순열 알고리즘 (재귀) 안녕하세요. Limky 입니다. 이번시간에는 경우의 수 중에 순열에 대해서 알아보겠습니다. 헌데, 순열은 순열이지 왜 중복순열이라고 했을까요?? 당연 중복순열과 중복되지 않는 순열은 조금 다릅니다. 자기자신을 포함하냐 안하냐에 따라 순열과 중복순열로 구분합니다! 예제를 들어 설명해보겠습니다. 여기 구슬 3개가 있습니다. 1, 2, 3 중복이 없는 순열은 자기자신을 제외하고 모든 경우의 수를 생각하는 것입니다. 3개의 구슬중에 2개를 뽑는 경우의 수는 아래와 같습니다. 1, 2 1, 3 2, 1 2, 3 3, 1 3, 2 입니다. 총 3 X 2 = 6가지 이지요? 하지만!! 중복순열은 다릅니다. 자기자신을 포함하죠.... 똑같이 구슬 3개가 있습니다. 1, 2, 3 중복을 허용해서 뽑으면 아래와 같습니다... 2019. 2. 21.
[BackJoon] 백준 3055 탈출(BFS) 백준 BFS 문제#3055- 탈출 https://www.acmicpc.net/problem/3055 사용한 개념 BFS개념을 사용했습니다.문제에서의 포인트는 다음과 같습니다. 한 단계씩 시간이 지날 때마다 고슴도치는 한칸 이동할 수 있고, 물은 상하좌우 4방향 중 물이 넘칠 수 있는 곳에 넘칩니다. 여기서 중요한 것은 물이 한단계 이후에 넘칠 위치는 고슴도치가 이동 할 수 없다는 것이 포인트 입니다. 자 아래 2가지만 명심하면 문제는 쉽습니다. 1. DFS를 통해 단계가 진행될 때, 고슴도치, 물 이 움직일 수 있는 조건들을 생각해 코딩합니다.2. 여기서 물이 한단계 이후 넘칠 공간에는 고슴도치가 이동할 수 없기 때문에 물을 먼저 넘치게하고 그다음! 고슴도치가 움직이는 매커니즘으로 작동하게 한다!! 여기.. 2019. 1. 7.
[BackJoon] 백준 1697 숨바꼭질(BFS) 백준 BFS 문제 #1697- 숨바꼭질 https://www.acmicpc.net/problem/1697 사용한 개념 BFS개념를 응용했습니다. 우선 방문한 곳은 check 1차원 배열로 방문여부를 체크하여 방문하지 않은 곳만 방문을 하게끔 만들고, BFS 을 통해 방문하지 않은 곳을 계속해서 탐색하도록 합니다. 여기서 포인트는 방문할 때마다 몇번만에 해당 탐색지점에 왔는지 카운트를 해주는 것입니다. *2에서 5를 찾는 경우 예를 들어 2번에서 시작한다고 치고, 2번에서 *2를 해 4번으로 갔다면, 처음 2번에는 카운트 0을 저장하고 4번에 카운트는 0+1 = 1 입니다. 다음 4번에서 +1을 했다면 5번에는 카운트 0+1+1 = 2 입니다. 이런식으로 2에서 시작해 5번으로 도착할때 카운트는 결국 카운.. 2019. 1. 3.
[알고리즘] 다익스트라 최단거리 알고리즘(Dijkstra) 다익스트라 최단거리 알고리즘(Dijkstra) 다익스트라 알고리즘은 워낙 유명하죠 ㅎㅎ 다익스트라 알고리즘은 그래프에 있어서 탐색 시작 노드에서 탐색할 노드까지의 최단거리를 구하는 알고리즘입니다. 다익스트라 알고리즘은 실생활에서도 많이 쓰입니다. 지하철 최단거리 노선을 알려준다거나, 네비게이션 최단 경로를 알려주는 등 굉장히 활용도가 높은 알고리즘 입니다. 일단 노드간 가중치가 있어 최단거리를 구할 수 있습니다. 연결되 노드간 가중치의 합이 최단거리라고 할 수 있기 때문이죠. 아래 전체소스에 주석으로 상세히 적어놓았으나, 몇가지 포인트는 알고있어야 합니다. 원리는 다음과 같습니다. 경로를 통해 지나온 노드간 가중치들의 합이 가장 작은 값을 계속 갱신하며, 최단거리 가중치 합을 구하는 것입니다. 예를 들어.. 2018. 12. 25.
반응형

티스토리툴바