java4 [프로그래머스] 단체사진 찍기 단체사진 찍기 개요 - 카카오의 캐릭터들이 줄을지어 사진을 찍는데, 캐릭터들의 자리에 대한 제약조건을 만족하는 케이스 수를 찾는 문제이다. - dfs(depth first search, 깊이 우선 탐색) 방식을 사용한 캐릭터들의 순열을 구한 뒤 제약 조건들을 만족하는 경우들의 수를 세는 방식으로 해결했다. 문제 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지.. 2022. 3. 26. [백준]1504. 특정한 최단 경로 1504. 특정한 최단 경로 개요 - 이 문제는 가중치가 있는 그래프의 최소 경로를 찾는 문제로 다익스트라 알고리즘을 이용하는 문제이다. - 다만 특이하게 반드시 거쳐야할 정점의 번호가 주어진다. 어렵게 생각하지않고 각 정점을 들르면서 목적지까지 갈 경로들의 가중치 중에서 최소값을 구하는 방법으로 문제를 해결했다. 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 .. 2022. 3. 18. [기본 개념] 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘(Dijkstra Algorithm) 개요 - 최소 경로를 찾는 다익스트라 알고리즘의 개념을 알아본다. - 사용하는 경우와 사용하지 못하는 경우를 알아보고, 최소 경로 결과를 도출하는 과정을 살펴본다. 기본 개념 - 그래프의 간선에 가중치가 주어졌을때 출발 노드에서 목적지 노드까지 도달하는 최소비용을 찾는 알고리즘이다. - 다익스트라 알고리즘을 이용하면 출발지에서 모든 노드까지의 최소 도달 비용을 알 수 있다. 따라서 목적지까지의 최소비용도 함께 알 수 있다. - 다음은 다익스트라 알고리즘으로 최소 비용을 찾는 과정이다. 최소 비용을 찾는 과정( 다익스트라 알고리즘 이용 ) 0. 모든 노드의 최소 가중치를 찾기 위해서 다음과 같이 세 변수가 필요하다. - 각 노드의 방문 여부 (모든 노.. 2022. 3. 12. [백준]5670. 휴대폰 자판 5670. 휴대폰 자판 개요 - 이 문제는 트라이 자료구조에 사전에 있는 단어들을 넣은 뒤 각 노드의 자식 노드 개수를 통해 각 단어의 최소 입력 횟수를 구하는 문제이다. 문제 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발하였다. 이 모듈은 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 준다! 자세한 작동 과정을 설명하자면 다음과 같다. 모듈이 단어의 첫 번째 글자를 추론하지는 않는다. 즉, 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력해야 한다. 길이가 1 이상인 문자열 c1c.. 2022. 3. 10. 이전 1 다음
