본문 바로가기

분류 전체보기46

[개념 정리] 투 포인터 최근 알고리즘을 풀면서 시간 초과와 예외처리로 인해 상당히 애를 먹었던 문제가 있다. 해당 문제의 다른 풀이를 찾아보니 투 포인터 알고리즘을 통해 간단하게 구현할 수 있다는 점을 알았고 이에 대해 정리해보고자 한다. 투 포인터 알고리즘은 하나의 배열에서 두 개의 인덱스 포인터를 조작하는 알고리즘을 의미한다. 문제를 예시로 들어서 설명하면 다음과 같다. 백준 - 2467. 용액 이 문제에서 0과 가장 가까운 거리의 합을 가지는 두 원소를 구하는 방법은 먼저 O(N^2)의 시간복잡도를 가지는 방법이 존재한다. 하지만 문제처럼 N의 크기가 O(N^2)으로 해결할 수 없는 경우에 투 포인터 알고리즘을 사용하면 O(N)에 해당 값을 구할 수 있다. (이 문제는 정렬이 필요하기 때문에 전체 문제의 시간복잡도는 O(.. 2021. 4. 1.

[백준] - 2206. 벽부수고 이동하기 문제 풀이 이 문제는 예전에 BFS를 한창 풀었을 때에는 못 풀었던 문제였는데 이와 유사한 문제인 1600. 말이 되고픈 원숭이문제를 풀고 영감을 얻어서 다시 도전했더니 쉽게 풀렸다. 이 문제가 일반적인 BFS보다 까다로운 이유는 어떤 좌표에 올 수 있는 경우의 수가 2가지(이전에 벽을 부신 경우, 이전에 벽을 부수지 않은 경우)라는 점이다. 따라서 2차원 방문 배열로는 처리가 불가능하고 3차원 배열을 사용하여 문제를 해결하였다. 3차원 배열에서 0번쨰 인덱스는 벽을 이미 부수고 온 경우, 1번째 인덱스는 벽을 아직 부수지 않은 경우이다. bfs를 진행하며 다음의 3가지 경우에 대해서 처리해주었다. 현재 벽을 부술 수 있는 기회가 남아있고 다음 방문할 좌표가 벽인 경우, 기회를 소진하고 벽을 방문 기회가.. 2021. 3. 24.

[백준] - 1277. 발전소 설치 문제 풀이 1번 발전소부터 N번째 발전소까지의 최소 비용을 구하는 문제이기 때문에 다익스트라 알고리즘을 사용하여 해결하였다. 먼저 각 발전소의 좌표를 저장(plant)하고, 연결되어 있는지 여부를 저장(connected)하였다. 다음으로 다익스트라 알고리즘을 수행하기 전, 1번부터 각 정점까지의 거리를 나타내는 distance 배열을 연결된 경우에는 0, 연결되지 않은 경우에는 INF로 초기화해주었다. 다익스트라 알고리즘을 수행하면서 가중치를 더해주는 부분은 각 좌표간의 거리이기 떄문에 두 점 사이의 거리를 구하는 공식을 통해 구했다. 추가적으로 인접한 행렬에서 찾는 일반적인 경우와 달리 모든 발전소의 거리를 계속해서 갱신해 줄 필요가 있기 때문에 1~N까지 자기 자신을 제외하고 거리를 갱신해주었다. 풀.. 2021. 3. 24.

[Kubernetes Best Practice] 10. 파드와 컨테이너 보안 이 글은 Kubernetes Best Practice를 읽고 개인적으로 중요하다고 생각하는 부분과 잘 모르는 부분에 대해 공부한 내용을 작성한 글입니다.모든 내용은 책에 포함되어 있는 내용을 기반으로 작성하였으며 자세한 내용이 궁금하신 분들은 책을 구매해서 읽는 것을 권장드립니다. 최근 서비스 메시에 대해 알아보거나 쿠버네티스를 사용하고 공부하면서 가장 많이 들었던 생각은 이 방법이 최선인가? 라는 생각이었습니다. 이에 대한 궁금증을 해결하는데 도움이 될만한 책을 발견해서 읽어보고자 합니다. Pod의 보안을 강화할 수 있는 쿠버네티스 API에는 PodSecurityPolicy와 RuntimeClass라는 2가지 방법이 존재합니다. PodSecurityPolicy PodSecurityPolicy는 클러스터.. 2021. 3. 23.

[개념 정리] 최단 거리 알고리즘 - 다익스트라 가중치가 없는 그래프의 최단거리 문제는 대부분 BFS로 해결할 수 있습니다. 하지만, 간선에 가중치가 존재한다면 BFS가 아닌 최단거리 알고리즘을 통해 접근해야 합니다. 일반적으로 가중치 그래프의 최단거리 문제는 다음과 같은 유형이 존재합니다. 두 정점 간의 최단 거리를 구하는 문제 하나의 정점에서 다른 모든 정점과의 최단거리를 구하는 문제 하나의 정점으로 가는 모든 최단 경로를 구하는 문제 정점 간의 모든 최단 경로를 구하는 문제 - 플로이드-와샬 저번 글에서는 4번 유형을 해결하기 위한 플로이드-와샬 알고리즘에 대해 알아보았습니다. 이번 글에서는 2번 유형을 해결할 수 있는 다익스트라 알고리즘에 대해서 알아보겠습니다. 다익스트라 알고리즘은 간단하게 설명하면 시작 정점에서 거리가 최소인 정점을 선택해 .. 2021. 3. 22.

[개념 정리] 최단거리 알고리즘 - 플로이드 와샬 가중치가 없는 그래프의 최단거리 문제는 대부분 BFS로 해결할 수 있습니다. 하지만, 간선에 가중치가 존재한다면 BFS가 아닌 최단거리 알고리즘을 통해 접근해야 합니다. 일반적으로 가중치 그래프의 최단거리 문제는 다음과 같은 유형이 존재합니다. 두 정점 간의 최단 거리를 구하는 문제 하나의 정점에서 다른 모든 정점과의 최단거리를 구하는 문제 하나의 정점으로 가는 모든 최단 경로를 구하는 문제 정점 간의 모든 최단 경로를 구하는 문제 이 중 4번을 해결하기 위한 플로이드-와샬 알고리즘에 대해 알아보고자 합니다. 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘은 모든 정점간의 최단경로를 구하는 알고리즘입니다. 앞으로의 설명에서 사용될 그래프는 다음과 같은 가중치를 가지고 있습니다. 초기 가중치 값을 저장하는 .. 2021. 3. 16.

이전 1 2 3 4 5 ··· 8 다음

티스토리툴바