백준 16928 문제 풀이 Point 이미 방문한 칸이어도 그 칸까지의 비용이 예전 경로의 비용보다 더 적은 경우 다시 탐색해야 한다. 코드 어려웠던 점, 배운 점 StringBuffer와 StringBuilder에 대해 알아볼 수 있어 ㅆ따. 'C'가 두 개
한 문자열이 주어졌을 때, 그 문자열이 UCPC로 줄어질 수 있는 것인지 확인하는 문제이다. 즉, 1) 그 문자열에 U, C, P, C라는 char가 있고, 2) 그 문자들이 문자열에 위치한 index가 오름차순인지, 이 두 조건을 만족시키는지 판별하면 된다. \->
문제 하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하는 문제이다. 가령, 정수 100이 주어지면 100 = ƒ4 + ƒ6 + ƒ11 = 3 + 8 + 89 = ƒ1 + ƒ3 + ƒ6 + ƒ11
문제 링크상어 위치에서부터 bfs로 잡아먹을 수 있는 가장 가까운 물고기를 찾는다이때, 문제 조건대로 가까운 물고기가 많으면, 가장 위에, 다음에 가장 왼쪽에 있는 물고기를 찾는다그런 물고기가 존재하지 않으면, 엄마 상어에게 도움 요청함 즉, time 출력하고 프로그램
문제 링크<span style="background-color:x 값이 1이 될 때까지 연산 하나씩 함.이때, 연산하려는 x 값의 최소 연산 개수에 대한 기록이 있으면, 즉 dpx가 있으면 dpx 반환.없으면 연산 하나를 함.그리고 다음 x에 대해서 반복적으로 해
문제 링크 모든 칸을 시작으로 하여 dfs 탐색해봄 이때, 특정 칸을 시작으로 dfs 탐색한 이후, 그 칸에서 최대로 이동한 칸의 개수가 cnt보다 크면 업데이트함. 그렇게 해서 가장 많이 이동한 칸의 개수를 저장한 cnt를 마지막으로 출력 이렇게 되면 반복
문제 링크\*\*<span style="background-color:- 그래서 1초일 때,0번 이동했으면 1번 나무 아래이기 때문에 dp\[1]\[0] = jadu\[1] % 2, 1번 이동했으면 2번 나무 아래이기 때문에 dp\[1]\[1] = jadu\[1]
문제 링크<span style="background-color:- 전 기록을 이용하여 마지막 날까지 기록마지막 날의 기록인 dp-1을 출력단, N+1일째 이후까지 이어지는 상담을 고려할 필요가 없기 때문에, dp의 size는 n + 1까지 설정하고, dp 크기를
문제 링크이 문제에서 그래프 탐색 시, 단순히 특정 좌표 칸에 방문했는지만 확인하는 것에 그치지 않음.그 칸에 방문했을 때, 몇 번의 말 움직임을 이미 했는지 에 대한 정보도 고려함.가령, graphx를 방문했을 때, 전에 1번 말 움직임 했는지와 2번 말 움직임 했는
문제 링크수빈이의 위치가 동생보다 큰 경우 (n >= k), 가장 빠른 경우는 계속X-1 하는 것이기에 바로print(n-k) 하면 됨그게 아닌 경우, <span style="background-color:- 동생 찾으면 바로 탐색 중지하고 프로그램 종료.이때,
문제 링크bfs로 탐색하되 이동한 거리를 나타내기 위해 방문한 칸의 값을 이동한 거리로 업데이트시켜준다.이렇게 값이 1인 모든 칸들을 bfs로 탐색완료했을 때, (N, M) 위치의 칸 값을 읽으면 최소 이동 거리를 읽을 수 있도록 함
<span style="background-color: (다익스트라 알고리즘을 그대로 사용하면 시간초과 발생)우선순위 큐는 다익스트라 알고리즘의 <span style="background-color:- 병목현상이란 기존 다익스트라 알고리즘의 대표적 문제
Bellman Ford 알고리즘은 다익스트라 알고리즘을 개선시킨 알고리즘이다. 장점\*\*음수 가중치로 인한 <span style="background-color: - 음수 가중치 자체는 문제가 되지는 않는다. 그러나 만약 음수 가중치가 포함된 음의
이 알고리즘은 모든 노드 간의 최단거리를 구할 수 있다.두 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 거리를 구하지만, 플로이드 워셜은 모든 노드 간의 최단거리를 구함공식: <span style="background-color: - 특정한 노드 k를 거
주어진 문자들 중에서 L개로 만들 수 있는 모든 조합을 구한다. 각 조합이 다음 두 가지 조건을 만족시키면, 그 조합을 오름차순으로 청렬하여 정답 list에 저장한다. 1) 모음이 최소 한 개인지 : 모음 집합과 교집합결과 집합 길이가 1 이상이면 만족2) 자음이 최
이 알고리즘은 구간합을 쉽게 구할 수 있도록 하는 알고리즘으로, 각 인덱스 i에 0 ~ i 까지의 누적합을 저장한 배열을 활용한다. 그 배열을 arr라고 할 때, a와 b 인덱스 사이의 구간합을 구한다고 하면 <span style="background-color:
2부터 시작하여 N이 그 소수로 나뉘는지 확인 (소인수인지 판단)소인수로 판단된 경우 그 소수로 N을 나눠지지 않을 떄까지 나눈다. 몇 번 나눴는지를 cnt로 기록한 후, 더이상 나눠지지 않으면 그 소인수와 cnt를 기록위 과정을 2 ~ n까지 반복여기서 N을 나누는
이는 <span style="background-color:알고리즘의 원리는 2부터 시작하여 특정 수의 배수에 해당되는 수들을 모두 배제하는 방식이다. 배제되지 않은 수들은 비로소 소수라고 판단할 수 있으며, 소수 발견시 똑같이 그 소수의 배수를 모두 배제한다(자
이 문제는 구간합의 최댓값을 구하는 문제이다.그러나 이 문제의 특이점은 구간합의 기준인 좌표가 연속적으로 제공되지 않았다는 점이다. 그래서 구간합을 구하는 대표적인 알고리즘인 누적합보다 투포인터를 이용하면 더 좋을 것 같다고 판단했다. 투포인터를 이용하여 구간합을 구하
매년마다 graph 전체를 탐색아직 방문하지 않은 빙산일 경우, 그 칸을 기점으로 bfs 탐색함으로써 빙산의 높이를 조정함bfs 탐색한 횟수(bfs_cnt)에 따라 다음 할 행동을 결정만약 1번만 탐색했다면, 빙산 덩어리가 하나임을 의미하므로, 내년으로 넘어감만약 2번
N 채널에 도달하는 방법에는 두 가지가 있다. \+/- 버튼만 누르는 경우: 100 채널에서 N 채널까지 +/- 버튼만 눌러서 가는 방법숫자 버튼을 누르는 경우: 숫자 버튼들을 눌러 특정 x 채널에 가고, 필요한 경우 +/- 버튼도 추가로 몇 번 누르는 경우이 두