본문 바로가기

전체 글46

[개념정리] 스위핑 알고리즘 스위핑 알고리즘이란 특정 기준에 따라 정렬된 순서대로 문제를 처리하는 방법이다. 스위핑 알고리즘을 사용해야하는 문제들의 특징은 러프한 방법 (일반적으로 O(N^2)의 시간복잡도를 갖는 방법)으로는 해결이 불가능하며, DP를 사용하기에는 메모이제이션 해야할 수가 너무 많은 경우가 일반적이다. 스위핑 알고리즘으로 문제를 풀 경우, 해당 시간 복잡도는 정렬에서 발생하는 O(NlogN)안에서 해결된다. 백준 - 8982. 사냥꾼 일반적인 방법으로 풀게되면 O(N*M)의 시간복잡도를 가지게 되고 시간초과가 발생한다. 그렇다고 좌표에 대한 정보를 기억할 수도 없기 때문에 스위핑 알고리즘을 통해 해결해야 한다. 먼저, 사대와 동물을 모두 x축 순서로 정렬하고 동물을 기준으로 사냥이 가능한지 확인한다. 확인 과정은 동.. 2021. 2. 26.

[Kubernetes Best Practice] 5. 지속적 통합, 테스트, 배포 이 글은 Kubernetes Best Practice를 읽고 개인적으로 중요하다고 생각하는 부분과 잘 모르는 부분에 대해 공부한 내용을 작성한 글입니다. 모든 내용은 책에 포함되어 있는 내용을 기반으로 작성하였으며 자세한 내용이 궁금하신 분들은 책을 구매해서 읽는 것을 권장드립니다. 최근 서비스 메시에 대해 알아보거나 쿠버네티스를 사용하고 공부하면서 가장 많이 들었던 생각은 이 방법이 최선인가? 라는 생각이었습니다. 이에 대한 궁금증을 해결하는데 도움이 될만한 책을 발견해서 읽어보고자 합니다. 컨테이너 이미지 경량화 이미지를 빌드할 때 이미지의 크기를 최적화하기 위한 고려가 필요합니다. 이미지의 크기가 작을수록 registry에서 다운 받는 시간이 감소하어 배포 과정에서 소요되는 시간이 줄어들뿐만 아니라.. 2021. 2. 25.

[Kubernetes Best Practice] 4. 설정, 시크릿, RBAC 이 글은 Kubernetes Best Practice를 읽고 개인적으로 중요하다고 생각하는 부분과 잘 모르는 부분에 대해 공부한 내용을 작성한 글입니다. 모든 내용은 책에 포함되어 있는 내용을 기반으로 작성하였으며 자세한 내용이 궁금하신 분들은 책을 구매해서 읽는 것을 권장드립니다. 최근 서비스 메시에 대해 알아보거나 쿠버네티스를 사용하고 공부하면서 가장 많이 들었던 생각은 이 방법이 최선인가? 라는 생각이었습니다. 이에 대한 궁금증을 해결하는데 도움이 될만한 책을 발견해서 읽어보고자 합니다. ConfigMap & Secret 컨테이너의 높은 이식성을 뒷받침하는 특성은 애플리케이션과 환경의 분리 즉, 런타임에 설정 데이터를 환경 변수나 볼륨 마운트를 통해 주입할 수 있다는 점입니다. 쿠버네티스는 이를 달.. 2021. 2. 22.

[백준] 1987. 알파벳 풀이 모든 경우의 수를 DFS로 탐색하며 이전에 방문한 알파벳인 경우 가지치기를 진행하엿다. 이 때 이전 방문 노드를 확인하는 방법으로 초기에는 ArrayList를 사용했지만 시간초과가 발생하였고 이에 대한 이유가 ArrayList의 remove 과정에서 O(N)의 시간복잡도가 발생했기 때문이라고 판단하였다. 그래서 이전 방문 알파벳을 유지하는 방식을 StringBuilder를 사용하였고 마지막 인덱스를 삭제함으로써 시간 초과를 해결하였다. 하지만 이 방법도 너무 느려서 이를 확인하는 방법으로 비트마스킹을 사용하였고 모든 경우에 distance를 비교하는 것이 아니라 유망하지 않은 경우에만 distance를 비교하도록 개선하였다. 비트마스킹으로는 현재 알파벳 - 'A'를 해줌으로써 포함 여부를 확인하였다.. 2021. 2. 19.

[백준] 3109. 빵집 풀이 DFS를 통해 탐색을 진행할 때 최대값을 찾는 경우는 대부분 모든 경우의 수를 확인해야 하기 때문에 유망하지 않은 경우 가지치기하는 백트래킹 방법을 사용할 수 없다. 하지만 이 문제는 시작 점은 가장 위에서부터 연결할 수 있는 경우에는 연결하는 경우가 최선의 방법이 되는 그리디한 접근 방식을 사용하였고 이를 통해 유망하지 않은 경우 탐색을 종료하는 경우 되돌아가는 백트래킹 방식을 사용하였다. 첫번쨰 열의 1번쨰 행부터 탐색을 진행하고, 만약 C번째 행에 도착했다면 이번 시작 위치에서의 탐색을 종료한다. 다음 위치도 동일하게 진행하는데 만약 실패한다고 하더라도 방문한 위치에 대한 체크를 되돌리지 않는다. 왜냐하면 해당 위치에서 파이프를 완성하지 못했다고 하더라도 뒤 선택지에서 해당 방향은 동일하게 실.. 2021. 2. 19.

[백준] 15686. 치킨 배달 풀이 얼핏 보면 경우의 수가 많아보이지만 결국 따져야 하는 경우의 수는 치킨집의 개수 중에 M개의 조합을 뽑는 경우다. 모든 경우에 대해 집과의 거리를 구하고 최소값을 구하는 방식으로 진행하였다. Next Permutation 방법을 통해서 조합을 생성했고 이전 최소값을 넘어서는 경우 거리 계산을 중지하고 리턴되도록 구현하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; public class Solution15686 { static class Pair { int x = 0; int y =.. 2021. 2. 19.

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

티스토리툴바