본문 바로가기

분류 전체보기46

[개념 정리] 순열, 조합, 부분집합 이번 글에서는 모든 경우의 수를 탐색하는 완전탐색 기법에서 순열과 조합 그리고 부분집합에 대한 구현 방법을 정리해보고자 합니다. 순열 순열은 N개의 원소 중에서 R개의 원소를 통해 순서를 가진 부분집합을 만드는 경우의 수입니다. 순열은 재귀 함수를 통해 모든 경우의 수를 구할 수 있습니다. 재귀함수를 사용하게 되면 이번 순서의 원소를 사용하는지 체크하는 과정이 필요한데, 이 과정은 boolean 배열을 통해 체크하거나 비트 마스킹을 통해 구현할 수 있습니다. Boolean 배열 사용 permutationByBoolean(0); static void permutationByBoolean(int cnt) { if (cnt == N) { printPermutation(); return; } for (int i.. 2021. 2. 19.

[Kubernetes Best Practice] 3. 모니터링과 로깅 이 글은 Kubernetes Best Practice를 읽고 개인적으로 중요하다고 생각하는 부분과 잘 모르는 부분에 대해 공부한 내용을 작성한 글입니다. 모든 내용은 책에 포함되어 있는 내용을 기반으로 작성하였으며 자세한 내용이 궁금하신 분들은 책을 구매해서 읽는 것을 권장드립니다. 최근 서비스 메시에 대해 알아보거나 쿠버네티스를 사용하고 공부하면서 가장 많이 들었던 생각은 이 방법이 최선인가? 라는 생각이었습니다. 이에 대한 궁금증을 해결하는데 도움이 될만한 책을 발견해서 읽어보고자 합니다. 메트릭 vs 로그 모니터링? 로깅? 메트릭? 로그? 인턴을 진행했을 때 이러한 용어들이 어떤 차이점을 가지고 있는지 헷갈렸던 기억이 있습니다. 책에서는 메트릭과 로그는 상호보완적인 관계이지만 사용 목적에 있어 차이.. 2021. 2. 14.

[백준] 9251. LCS 문제 풀이 하루종일 이 문제만 붙들고 있었던 것 같다. 처음 시도했던 방법은 일차원 배열을 통해 메모이제이션을 수행하고자 했다. 하지만 일차원 배열을 사용하는 경우에는 같은 문자가 여러번 등장할 경우에 대해서 잘못된 최대값을 얻는 경우가 발생한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int[][] cache; public static void main(String[] args) thro.. 2021. 2. 10.

[백준] 11053. 가장 긴 증가하는 부분 수열 문제 풀이 처음으로 접근했던 방법은 index를 통해 메모이제이션을 수행하려고 했다. 하지만 같은 수가 존재할 경우 갱신하는 과정에서 일관된 규칙을 찾을 수 없었고 이를 커버하기 위해 index가 아닌 실제 값을 통해 메모이제이션을 수행했다. 앞에서부터 순서대로 해당 값 A를 찾고 1 ~ A-1까지의 최대 길이 + 1로 증가하는 부분 수열의 최대 길이를 저장했다. import java.util.Scanner; public class Solution11053 { static Scanner sc = new Scanner(System.in); static int[] cache = new int[1001]; public static void main(String[] args) { int N = sc.nextIn.. 2021. 2. 10.

[백준] 9663. N-Queens 문제 풀이 처음에는 완전탐색으로 접근했었지만 시간초과로 실패하였다. 그래서 경우의 수를 줄이기 위한 방법을 고민했고 모든 행/열이 아닌 어차피 한 행에는 하나의 Queen만 올 수 있다는 점을 이용해 재귀함수의 깊이를 줄일 수 있었다. import java.util.Scanner; public class NQueens { static Scanner sc = new Scanner(System.in); static int result = 0; static int N = 0; static boolean[][] check; static int[] dx = {0, 0, -1, 1, 1 ,1 , -1, -1}; static int[] dy = {-1, 1, 0 ,0, -1, 1 , 1, -1}; public sta.. 2021. 2. 5.

[백준] 2493. 탑 문제 풀이 처음에는 배열의 끝에서부터 탐색을 시작해서 자신보다 큰 값을 만날 때까지의 모든 요소들을 같이 초기화하는 방식을 생각했다. 하지만 이 경우에는 아래 방향의 화살표 모양(ex. 5 2 1 3 4) 경우를 커버하지 못해서 다른 방법을 생각해봤다. 최종적으로는 스택 두개를 사용해서 하나의 스택(A)은 입력 순서대로 들어가 있고 나머지(B)는 꺼낸 값을 저장했다. 꺼낸 값을 B 스택에 넣기 전에 B스택의 top이 더 작은 경우에는 꺼낸 값의 인덱스가 top의 결과가 된다. 인덱스를 찾는 방법에 대해서는 Map을 통해서 초기 입력시 해당 값을 key로 인덱스를 value로 저장해서 O(1)로 찾을 수 있도록 했다. Map을 통한 구현 import java.io.BufferedReader; import .. 2021. 2. 4.

이전 1 2 3 4 5 6 7 8 다음

티스토리툴바