Algorithm

개발만 하다가 오랜만에 알고리즘 문제를 풀었다. 문제를 2시간이나 풀었다..알고리즘 근육을 다시 좀 키워야할 필요성을 느꼈다. 풀이 전략 요약하자면 지도에서 땅(1) 과 바다(0) 가 주어진다. 상/하/좌/우 + 대각선 총 8방향으로 연결된 1들은 같은 섬으로 간주한다. 여러 개의 테스트케이스가 입력되고, w=0, h=0이면 종료한다. 각 테스트케이스마다 섬의 개수를 출력한다. 늘 그렇듯 흔히 하는 방식으로 먼저 static 변수를 생성해준다. 지도를 2차원 배열에 저장하고 방문 여부 체크, 전체 좌표 순회, 모든 좌표 탐색 후 개수 출력! 이렇게 접근했다. 연결된 땅(1)을 하나의 섬으로 세는 건 그래프 탐색 문제고 DFS를 써야 할지 BFS를 써야 할지 고민을 했는데 한 방향으로 깊게 들어..

오늘은 그리디 알고리즘의 대표 문제 중 하나인 회의실 배정 문제를 풀어봤다. 풀이 전략 이 문제는 모든 회의를 탐색하며 최적의 조합을 찾는 완전탐색으론 시간 초과가 난다. 따라서 그리디 알고리즘을 사용해야 한다. 왜 그리디일까? 우리는 최대한 많은 회의를 배정하고 싶다.가능한 한 빨리 끝나는 회의를 먼저 배정해야 뒤에 올 수 있는 회의의 수가 많아진다. 핵심은 끝나는 시간이 빠른 회의부터 정렬하고 겹치지 않으면 채택하는 방식으로 회의를 골라나가는 것이다. 풀이 순서 회의 정보를 배열에 저장 -> 종료 시간 기준으로 정렬 -> 현재 회의의 시작 시간이 이전 회의의 종료 시간 이상이면 채택-> 채택된 회의의 카운트 증가. 이제 코드를 보자. 코드 풀이 int N = Integer.pars..

오늘은 백준 1697번 숨바꼭질 문제를 풀어보겠다. 수빈이는 현재 위치 N에 있고, 동생은 위치 K에 있다. 수빈이는 1초에 한 번씩 다음 세 가지 방법으로 이동할 수 있다: X - 1 (1초 후 왼쪽으로 이동) X + 1 (1초 후 오른쪽으로 이동) X * 2 (1초 후 순간이동) 수빈이가 가장 빠르게 동생에게 도달하는 시간을 구해보자. 풀이 전략 이 문제는 1차원 수직선 문제이다. x,y 같은 좌표가 아닌 숫자 하나로만 위치를 표현하면 되는 문제이다. 모든 이동의 비용이 동일하고 최단 시간을 구하는 문제이므로 BFS를 사용해야 한다. BFS 사용 이유 DFS는 한 경로를 끝까지 탐색하기 때문에 더 짧은 경로가 있더라도 먼저 도착하지 못할 수 있다. BFS는 같은 거리(=시간) 단위로 전방위적으..

이 문제는 대표적인 다익스트라 문제로 유명한 최단경로 문제이다. 우선순위 큐에 대한 개념을 많이 까먹고 있었는데 이 문제를 통해 다시 복습할 수 있었고 다익스트라에 대한 공포를 어느정도 걷을 수 있게 된 문제였다. 풀이 전략 문제가 길고 복잡해질수록 변수와 초기값을 명확히 정의하는 것이 중요하다고 판단했다. 어떤 데이터 구조를 사용할지, 어디에 어떤 값을 저장해야 하는지, 시간 복잡도를 고려한 최적의 알고리즘을 적용할지, 시간 복잡도를 고려해서 어떤 알고리즘을 다익스트라 구현에 생각할지 생각했다. 인접 행렬과 인접 리스트로 그래프를 표현할 수 있는데 정점이 많은 경우 보통 인접 리스트를 사용해서 메모리 절약과 탐색 속도를 높이는 것이 효과적이므로 인접 리스트를 사용하기로 했다. 그리고 모든 가중치가 ..

재밌는 문제이고 그리디 알고리즘을 모르는 상태에서 접근하려다보니 어려움을 느꼈던 문제였다. 로직을 어떻게 생각해야 할지가 어려운 문제였다. 구현 자체는 쉬운 편이었다. 풀이 전략 예제를 보고 어떻게 풀이를 할 지 생각해보자. A를 B로 바꾸는데 몇 번의 연산이 필요한지 카운트하는 문제이다. 조건에 맞추어 2에서 162가 되기 위해선 2에서 2를 곱해서 44에서 2를 곱해서 88의 오른쪽에 1을 추가해서 8181에 2를 곱해서 1624번의 연산이지만 출력 조건에 +1을 해줘야 하니까 count 기준을 1부터 시작.총 5만큼 카운트가 되어야 하고 count 값은 5여야 한다. 이렇게 생각하고 문제를 들어다보았다. 이제 접근해보자. 두 연산 중 하나는 A를 두 배로 만들고 다른 하나는 A 뒤에 1을 ..

이번 문제는 선택한 노드 간의 촌수를 구하는 문제이다. 간단하면서도 재밌어서 풀이 과정을 공유하겠다. 요즘 레이팅이 실버 3까지 올랐는데 개발 공부에 집중하다보니 알고리즘에 집중을 못한 것 같아서 풀어보게 되었다. 다익스트라 알고리즘도 공부중인데 조만간 포스팅하겠다. 풀이 전략 인접 리스트를 사용하는게 좋아보였으나 개인적으로 인접 행렬이 마음이 편하고 재밌어서 인접행렬로 하게 되었다. 최적의 풀이 방법을 찾으려면 다양한 방법으로 수행해야 하므로 더 노력해야겠다. 한 지점에서 다른 지점으로 가는 움직임을 count 해주고 그 카운트 값을 출력해주면 된다. 관계가 없는 두 지점은 -1로 초기값을 설정하고 그대로 출력되게 만들었다. 예제 입력을 보면 이런 관계가 된다. ( 그림판으로 그려서 좀 이상하다 ..

내 첫 골드 문제이기 때문에 더욱 신중하고 확실하게 풀기 위해 노력했다. 이 문제는 적록색약이 있는 사람과 없는 사람이 보는 색상의 차이를 구분해서 같은 색으로 인식하는 영역의 개수를 각각 구하는 문제이다. 방법은 DFS를 사용했다. 풀이 전략 N x N 크기의 RGB 색상이 주어지면 우선 일반적인 사람 기준으로 같은 색의 영역 개수를 구하고 적록색약이 있는 사람 기준으로 같은 색의 영역 개수를 구하는 것으로 순서를 정했다. G를 R로 변환하여 탐색하기로 했다. 코드 풀이 전역 변수 선언static int N; static char[][] arr; static boolean[][] check; static int[] dx = {-1,1,0,0}; static int[] dy =..

문제 풀이 분석 1. 주어진 지도에서 연결된 집들을 하나의 단지로 본다. 2. 상하좌우로 연결된 집들을 하나의 단지로 취급한다. 3. 각 단지의 크기와 단지의 개수를 구한 후 단지의 크기를 오름차순으로 정렬한 후 출력한다. 풀이 전략 그래프 탐색 문제이다. DFS를 사용해서 집들 탐색하고 단지의 크기를 구하자. 방문 처리를 해서 이미 방문한 집은 다시 방문하지 말자. 모든 단지를 찾고 오름차순으로 정렬하고 출력하자. 코드 풀이 1. 입력과 배열 초기화 지도 크기 N을 입력받고 N x N 크기의 arr과 방문 여부를 판단하는 배열인 check를 초기화한다.arr배열에 0과 1로 이루어진 지도를 입력받는다.line.charAt(j) - '0'을 사용해서 문자를 숫자로 변환하고 저장한다. Buff..