전체 글(49)
-
BOJ 백준 [2805] 나무 자르기
IDEA N의 최댓값은 1,000,000이며 M의 최댓값은 2,000,000,000이다. 가능한 모든 높이의 길이를 탐색하여 답을 구하고자 한다면, 1,000,000 * 2,000,000,000 즉, 주어진 시간제한을 넘길 것이다. 이를 해결하기 위해서 좀 더 생각을 해보자. 나무가 나열된 순서는 상관이 없다. 그렇다면 나무를 순서내로 나열 시켜보자. 위와 같이 나무를 정렬 시켰을 때, 자르고자 하는 나무의 높이를 이분탐색하여 찾는다고 생각해보자. 우선, 나무를 정렬시키는데 사용되는 시간은 NlogN --> 1,000,000*lg1,000,000 약, 20,000,000의 시간이 소요된다. 그리고 이분탐색을 이용하여 높이의 최댓 값을 탐색해보자. NlogM --> 1,000,000*lg2,000,000,..
2019.09.04 -
BOJ 백준 [2003] 수들의 합 2
IDEA 1 문제에서 주어진 N의 경우 10,000이다. 그리고 각각의 A[x]는 30,000을 넘지 않는 자연수라고 하였다. 그렇다면 N의 값이 최대일때, 모든 A[x]를 다 더하여도 300,000,000을 넘지 않는다. 즉, 최댓값이 2,147,438,647인 int형의 최댓값보다 작다. 만약 아래와 같이 배열을 만든다고 가정하고 생각하자. 1 2 3 4 5 int sums[MAX_N] for(int i = 0; i
2019.09.03 -
[알고리즘 문제해결 전략]6장. 무식하게 풀기_⑤
CLOCKSYNC in algospot problem 문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)CLOCKSYNC10000ms65536kb75972989 (39%)출제자출처분류JongManIOI 1994보기문제그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같..
2018.12.30 -
[알고리즘 문제해결 전략]6장. 무식하게 풀기_④
BOARDCOVER in algospot problem 문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)BOARDCOVER2000ms65536kb63352902 (45%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.입력력의 첫 줄에는 테스트 케이스의 수 C (C
2018.12.29 -
[알고리즘 문제해결 전략]6장. 무식하게 풀기_③
PICNIC in algospot problem 문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)PICNIC1000ms65536kb96664136 (42%)출제자출처분류JongMan알고리즘 문제 해결 전략보기 문제안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 ..
2018.12.29 -
[알고리즘 문제해결 전략]6장. 무식하게 풀기_②
BOGGLE in algospot problem 문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)BOGGLE10000ms65536kb101291635 (16%)보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다.예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다.보글 게임판과 ..
2018.12.29