본문 바로가기

전체 글79

[SWEA] 7465 창용 마을 무리의 개수 - 자바 문제 접근 : DFS 고려 요소 양방향이므로 양방향 간선으로 저장해야 합니다. 또한, 연결리스트를 통해 이러한 간선에 대해 표현하였습니다. 연결리스트 초기화 필수!! 노드는 1~N번 모든 노드에 대해 DFS를 탐색해야하며, 이미 방문한 노드(이미 그룹이 됨)는 탐색을 수행하지 않도록 boolean배열을 사용합니다. public class Solution_7465 { private static List node; private static boolean[] visited;//방문 여부 확인 private static int N;//마을에 사는 사람의 수 public static void main(String[] args) throws NumberFormatException, IOException { Buf.. 2022. 8. 24.
[Algorithm] 비트마스크 오늘은 부분집합을 비트연산자를 통해 구현하는 방법에 대해 알아보겠습니다. bit 1인 경우, 그 위치에 맞는 집합의 숫자를 출력하는 형태를 통해 모든 부분 집합의 경우의 수를 나타낼 수 있습니다. 특히, 부분집합의 개수는 2^N으로 표현되는데, 이를 1 2022. 8. 22.
[SWEA] 자바 1247 최적경로 접근 방안 : 완전 탐색(DFS) 고객의 집 방문 순서에 대해 하나씩 방문해보면서 총 이동 경로를 구했습니다. 재귀함수를 통해 이와 같은 로직을 구현했습니다. 또한, 마지막 고객의 집에 방문한 경우 구하고자 하는 답의 값을 갱신해주었습니다. 실행시간 단축을 위한 추가 개선 사항 비트 연산자를 통해 사용해 풀어볼 수 있습니다. flag와 1 2022. 8. 21.
[Algorithm] 순열, 조합 구현 순열 : 서로 다른 n개의 수에서 r개를 뽑아서 정렬하는 경우의 수( nPr 로 표현된다.) 순열은 순서를 생각해서 뽑아야 한다. 예를 들어 {1,2,3,4,5} 중에서 3개의 수를 뽑아야 하는 경우 {2,3,4}와 {2,4,3} 은 다른 경우의 수로 카운트된다. 재귀를 통해 구현할 수 있다. 순열을 구현하기 위해서는 함수 안에서 현재 수를 뽑고 다음수를 뽑기 위해 재귀함수를 호출한다. 특히, 중복순열과는 다르게 순열은 중복해서 수를 뽑을 수 없기 때문에, 현재 수를 뽑았는지를 확인하기 위해 boolean배열을 사용한다. public class PermutationTest { private static int N;//총 개수 private static int R;//뽑을 개수 private static .. 2022. 8. 20.

티스토리툴바