오늘 알고리즘 문제는 어제보다 어려웠다. 백트랙킹을 dfs(재귀함수)로 풀었는데 개인적으로 재귀함수를 구현하는 게 너무 어려워서 더 어렵게 느껴진 것 같다. 그 외에도 수학(구현) 문제가 있었는데 생각해야하는 부분이 좀 있어서 어려웠던 것 같다. 그래도 무탈하게 팀 스터디 진행했다! 조금씩 알고리즘 실력이 늘어나고 있다고 생각한다. 남은 주차들고 화이팅!
알고리즘 기술 매니저님 피드백
- bufferedWriter -> thread safe
- syncronized 처리되어있음! -> 로직이 좀 무거움
- stringBuilder 사용하느 게 더 빠름
- 조금 더 성능 개선 시키고 싶으면 stringBuilder 사용하도록!
- stream 사용하면 가독성 좋을 거 같긴 함
- 함수에서 넘겨주는 거 많을 때 그냥 static으로 변수 빼주는 것도 추천 (취향차이)
- 문제가 잘 안 풀릴 때 예시를 보면서 해봐라
- 필요없는 입력값은 날려도 된다 br.readLine()
- valueOf() vs parseInt()
valueof: primtive 타입 (Int) 반환
parseInt: 래퍼 객체 반환
- stream 정렬 -> team sort: Insertion sort와 Merge sort를 결합한 알고리즘
- 오늘 진행된 강의에서 학습한 내용은 무엇인가요?
문자열
- 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?
백트래킹에 대해 알게 되었다.
백트래킹
- 해를 찾아가는 도중에 지금의 경로가 해가 되지 않을 것 같으면 그 경로를 더 이상 가지 않고 되돌아 간다.
- 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다.
- 즉 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.
- 주로 문재 풀이에서는 재귀로 모든 경우의 수를 탐색할 때 답이 될 수 없는 상황을 정의하고 그 경우 탐색을 중지시킨 뒤 그 이전으로 도아가서 다시 다른 경우를 탐색하도록 구현을 한다.
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static int[] sequence;
private static boolean[] visited;
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
sequence = new int[m]; visited = new boolean[n+1];
dfs(n, m, 0);
System.out.println(sb.toString());
}
public static void dfs (int n, int m, int d) {
if (d == m) {
for (int num : sequence) {
sb.append(num).append(" ");
}
sb.append("\n");
return;
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
visited[i] = true;
sequence[d] = i;
dfs(n, m, d+1);
visited[i] = false;
}
}
}
}
댓글