Limky 삽질블로그

백준 DFS 문제 #2667 - 단지번호붙이기 https://www.acmicpc.net/problem/2667 사용한 개념 1) DFS 저는 깊이탐색을 사용했습니다. 우선, 2차원 배열에서 0이 아닌 1인 경우에 깊이탐색을 시작하여 인접해있는 1을 모두 찾게합니다. 그 다음 다시 탐색을 이어가 0이 아닌 1인경우 다시 깊이탐색을 시작합니다. 여기서 달라지는 점은, 이미 탐색을 했다라는 표시를 하기 위해 임시 변수 값이 CNT의 값을 증가시켜 해당 값으로 매핑시켜 표시합니ㅁ다. 따라서.. 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 인 경우, 2 2 0 0 0 2 0 0 0 0 0 0 0 3 3 4 4 0 3 3 0 4 0 0 3 위와 같이 매핑되는 것입니다...

삼성 SW테스트#15684 - 사다리 조작(Ladder Manipulation) https://www.acmicpc.net/problem/15684 사용한 개념 1. 중복이 없는 조합 해당 문제를 푸는데 있어 많은 개념이 사용되지는 않았습니다. 다만.. 아래와 같은 고민을 많이했습니다. 1. 사다리를 어떻게 저장하고 표현할 것인가??2. 사다리를 탈때, 원리가 무엇이고 해당 원리를 어떻게 반영할까?... 또한, 문제를 풀면서...보완해야할 점도 생각하게 되었습니다. 중복이 없는 조합을 재귀로 구현했지만, 나중에는 재귀방식이 아닌 더 간단한 방식으로 조합을 구하는 방법을 강구해야 할 것 같습니다. 소스가 복잡해지고, 예외처리를 해야하는 부분이 늘어나는 느낌이라서요...ㅎㅎ 자 그럼 ... 1. 사다리를 어..

삼성 SW테스트#15685 - 드래곤 커브(Dragon Curve) https://www.acmicpc.net/problem/15685 사용한 개념 1. 음...규칙찾기?(수열과 같은 느낌) 처음 이런류의 문제를 시뮬레이션이라 부른다고 합니다.. 백준 알고리즘 카테고리에는 시뮬레이션으로 분류되어있네요~ 문제를 이해하셨다면 아시겠지만, 분명 세대가 증가할때마다, 이전 세대와의 어떠한 규칙이 있음을 의심하고 그 규칙을 찾는것이 제일 먼저 선행 되어야 합니다. 보통 대게 이런문제가 규칙을 찾고 그 규칙대로 구현을 하면 되는 문제인 것 같습니다. 자.. 그럼 규칙을 찾아보겠습니다. 저는 무식하지만 제일 간단한 접근방법인 한단계씩 적어서 어떠한 규칙이 있는지 파악하겠습니다. 다음과 같이 방향이 주어질때, 0 방향..

삼성 SW테스트#15686 - 치킨 배달 https://www.acmicpc.net/problem/15686 사용한 개념 1. 경우의 수 (재귀)2. BFS 탐색 전체적인 알고리즘을 작성하기 앞서, 문제를 해결하기 위해 어떤 알고리즘들이 사용되는지 생각해보았습니다. 먼저, 문제에서도 알 수 있듯이, 전체 치킨집들 중에서 특정 치킨집들만 선택하기 때문에 경우의 수 조합이 필요합니다. 또한, 2차원 배열상 A와 B 사이의 거리를 구해야하기 때문에 탐색 알고리즘이 필요합니다. 저는 BFS 너비탐색으로 탐색하기로 했습니다. 알고리즘 선택이 끝났으면, 이제 전체적인 프로세스 순서를 생각해봅시다. 먼저... 순서는 다음과 같이 생각할 수 있겠네요.. 1. 전체 치킨집 중 N개 치킨집을 간택한다. 즉 nCr2. 각각..

BackJoon #7576 - 토마토(Tomato) https://www.acmicpc.net/problem/7576 백준 쉬운 토마토 문제 BFS로 돌리면 쉽게 해결 할 수 있습니다. ㅎㅎ package BackJoon.Graph.BFS; import java.awt.Point; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Tomato2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m =..

BackJoon #1914 - 하노이(Hanoi) https://www.acmicpc.net/problem/1914 하노이 솔루션 우선 n개를 쌓을 경우 n번째를 제외한 n-1를 하나로 간주하고 3가지 스텝을 거치면 풀린다.... 1. 1기둥에 있는 n-1개를 3기둥을 이용하여 2기둥으로 옮긴다!2. 1기둥에 있는 1개를 3기둥으로 옮겨라3. 2기둥에 있는 n-1개를 1기둥을 이용하여 3기둥으로 옮겨라! ** 문제는 출력초과 **- 이 부분은 좀 더 연구가 필요하다....아시는 분은 저에게 가르침을... package BackJoon.Recursion; import java.util.Scanner; public class Hanoi { public static void main(String[] args)..

BackJoon #11403 - 경로찾기(Find Directions) https://www.acmicpc.net/problem/11403 위 문제는 DFS 탐색 예제입니다... DFS는 보통 재귀함수 (Recursion)을 사용하는데, 재귀함수에 대한 연습도 할 겸 풀어보시면 좋습니다. 우선 기본적으로 DFS 재귀함수를 통해 i에서 j로가는 경로가 있는지 c 1차원 배열에 경로 여부를 체크합니다. 또한, 다음 경로탐색을 위해 Arrays.fill 메서드를 이용 0으로 초기화 해줍니다. n+1로 n값에 +1을 한 이유는 편의상 배열의 첨자와 정점의 싱크를 맞추기 위해서 입니다. 0번 인덱스는 신경쓰지 않으셔도 됩니다. 즉 정점은 1부터 시작하니 그냥 2차원배열이든 1차원배열이든 1첨자로 부터 시작하기 위..

BackJoon #14890 - 경사로(Runway) https://www.acmicpc.net/problem/14890 삼성SDS 2017 하반기 SW직군 역량테스트 중 기출문제 2번을 풀어봤습니다.생각보다 많이 고전한 문제였습니다...코드가 좀 지저분한데 리팩토링 좀 해야겠네요.. package SamsungTest; import java.util.Scanner; public class Runway { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int l = sc.nextInt(); double [][] ground = new double[n][n]; double [..