알고리즘 문제/BOJ17 [BOJ][1346] 구슬 탈출 2 문제 : www.acmicpc.net/problem/13460 너비 우선 탐색(BFS)를 이용한다. 방문 여부는 빨간 공 (x, y) 파란 공 (x, y) 이용해서 4차원 배열을 만들어서 체크한다.(check 배열) 큐 안에는 (빨간 공(x, y), 파란 공(x, y), 기울인 횟수)를 저장한다. 벽 또는 탈출구가 나올 때까지 한 방향으로 공을 계속 움직인다. 파란 공이 빠져나오는 경우는 불가능한 경우이고 빨간 공만 나온 경우는 기울인 횟수를 출력하고 종료한다. 파란 공과 빨간 공이 겹치는 경우, 기울이기 전 위치를 비교해서 겹치지 않게 해준다. 만약, 아래 방향으로 움직이는 경우 기울이기 전 빨간 공이 파란 공보다 아래에 있었다면 파란 공의 위치를 1위로 옮긴다. 공들의 위치를 겹치지 않게 조정한 다음.. 2020. 11. 1. [BOJ][16236] 아기 상어 문제 : www.acmicpc.net/problem/16236 거리가 가장 가까운 먹을 수 있는 물고기를 찾되 조건에 해당하는 물고기가 여러마리라면 가장 위, 가장 왼쪽에 있는 물고기를 먹으러 간다. 가장 가까운 먹을 수 있는 물고기를 찾아야하므로 BFS(너비우선탐색)을 하는데 가장 위, 가장 왼쪽에 있는 물고기를 찾아야 하므로 큐가 아닌 우선 순위 큐를 사용했다. 우선 순위 큐에 (현재 상어 위치와 이동하고자 하는 좌표간 거리(dist), (이동하고자 하는 좌표(x, y))) 를 저장한다. 해당 큐에서 좌표간 거리가 가장 짧고, 이동하고자 하는 좌표(x, y)를 x가 작을 수록, y가 작을수록 높은 우선순위를 가진다. 우선 순위 : dist 오름차순 -> x 오름차순 -> y 오름차순 상어가 지나갈 수.. 2020. 10. 31. [BOJ][14888] 연산자 끼워넣기 문제 : www.acmicpc.net/problem/14888 N의 범위가 2~11 이다. 백트래킹으로 돌려도 될만한 시간이다. 정수집합을 앞에서부터 탐색해가면서 가능한 부호를 모두 돌려봐서 나오는 수들 중 최대값, 최소값을 구한다. pair answer; // arr : 정수형 배열 // signCnt : 부호 개수, // ind : arr 탐색 중인 인덱스 // result : 이때까지 계산한 결과값 // sign : arr[ind]에 적용할 부호. arr[ind] 앞에 들어갈 부호 void backtracking(int[] arr, int[] signCnt, int ind, int result, int sign) { // 경계값 확인 sign 부호 확인 + 인 경우: result += arr[ind.. 2020. 10. 24. [BOJ][15686] 치킨 배달 문제 : https://www.acmicpc.net/problem/15686 백트래킹으로 풀 수 있다. 도시들을 탐색하면서 집 배열, 치킨집들 배열을 만든다. 치킨집들을 선택해나가면서 집들에서 가장 가까운 치킨집의 거리들을 갱신해나간다. // dist : i번 집과 치킨집과의 최소 거리 // ind : 치킨집 인덱스, // cnt : 선택된 치킨집 개수 void backtracking(vector dist, int ind, int cnt) { // 경계값 확인 backtracking(dist, ind + 1, cnt); // ind 번째 선택하지 않고 다음 치킨집 탐색 pair chi = chickens[ind]; // ind 번째 치킨집 좌표 저장 int sum = 0; // dist 배열 합 for .. 2020. 10. 20. [BOJ][2143] 두 배열의 합 문제 : https://www.acmicpc.net/problem/2143 투 포인터(Two-Pointer)를 이용하여 풀었습니다. 배열 당 모든 부배열을 만드는 시간 복잡도는 O(n2)인데 n의 크기가 (1T) 이므로 R--해줍니다. (L=1 / R=6) 1+5 = 6 (>T) 이므로 R--해줍니다. (L=1 / R=5) 1+4 = 5(==T) 이므로 subA에서 1의 개수 x subB에서 4의 개수를 구하면 2x1 = 2가 됩니다. 곱하는 이유는 부 배열 쌍의 개수를 구하는 것이기 때문입니다. 해당 수를 정답에 더하고 L++, R-- 해줍니다. (L = 1, 2 / R = 4) 2+3 = 5 (==T) 이므로 subA에서 2의 개수(1) x subB에서 3의 개수(1)의 값을 정답에 더하고 L++, .. 2020. 7. 8. [BOJ][11585] 속타는 저녁 메뉴 문제 : https://www.acmicpc.net/problem/11585 두번째 문장을 2개 이어붙인 문자열에서 세번째 문장이 몇 번 나오는지 찾는다. 이를 KMP로 찾을 수 있다. 주의할 점은 입력값이 ABCDE, ABCDE인 경우 정답은 1/5 이지만 2/5 가 출력된다. 두번째 문장을 2개 이어붙였기 때문에 ABCDEABCDE에서 실제로는 1개지만 빨, 파 2 번 나타났다고 판단했기 때문이다. 따라서 패턴문자열을 찾았을 때 첫번째 문자열을 시작으로 하는 부분문자열에서 패턴이 나타났다면 1을 빼준다. KMP로 구한 패턴문자열이 나타낸 횟수가 분자, 문자열 길이(N)가 분모가 된다. 기약분수는 최대공약수를 유클리드로 구해서 분자, 분모에 나눠주면 된다. 시간복잡도는 O(N). 소스코드 : https.. 2020. 4. 8. 이전 1 2 3 다음
