본문 바로가기

전체 글657

[BOJ][16236] 아기 상어 문제 : www.acmicpc.net/problem/16236 거리가 가장 가까운 먹을 수 있는 물고기를 찾되 조건에 해당하는 물고기가 여러마리라면 가장 위, 가장 왼쪽에 있는 물고기를 먹으러 간다. 가장 가까운 먹을 수 있는 물고기를 찾아야하므로 BFS(너비우선탐색)을 하는데 가장 위, 가장 왼쪽에 있는 물고기를 찾아야 하므로 큐가 아닌 우선 순위 큐를 사용했다. 우선 순위 큐에 (현재 상어 위치와 이동하고자 하는 좌표간 거리(dist), (이동하고자 하는 좌표(x, y))) 를 저장한다. 해당 큐에서 좌표간 거리가 가장 짧고, 이동하고자 하는 좌표(x, y)를 x가 작을 수록, y가 작을수록 높은 우선순위를 가진다. 우선 순위 : dist 오름차순 -> x 오름차순 -> y 오름차순 상어가 지나갈 수.. 2020. 10. 31.
[201024] 운동근황 체중은 빠지는데 근육도 같이 빠져서 1일 닭가슴살 3덩이 형을 받았다. 덕분에 어제 1시간 동안 저녁을 먹었다.. 이번주엔 오늘까지 합쳐서 4일 운동하러 갔다. 내일까지가면 주5일 출첵! 장족의 발전이군. 더 열심히 해라. 2020. 10. 24.
[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.
[leetcode][735] Asteroid Collision 문제 : leetcode.com/problems/asteroid-collision/ 0이 아닌 정수 값을 가진 asteroids 배열이 주어진다. 요소의 절대값은 크기를 의미하고 부호는 방향을 의미한다. 같은 방향을 가지는 운석들은 부딪히지 않는다. 다른 방향을 가지는 운석들이 만날때 크기가 크거나 같은 운석들이 파괴된다. asteroids 배열에서 충돌가능한 운석들이 충돌한 뒤 남은 운석들의 배열을 반환하라. [1,2,3,4,-5] 가 주어졌을 때, -5는 4,3,2,1을 차례대로 파괴시킬 수 있고, 만약 [1,2,6,3,-5] 과 같은 운석들이 있다면 -5 운석은 3까지만 파괴시키고 6을 만나 파괴되므로 1,2 운석은 확인하지 않아도 되기 때문에 스택을 사용했다. 배열을 앞에서부터 탐색하면서 스택에 .. 2020. 10. 24.
[leetcode][133] Clone Graph 문제 : leetcode.com/problems/clone-graph/ 모든 노드들이 연결된 방향성 없는 그래프가 주어진다. 이를 깊은 복사한 트리를 생성한 뒤 반환하라. 트리 노드부터 탐색해가면서 노드를 붙여나가는 BFS 방식으로 풀었다. 생성된 노드들에 대한 정보를 저장하기 위한 map 을 추가했다. 해당 map의 key는 node.val이 고유하다고 명시되어 있기 때문에 이를 사용하고 map의 value는 Node*을 저장한다. 탐색 중인 노드의 neighbors 들 중 생성되지 않은 노드가 있다면 생성한 뒤 map에 저장, 탐색 중인 노드의 clone 노드에 생성한 노드를 neighbors로 등록. 이미 생성된 노드라면 map에서 해당 노드를 가져온 뒤 clone 노드의 neighbors로 등록하.. 2020. 10. 21.
[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.

티스토리툴바