Hee's Story

Backtracking (백 트래킹) 모든 경우의 수를 전부 고려하는 알고리즘이다. 즉, 조합 알고리즘 문제에 대해 어떤 조건을 만족할 때 모든 가능한 해를 나열한 것이다. 일종의 트리 탐색 알고리즘으로 DFS, BFS 등의 방식을 사용한다. DFS 모든 경우의 수를 고려해야 하는 문제일 때 주로 사용한다. 하지만 트리의 깊이가 무한대가 될 때는 절대 사용하면 안된다. (무한루프에 빠짐) -> 이 때, 중복검사를 따로 해야 함 BFS 최단거리를 구할 때 주로 사용한다. Backtraking의 대표적인 예제로 N-Queen이 있다.

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo&categoryId=AWXRUN9KfZ8DFAUo&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀기 전 생각 1. 한 변에 들어가는 글자수는 N/4 2. 위의 그림처럼 마지막 것이 앞으로 오고 한 변에 들어가는 글자수 (N/4)를 기준으로 문자열을 자른다. 즉 마지막 것을 앞으로 새로 넣고, 기존에 있는 것을 삭제한다. 3. 자른 값들 (즉, 생성된 문자열들)은 Arraylist에 저장한다. 이때, 중복확..

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yGVsKC0YDFAUx SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 제약 사항 1 ≤ N ≤ 500 1 ≤ M ≤ 2^31 – 1 동작 순서 N = 2, M=5 일 때 Tiles에 입력받은 N값들을 저장한다. rects 리스트에 사용할 타일을 add한다. 주어진 타일(m)은 5이기 때문에 처음에는 (m,m) 즉 (5,5) 타일 add한다. (rects 리스트에 들어가는 것은 사각형의 W,H 이다. (w,h)를 나타낸다.) 이제 입력받은 N값들 하나씩 꺼내..

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 주어진 제약 사항 1 ≤ N ≤ 4 2 ≤ W ≤ 12 2 ≤ H ≤ 15 풀기 전 생각 Q. 어디서 구슬을 떨어트려야 최대로 벽돌이 깨지는가? -> 그럼 어디서 구슬을 떨어트려야 하는가?? => 어디서 최대로 벽돌이 깨지는지 모르니까 하나씩 해보자!! -> 구슬은 최대 4개까지 떨어지고 W는 최대 12이다. 최악일 경우 12^4 = 20,736번 케이스를 돌아야 한다. -> 이 정도는 ..

문제 철수는 마을의 여러 건축물들을 폭파해달라는 요청을 받았다. 이에 건축물들을 하나씩 폭파하려 한다. 일반적으로, 하나의 건물을 폭파하기 위해서는 다이너마이트 하나가 필요하다고 하자. 철수의 마을에 있는 건축물들 사이에는 특별한 단방향 통로가 존재한다. 하나의 건축물을 폭파시킬 경우, 이 단방향 통로로 인하여 상황이 약간 복잡해지는데, 이는 건물 A에서 건물 B로 통로가 이어져 있을 경우, 건물 A를 폭파시키면 건물 B 역시 폭파된다는 것이다. 이유인 즉슨, 단방향 통로가 지하에 매설되어 있기 때문에, 지하의 통로가 무너지면서 건물 B가 함께 무너진다. 철수의 마을에 존재하는 건축물의 개수가 주어지고, 이 건축물들 사이의 단방향 통로가 주어질 때, 최소 몇 개의 다이너마이트가 있어야 모든 건축물을 폭파..

문제 SCC (Strongly Connected Component)란, 방향성 그래프가 주어질 때 정점을 여러 집합으로 나누는 기법으로써, 같은 집합에 속해있는 정점끼리는 서로 왔다갔다 할 수 있어야 한다. 아래 그림은 그래프의 예제와, 이 그래프에서 SCC를 구한 예제이다. 아래 그림처럼, 정점을 {1, 2, 5}, {6, 7}, {3, 4, 8} 의 3개의 집합으로 나누게 되면, 같은 집합에 속한 정점들끼리는 모두 왔다갔다 할 수 있다. 그래프가 주어질 때, SCC를 구하였을 때 얻을 수 있는 정점의 집합의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진..