알고리즘
-
BOJ) 숫자판 점프알고리즘/백준 2020. 7. 6. 18:01
숫자판 점프 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 풀이 5x5 크기의 숫자판에서 숫자 6개를 골라, 만들 수 있는 숫자의 갯수를 구하는 문제다. 또한, 000001 or 000000과 같은 숫자가 허용되고 이동할 때는 먼저 거쳐간 칸을 다시 거쳐가도 된다는 조건이 있다. 따라서, int형보다는 String으로 문제를 푸는 것이 적합하다고 생각했고, visit이 필요없는 문제였다. 그래서 처음에는 dfs안에서 좌표 for문을 돌면서 각 좌표 상하좌우에 있는 ..
-
BOJ) 연산자 끼워넣기알고리즘/백준 2020. 7. 5. 20:18
연산자 끼워넣기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 풀이 어렵지 않은 문제지만, 푸는데 많은 시간이 들었다. return하는 부분에서 조건을 잘못 설정해줘서 찾는데 한참이 걸렸다.. ㅎㅎ ㅠㅠ 방법은 간단하다. 숫자 배열을 입력받아 저장하고, 연산자 배열(+,-,*,/ 순서)을 저장하면 이 문제는 끝이다. 숫자 사이사이 연산자를 집어 넣는 경우로, 숫자 배열을 가리키는 index를 통해 DFS를 풀어나가면 된다. 여기서 숫자 배열을 가리키..
-
프로그래머스 고득점 Kit) Hash, 전화번호 목록알고리즘/프로그래머스 고득점 Kit 2020. 7. 4. 00:55
전화번호 목록 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조�� programmers.co.kr 풀이 다른 사람 풀이를 구경하다가 좋은 메소드를 알게돼서 포스팅을 남긴다. 코득점 Kit의 Hash 문제라 처음에는 Hash를 이용해서 풀었었다. 오늘 다시 풀었을 때는 2중 포문과 substring을 이용해서 풀었다. 2중 포문으로 돌리는 법은 쉬운 방법이기 때문에 코드를 남기지는 않겠다. 다만, 코드 1에 남긴 코드가 너무 충격적이었다. String에 startsWith라는 메소드가 있다는 것을 처음 알았다. 파라메터로 입력한 값으로 시..
-
BOJ) 벽 부수고 이동하기 4알고리즘/백준 2020. 7. 3. 16:37
벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 � www.acmicpc.net 풀이 처음에는 모든 벽에 대해서 벽을 허물고 값을 구하고자 했다. 하지만, 주어진 n과 m의 최대값이 1000이나 되기 때문에 시간초과가 뜰 것 같았다. 그래서 생각한 것은 0에 대해서 grouping을 해주는 것이다. 빈칸이 이어진 곳들에 대해서 그룹 index를 남기고, 몇 개의 빈칸이 존재하는지 세주어서 저장하는 것이다. 이후에, Map을 돌면서 벽을 허물었을 경우, 상하좌우에 (인접한 곳에) 빈칸 그룹이 가지..
-
BOJ) 부등호알고리즘/백준 2020. 7. 3. 16:27
부등호 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제�� www.acmicpc.net 풀이 답은 바로 구했지만, 메모리를 너무 많이 잡고 속도가 느려서 몇 번을 다시 풀었다. 처음에는 모든 경우의 수를 다 구해서, 부등호의 갯수 n개 +1 만큼의 숫자를 뽑은 경우를 답 리스트에 넣어주었다. 이후, 정렬을 통해 양 끝에 있는 수를 출력해주었다. 정말 별로인 코드다... 그래서 조금 고쳐보기로 했다. String으로 다 저장해서 정렬을 하는것이 아니라, Long 타입 변수를 통해 MAX와 MIN 값을 저장해주었다. 로직 자체가 문제라서 메모리와 속도에 ..
-
BOJ) 스타트와 링크알고리즘/백준 2020. 7. 2. 16:22
스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 주어진 짝수 인원(4~20)이 축구 경기를 하는데, n/2 : n/2 경기를 해야한다. 이 때, 실력차이가 가장 적게나는 경우를 찾는 문제다. 결국, 모든 경우의 수를 다 파악해야하는 Brute-force 문제였다. n이 20이나 되지만, DFS를 선택했다. 왜냐하면, N=20인 경우, 10 : 10 경기를 하기 때문에, 결론적으로는 2^20까지 가지 않기 때문이다. 중간에 한쪽 팀이 N의 절반이 넘어가는 경우를 가지치기만 해준다면 가능하다고 생각했다. dfs를 통..
-
BOJ) 에너지 모으기알고리즘/백준 2020. 7. 2. 16:16
에너지 모으기 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있� www.acmicpc.net 풀이 브루트 포스 문제로 모든 경우의 수를 다 구해야 했다. BFS와 DFS 중 DFS가 더 적절하다고 생각해서 DFS로 문제를 풀었다. 문제 조건에 따라서, 1~n-1 까지 하나의 숫자를 골라 좌 우에 있는 에너지를 곱해서 더해나갔다. 이때, 에너지를 담을 변수는 ArrayList를 선택해서 따로 index값을 복잡하게 조정하지 않게 해주었다. 왜냐하면, ArrayList에는 특정 index에 값(Element)를 넣을 수 있는 메소드가 존..
-
BOJ) 연구소알고리즘/백준 2020. 7. 2. 16:09
연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 풀이 배열 복사 문제로 고생을 조금 했다. 바이러스가 퍼지는 부분을 갱신할 때, 기존 MAP에 덮어 씌우면 답과 거리가 멀어지기 때문이다. 왜냐하면, char[][] map은 dfs에 계속 이용이 되기 때문에.. 다른 값들에 영향을 미친다. 배열 복사 이후에 바이러스가 퍼지고, 안전 구역을 탐색하니까 답을 맞출 수 있었다. 일단 3번 답을 구했는데, 첫번째로 구했던 답은 LinkedList를 이용하는 것이었다. 바이러스를 퍼뜨릴 때, LinkedList를 이용해서 B..