알고리즘/백준4 [백준] 1715 - 카드 정렬하기 난이도 - G4 사용 개념 - 구현, 자료구조(PriorityQueue) 풀이 시간 - 20분 ( 설계 10분, 구현 10분 ) 핵심 키워드 * 1. 문제의 설명에 의하면 결국 가장 작은 값 2개를 꺼낸 후 덧셈을 진행하고, 다시 Prioirty Queue에 넣어야 한다. -> 배열로 진행하면 인덱스 처리가 복잡해진다. Priority Queue를 사용해서 풀라고 만든 문제같다. * 2. int의 범위로는 할 수 없다. long을 사용하여야 한다. ( 최악의 상황 ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 import java.io.BufferedReader; import java.io.InputStreamReader; imp.. 2024. 3. 20. [백준] 17298 - 오큰수 난이도 - G4 사용 개념 - 구현, 자료구조(Stack) 풀이 시간 - 45분 ( 설계 25분, 구현 20분 ) 핵심 키워드 * 1. 시간제한이 1초지만, N 범위 최대가 1,000,000회라 O(n²)이면 시간초과 발생 -> O(Nlogn)으로 해결 가능 * 2. 스택을 사용하며 역순으로 진행한다. ( 맨 뒤의 index는 무조건 -1이기 때문 ) 2-1. 한 번 값을 얻어올 때 마다 스택의 맨 위와 비교하여 행동을 결정한다. 2-2. 만약 배열에 저장된 값이 스택의 맨 위보다 작다면, 스택에 저장된 값이 배열의 해당 index의 오큰수는 스택의 맨 위 값이 된다. 2-3. 만약 배열에 저장된 값이 스택의 맨 위보다 크다면, 스택을 하나씩 꺼내보며 더 큰 수를 발견하거나, 스택이 빌 때 까지 확인한다.. 2024. 3. 20. [백준] 20055 - 컨베이어 벨트 위의 로봇 난이도 - G5 사용 개념 - 구현, 자료구조(Queue) 핵심 키워드 * 1. 로봇은 n-1위치에 존재할 때 내릴 수 있다면 무조건 내린다. * 2. 컨베이어 벨트의 작업 순서에 유의해야 한다. 1) 컨베이어 벨트가 먼저 회전한다. 벨트 위에 로봇이 존재한다면 로봇을 포함하여 회전한다. 2) 이후 로봇이 움직일 수 있다면 "먼저 들어온 로봇의 순서대로" 앞으로 1칸 이동한다. 3) 이후 0번 인덱스에 존재하는 컨베이어 벨트의 내구도가 1보다 크고 로봇이 없다면, 로봇을 올리고 내구도를 1 감 소한다. 4) 이 과정 속에서 로봇이 n-1에 존재한다면, 무조건 내린다. * 3. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다. 1 2 3 4 5 6 7 8 9 1.. 2024. 3. 17. [백준] 17135 - 캐슬 디펜스 난이도 - G3 사용 개념 - 조합 + 브루트포스 + 구현 + BFS 핵심 키워드 * 1. 같은 거리에 있다면 가장 왼쪽에 있는 적을 처치한다. * 2. 여러 명의 궁수가 같은 적을 공격할 수 있다. ----> BFS의 결과 확인을 동일 시간대에 확인해야함. * 3. 좌, 중, 우 순으로 조회 - 궁수는 거리가 가까운 적부터 처리한다. 만약 거리가 같은 적이 여럿 존재한다면 가장 왼쪽의 적부터 처리한다. - 다른 궁수가 같은 타겟을 공격할 수 있다. 즉, 동일 시간대에 처리되는 적에 대한 상황을 생각해야한다. - 1번의 사이클이 끝나고 난다면 적이 1칸 내려온다 ( --> 궁수가 1칸 전진한다와 같은 의미) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 .. 2024. 2. 17. 이전 1 다음
