목록분류 전체보기 (250)

잡다한 IT 지식

1561. Maximum Number of Coins You Can Get

숫자가 적혀있는 동전을 3개씩 뽑아서 숫자의 크기가 제일 큰 애는 Alice한테 주고 Bob한테는 제일 작은 값 주고, 가운데 값은 자기가 가진다. 동전이 없어질 때까지 반복한다. 자기가 가진 동전의 숫자의 합의 최댓값은? 문제를 보고 제일 먼저 생각난 건 3n이면 반복할 횟수는 n번. 뽑을 때마다 최댓값을 가진 동전 다음으로 큰 동전을 뽑아야함. 1,2,2,4,7,8 x,x,o,x,o,x 2,4,5 x,o,x 1,2,3,4,5,6,7,8,9 x,x,x,o,x,o,x,o,x import java.util.Arrays; class Solution { //1,2,2,4,7,8 //x,x,o,x,o,x //2,4,5 //x,o,x //1,2,3,4,5,6,7,8,9 //x,x,x,o,x,o,x,o,x publ..
알고리즘 문제 풀이 2021. 5. 13. 21:53
BFS

참고한 영상 BFS 위키백과 너비 우선 탐색(Depth-First Search) 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 큐를 이용해서 구현합니다. 장점 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다. 단점 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다. 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다. 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다. 영상 보면서 직접 코틀린으로 구현해본 소스 코드. i..
알고리즘 문제 풀이/BFS 2021. 5. 7. 09:11
938.Range Sum of BST

주어진 트리 노드에서 노드의 값을 val이라고 정의했을 때, low
알고리즘 문제 풀이/DFS 2021. 5. 6. 12:05
DFS

참고한 영상 DFS 위키백과 깊이 우선 탐색(Depth-First Search) 최대한 깊은 단계까지 우선 검색하는 방법. 구현방법으론 스택과 재귀식 구현이 있음. 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다. 영상 보면서 직접 ..
알고리즘 문제 풀이/개념 2021. 5. 6. 10:47
01 Matrix

각 블록에서 가장 가까운 0을 찾는 문제. 자신이 0이면 그 블록에 값은 0이고, 옆에 있으면 1이 됨. 블록은 상하좌우로만 움직임. 처음 문제를 봤을 때 구현 문제가 생각났음. 처음 블록에서 주변 상하좌우를 확인한 후, 없으면 상,하,좌,우 이동한다. 그 다음에 다시 상,하,좌,우에 0이 있나 확인. 접근 방법은 생각났는데 코드 구현을 못해서 계속 헤메다가 BFS가 떠올라서 BFS 검색해서 어설프게 구현했음. 제일 헤멨던 게 x,y좌표 구분에서 엄청 헤멨음. x,y를 명확하게 뭐라고 확실히 정하고 하지 않아서 굉장히 고생함. 다음에 좌표 문제가 나오면 x,y 확실히 정하고 풀어야겠음. 다음엔 밑에 2가지를 신경 써서 풀어야겠음. 1. BFS 제대로 구현 2.x,y 좌표 명확하게 잡기. 푼 거. impo..
알고리즘 문제 풀이/BFS 2021. 4. 14. 16:58
Minimum Number of Operations to Move All Balls to Each Box

처음 생각한 답. import java.util.HashSet; import java.util.Set; class Solution { public int[] minOperations(String boxes) { int[] answer = new int[boxes.length()]; Set set = new HashSet(); int boxLength = boxes.length(); for (int i = 0; i < boxLength; i++) { if (boxes.charAt(i) == '1') { set.add(i); } } for (int i = 0; i < boxLength; i++) { int count = 0; for (int j : set) { count += Math.abs(i-j); } ..
알고리즘 문제 풀이/다시 봐야할 것들 2021. 4. 14. 05:00
이전 Prev 1 ··· 38 39 40 41 42 Next 다음