적자 생존 (Write, Survive!)

백준 - 좌표 정렬하기 문제 파악좌표의 개수 n 과 x, y 두 좌표가 주어진다.이를 x 기준으로 오름차순으로 정렬하는데 두 수가 같다면 y 를 기준으로 오름차순으로 정렬하는 문제접근 방법완전히 이상한 접근을 했다….배열에 저장하는 것까지 했는데 완전탐색으로 돌리려다가 이중 for문에 if문도 많아지고, 초기 비교값도 넣어야 하고 처음 정렬에 성공했다쳐도 이미 정렬된 값이랑 새로운 값이랑 비교도 해야하는 문제 때문에 이 방법은 답이 없다고 판단했다.해시테이블 + StringBuilder 를 이용해서 문자로 정렬해서 비교할까? 싶었는데 이것도 key 중복이랑 y좌표 기준 정렬 때문에 불가능으로 판단했다.마지막으로 스택을 이용해서 정렬하려고 했는데 1번 방법과 같은 이유로 실패했다.그냥 sort 이용해서 정..

Coin Change - LeetCode문제 파악coins에는 현재 가지고 있는 동전이 들어있다. amount는 만들어야 하는 금액인데, 주어진 동전들로 이 금액을 만드는 문제 amount가 0이면 0, 주어진 동전들로 만들 수 있는 금액이 아니라면 -1을 반환한다. (coin이 0인 경우는 없다.)접근 방법0원부터 11원까지 만들 수 있는 동전의 최소 필요 수를 dp에 저장한다.11원을 만들려면? 3가지 선택지가 있음. 10원 + 1원, 6원 + 5원, 9원 + 2원이 된다.이 중에서 동전이 최소로 드는 경우를 찾는다.dp에는 필요한 최소 동전 수가 저장되어있다.점화식으로 나타내면 $dp(i) = min(dp(i-coin) + 1)$ 이 된다. 내가 처음에 실수한 포인트는 쪼개면서 amount에서 바로..

프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 파악연결된 컴퓨터끼리 하나의 네트워크라고 했을 때 전체 컴퓨터 중에서 네트워크의 개수를 구하는 문제이렇게 그래프가 주어진다면 네트워크는 2개이다. 입출력 예ncomputersreturn3[[1, 1, 0], [1, 1, 0], [0, 0, 1]]23[[1, 1, 0], [1, 1, 1], [0, 1, 1]]1접근 방법BFS, DFS를 실행해서 그래프 탐색을 진행한다.모든 노드에 대해서 진행하여 네트워크가 발견될 때마다 카운팅나는 DFS로 실행했기 때문에 DFS 로직을 구현함현재 노드 방문다음 노드 탐색방문하지 않았으면 재귀로 dfs 실행코드 구현import j..

백준 2178 - 미로탐색문제 파악N x M 미로가 주어지고 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸(1,1)에서 출발해서 (N,M)까지 도착할 때 지나야하는 최소의 칸 수를 구하는 문제 (1,1)에서 (N,M)까지의 최소 거리를 구하는 문제 = BFS격자 배열이 있고, 최소 거리를 구하는 걸로 보아 암시적 그래프 문제이다. 입출력 예시첫 줄 : N, MN개의 줄 : 미로의 정보4 6101111101010101011111011접근 방법BFS를 사용하여 풀면 간단하다.암시적 그래프에서 BFS가 즉, 최소 거리를 구해주는 과정이기 때문에! 방법은 두 가지가 있다.방문 배열 자체를 distance로 하여 거리를 저장하면서 가는 방법거리를 큐에 같이 추가하여 방문할 때 더하는 방법나는 2번을 채택하여..

프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 파악N 개의 마을이 주어지고, 양방향으로 통행할 수 있음도로를 지날 때 걸리는 시간이 주어질 때, 1번 마을의 음식점에서 각 마을로 배달을 함.N개의 마을 중에서 K시간 이하로 배달이 가능한 마을에서만 주문을 받음. 마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 가중치가 있는 그래프이며 도착 지점까지의 최소 비용(시간)을 구하는 문제 → 다익스트라!! 제한사항마을의 개수 N은 1 이상 50 이하의 자연수입니다.road의 길이(도로 정보의 개..

프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 파악하루에 한 번씩 탐험할 수 있는 던전이 여러 개 존재함.던전을 탐험하기 위해서는 최소 필요 피로도와 소모 피로도가 존재함.최소 필요 피로도는 던전을 탐험하기 위한 입장 조건이고 소모 피로도는 탐험을 마치고 나면 차감되는 피로도이다.이걸 고려해서 최대 몇 개의 던전을 탐험할 수 있는지 구하는 문제 입출력 예kdungeonsresult80[[80, 20], [50,40], [30,10]]3 입출력 예시 설명현재 피로도는 80입니다. 만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필..

프로젝트 때문에 알고리즘을 놓으면 안될 것 같아서 다시 풀어봤다. 문제 파악N * M 맵이 주어지면 도착지점까지의 최단거리를 구하는 문제하지만 딱 한 번 벽을 부술 수 있음접근 방법프로그래머스 보물지도 문제에서 내가 예전에 틀렸을 때의 상황이랑 똑같다.구멍을 무시하고 통과하는 코드를 작성했는데 구멍=벽일뿐 동일한 상황이라서 그대로 작성했다.일반탐색 부분벽을 부술 때 탐색, 일회성 사용이기 때문에 큐에 같이 추가하고 3차원 배열로 사용 여부도 추가함.시작점도 포함이라 거리가 1부터 시작해야한다,, → 이거 몰라서 계속 1 적게 나왔다…코드 구현import java.util.*;import java.io.*;public class Main { public static void main(String[] a..

📚 투 포인터(Two Pointer)투 포인터(Two Pointer)는 리스트(배열)에서 두 개의 포인터를 이용해 조건을 만족하는 구간이나 값을 효율적으로 탐색하는 알고리즘이다.서로 다른 두 개의 포인터를 이동시키며 문제의 조건을 만족하는 부분을 탐색한다.주로 정렬된 배열에서 구간합, 쌍(pair), 부분 수열 등을 찾을 때 사용된다.투 포인터 사용의 가장 큰 장점은 시간복잡도 $O(n^2)$의 문제를 $O(n)$으로 해결할 수 있다는 점이다.배열 기반 (Array-based)배열의 양 끝이나 시작점에서 출발하는 두 개의 포인터(start, end)를 이동시킨다.일반적으로 while(start 혹은 while(end 같은 조건으로 순회한다.조건에 따라 한 쪽 포인터만 이동시키거나두 포인터를 동시에 ..

📚 다익스트라 알고리즘 (Dijkstra)가중치 그래프에서 적용할 수 있는 알고리즘이다.가중치가 없는 그래프일 경우에는 모든 가중치가 동일하다고 보고 최단 경로를 효율적으로 보지만, 가중치가 있는 그래프에서는 가중치를 계산했을 때 도착지점까지의 최소 비용이 드는 경로를 효율적인 경로라고 판단한다.예를 들어, 가중치가 없을 때 D까지의 최단 경로는 A->B->E->D와 A->B->C->D는 차이가 없다.하지만 가중치가 주어지고 최소 비용 경로는 A->B->E->D가 더 효율적이다.이러한 가중치 문제를 해결하기 위해서 다익스트라 알고리즘을 사용한다.다익스트라 알고리즘은 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최소 비용을 return 하는 알고리즘원리시작점의 라벨은 0, 나머지 점들을 ∞로 초기화..