안드 공부를 해볼까?

1. 개요 지난번에 조합에 이어 순열을 정리해볼려고한다. 알고리즘을 푸는 중 조합 + 순열을 사용해서 푸는 문제가 있었다. 2개 다 까먹어서 한번 더 볼겸 순열을 정리할려고 한다.. 2. 목차 - 순열이란? - Swap을 활용한 순열 - Visited배열을 활용한 순열 순열은 어렵지 않으니 간단하게 보고 2가지 방법으로 구현해보자. 3. 본문 1. 순열이란? 순열(Permutation)은 고등학교 때 한번 슬쩍 배웠을 것이다. 간단한 예제를 보자 숫자 1,2,3,4를 중복을 허용하지 않고 2개를 뽑는 방법은? 1 2, 1 3, 1 4 | 2 1, 2 3, 2 4 | 3 1, 3 2, 3 4 | 4 1, 4 2, 4 3 -> 총 12개가 된다. 가볍게 생각해보면 4개중 순서 상관없이 2개, 4P2 -> 4..

1. 문제분석 치킨집의 최대이익을 위해서 필요없는 치킨집을 없앤다고 한다. 처음 생각한건 백트래킹으로 치킨집을 개수에 맞게 랜덤으로 만든 후 BFS로 최단거리를 구할려고 했다. 하지만 최소거리가 아닌 모든 점의 거리를 구하는 것이기 때문에 다시 풀어야했다. 여기서 봐야할 점은 조합이다. 치킨집이 {1,2,3}이 있고 2개로 줄일려고 한다. 예시로 {1,2}, {2,1}은 같은 경우이므로 조합을 통해 중복없이 구해야 한다. 조합을 통해 치킨집을 선정했다면 최소거리를 구하면 된다. 필자는 ArrayList에 치킨집과 집의 정보를 넣었다. 한 사람의 집에서 조합으로 나온 치킨집의 거리를 구한 후 최솟값을 저장하면 된다. 결과적으로 조합으로 나온 치킨집과 거리를 측정 후, 최소값을 print해주면 된다. 2. ..

1. 문제분석 연구실 공간에 바이러스가 존재한다. 이 바이러스는 사방면으로 퍼져나간다고 한다. 하지만 우리는 벽을 3개 세울 수 있다. 이 3개로 최대한 바이러스가 안퍼져나가게 해야한다. 이 3개를 항상 최적으로 구해서 대입하고 바로 빈공간을 구할 수 없다. 여기서 볼 점은 벽 3개를 여러 곳에 넣어보고 그 때 빈 공간이 최대인 곳을 구하는 것이다. 그렇다면 벽 3개를 여러군데 넣어주는 것을 어떻게 할까? 바로 DFS를 통해서 넣어주면 된다. 만약 벽을 3개 세웠다면 바이러스가 퍼져나간 후 빈공간을 구하면 되는 것이다. static void setWall(int count) { if (count == 3) { bfs(); } else { for (int i = 0; i < N; i++) { for (in..

1. 문제분석 사실 이전에 퇴사2 문제를 먼저 풀고 풀어서 그런지 쉽게 풀었다. 퇴사 2에서는 구글링을 해도 이해가 안갔지만 하루동안 찾아보니 스스로 해결책을 알아버렸다. 일단 이 문제는 dp로 풀 수 있다. 만약 i일 때 일을 했다면 그 때 dp테이블의 값을 구하면 되는 것이니까. 노션에 이미 정리한 글이므로 복사해왔다. 그럼 하나씩 하기전에 2가지 조건을 세워서 해보자. 돈은 다음날 받는다. 예를 들어 1일날 일했으면 3일동안은 상담을 해야합니다. 그렇다면 1, 2, 3일은 다른 상담을 못하고 1일만의 상담을 해야합니다. 돈은 상담을 마치고 다음날에 들어오는 것으로 기준을 잡았습니다.(1일 → 4일) 내가 n일에 일했을 때, 나오는 값(점화식) 내가 1일에 일했다 → 4일부터 일 가능 → 4일까지의 ..

1. 문제분석 스타트팀과 링크팀을 나누어서 각 팀의 능력치를 구하고 팀 전체 능력의 차이가 최소인 점수를 구하는 문제다. 위에서 이미 답을 준 셈이다. 1번과 2번이 팀이고 3번과 4번이 팀이라고 한다. 그 때, {1,2}, {2,1}과 {3,4}, {4,3}, 서로를 더해 빼면 되는 것이다. 위에서 나온 팀을 순열로 구한 것이다. 반면 팀은 어떻게 구할까? 여기서 팁은 조합이다. 1번과 2번이 팀인 경우 답을 구했다. 그렇다면 2번과 1번일때 또 구해야할 필요가 있을까? 즉, 조합을 구해서 팀을 꾸리고 능력치를 순열로 구하는 문제다. (팀 : n C n/2, 능력치: n/2 P 2) 2. 구현 import java.io.BufferedReader; import java.io.InputStreamRead..

1. 개요 싸피 교육기간 중 알고리즘을 배우는 시간 있었다. 순열과 조합에 대해 굉장히 중요하다고 하셨고 이를 구현해봤지만 아무리 생각해도 이해가 안갔다. 그래서 구글링을 하며 내걸로 만들고자 이번 포스팅을 준비했다. 2. 목차 1. 조합이란? 2. 조합을 뽑는 방법 3. 구현 먼저 조합이 무엇인지와 구조를 이해하고 구현을 했다. 구글에 존재하는 코드를 이해하지 않고 적었다면 이 포스팅으로 이해해보자. 3. 본문 1. 조합이란? 항상 수학시간에 궁금했던 문제다. 순열과 조합은 도대체 무슨차이일까? 필자는 단순 중복여부를 생각했다. 순열은 순서에 상관없이 다 뽑아내고 조합은 중복이 되면 안되는 것이고. 간략하게 생각해보면 위에 말이 맞다. 예시를 들어보자 우리는 1,2,3을 사용해서 2개를 뽑을 것이다. ..

1. 문제분석 비가 올 때 안전지역, 즉 비의 높이 이하인 지역의 영역의 개수를 구하는 문제다. 나는 문제가 도대체 뭘 구하라는 건지 몰라서 구글링을 했다. 막상보니 영역을 1개로 치고 그 영역을 구하는 것이다. 1번째 그림을 보자. 비의 높이는 4이므로 4 이하는 전부 회색으로 처리한다. 그 후, 나머지 영역을 보면 (6,8), (6), (7,6,7,8,9,5,5), (6,7), (6)으로 5개 나온다. 2번째 그림은 비의 높이가 6일 때의 상태다. 6이하는 전부 회색으로 처리한 상태고 나머지 영역을 구하면 된다. (8), (7), (7,8,9), (7) 총 4개의 영역이 나온다. 우리는 이 영역의 최대값을 구하면 되는 것이다. 기초적인 DFS에서 조건 1가지를 주면 구할 수 있다. 먼저 비의 높이는 ..

1. 문제분석 기본적인 DFS 문제다. 나는 visited배열 + 재귀형식으로 구현을 했다. 단지별로 모여있다는 것은 출발점에서 DFS를 통해 탐색이 가능한 경우를 1개로 친다. 예시인 1단지를 보자. 만약 방문이 가능하다면 DFS를 실행한다. 그렇다면 해당 구역을 전부 찾았을 것 이다. 찾은 구역의 visited값을 false로 두고 다음 탐색 가능 구역을 가면 된다. 탐색이 가능하면 단지의 개수를 증가하고 ArrayList에 넣어주었다. 마지막 단지개수와 오름차순으로 정렬한 단지 값을 출력하면 된다. 2. 구현 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.ut..