dfs
-
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를 풀어나가면 된다. 여기서 숫자 배열을 가리키..
-
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..
-
BOJ) 계란으로 계란치기알고리즘/백준 2020. 6. 30. 15:01
계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 이 문제가 너무 좋은 점은, 테스트 케이스가 충분히 주어졌기 때문이다. 그래서 그런지 정답 비율이 꽤나 높다. 문제가 제시한 조건을 살펴보면, 계란이 일렬로 나열되어있고 가장 왼쪽 계란부터 오른쪽 끝까지 순차적으로 들어서 계란판에 있는 다른 계란을 내려 치는 것이다. 두 계란의 내구도는 각각 상대 계란의 무게만큼 감소하게 된다. 한번 내리친 다음에, 손에 들고있던 계란을 내려놓고 다음 계란을 든다. 이때, 조건이 손에 쥔 계란..
-
BOJ) 부분수열의 합 2알고리즘/백준 2020. 6. 3. 23:23
부분수열의 합 2 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 오늘 문제가 너무 안풀려서 하나만 더 풀어보자 하고 기출문제와 유사한 문제라고해서 풀어봤다. 오랜만에 백준 문제를 풀어서 그런지 어려웠다. 그리고 백준이 바로 코딩하기에 친절하지가 않아서 처음 구조를 잡아나갈 때를 제외하고는 ide힘을 빌려야했다.. ㅠ N개의 정수로 이루어진 배열에서 부분 수열의 합이 S가 되는 경우의 수를 구하는 문제다. N은 40 이하의 수, S는 -1,000,000 ~ 1,00..
-
알고리즘) 프로그래머스 DFS/BFS, 여행경로알고리즘/프로그래머스 고득점 Kit 2020. 4. 21. 15:36
프로그래머스 고득점 Kit - DFS/BFS 여행경로 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. ..