본문 바로가기

전체 글159

[알고리즘] 장애물이 있을 때 최단거리 길 찾기 1. 문제 상황 설명 직사각형 형태의 필드에 시작위치에서 목표 위치로 가는길에 장애물이 있는경우 아래 예시 문제에서는 귀신이 따라와서 귀신보다 빨리 가야 한다. 즉 귀신보다 목표 위치가 가까워야 하며, 장애물까지 고려한경우 귀신보다 변위가 짧아야 한다. 처음에는 모든 경우를 계산하도록 재귀함수를 만들었으나 단순히 Queue를 이용하여 해결하였다. 시작점에서 상하좌우로 퍼져나간다. 퍼져나간 노드에서 다시 4방향으로 퍼져나간다. 한번 지나간 노드는 다시 지나가봤자 변위 손해이며 최단거리가 아니다. 2. 코드 작성 public class Main { public static void main(String[] args) throws IOException { //문제를 입력 받는다. BufferedReader b.. 2024. 2. 2.
[알고리즘] 플로이드 와샬(Floyd-Warshall) 1. 플로이드 와샬 알고리즘 그래프의 모든 노드에서 다른 모든 노드까지 최단거리를 구하는 알고리즘 O(V^3)의 시간복잡도를 가졌다. 코드를 보면 알겠지만 3중 포문이 돌아간다. 매커니즘 j노드에서 k노드를 바로 가는 것과 i를 거쳐서 가는 것 중 비교를 계속 진행한다. 2. 문제와 코드 프로그래머스 배달 문제 참고 class Solution{ public int solution(int N, int[][] road, int K) { int answer = 0; //거리 비용을 2차원 배열에 정리 int[][] costs = new int[N][N]; for (int i = 0; i < costs.length; i++) { Arrays.fill(costs[i], 500001); costs[i][i] = 0.. 2024. 1. 31.
[알고리즘] 다익스트라(Dikstra Algorithm) 1. 다익스트라 알고리즘 그래프의 한 노드에서 각 모든 노드까지 최단거리를 구하는 알고리즘 음의 가중치를 가지면 최소 비용의 음의 무한대 발산, 그리디 알고리즘 적용 불가능 등이 발생. 초기 모델은 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐 등을 이용한 고안된 알고리즘이 탄생했고, 현재는 O((V+E)log V)의 시간복잡도를 가지고 있다(만일 연결 그래프라면 O(ElogV)까지 시간 복잡도를 줄일 수 있다고 한다). 일반적으로는 그래프가 희소 그래프인 경우에 우선순위 큐를 이용하는 것이 낫다고 한다. 연결 그래프 : 모든 두 꼮짓점 사이에 경로가 존재하는 그래프 희소 그래프 : 밀집 그래피의 반대 밀집 그래프 : 간선의 수가 최대에 가까운 그래프 : 간선 개수 = 정점의 개수 ^2와 근사하다.. 2024. 1. 31.
[프레임워크] .NET 이란? 1. .NET 이란? 마이크로소프트에서 개발한 무료, 오픈소스, 크로스플랫폼 프레임워크 웹 어플리케이션, 데스크탑 어플리케이션, 게임, 모바일 어플리케이션 등 다양한 종류의 어플리케이션 개발 가능 C#, F3, Visual Basic .NET 등 다양한 언어 지원 대규모 개발자 커뮤니티와 다양한 미리 제작된 구성요소 라이브러리를 보유하여 개발을 더욱 빠르고 쉽게 해준다. 코드 액세스 보안 및 샌드박스 환경과 같은 기능을 제공하여 어플리케이션 보안 향상 Window, Linux 및 macOS를 포함한 다양한 플랫폰에서 실행될 수 있도록 지원 2. .NET SDK .NET 스프트웨어 개발 키트를 의미 .NET 어플리케이션을 개발, 테스트 및 배포하기 위해 필요한 도구, 라이브러리 및 런타임 환경을 제공 .N.. 2023. 12. 18.

티스토리툴바