음식물 피하기 #1743 더보기 음식물 피하기 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 19737 9366 7420 47.494% 문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 선..

전쟁-전투 #1303 더보기 전쟁 - 전투 문제 전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다. N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다. 입력 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 ..

DFS(깊이 우선 탐색) 깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 기능 특징 시간 복잡도 (노드 수:V , 에지 수 :E) 그래프 완전 탐색 - 재귀 함수로 표현 - 스택 자료구조 이용 O(V+E) 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 한다. 깊이 우선 탐색의 핵심 이론 DFS는 한 번 방문한 노드를 다시 방문하면 안되므로, 노드 방문 여부를 체크할 배열이 필요 그래프는 인접 리스트로 표현한다. DFS의 탐색 방식은 후입선출 특성을 가진다. (스택 사용) DFS 구현은 스택보다는..

구간합 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. 구간 합 핵심 이론 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. 합 배열 S 정의 S[i] = A[0] + A[1} + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열이라 생각하면 된다. 이렇게 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다. 합 배열 없이 배열 합을 구하는 경우, 최악의 경우는 i가 0이고 j가 N인 경우로 시간 복잡도는 O(N)이다. 이런 경우 앞에서 알아본 합 배열을 사용하면 O(1) 안에 답을 구할 수 있다. 합 배열 S를..