알고리즘 검색 결과

해당 글 82건
가희와 비행기 문제를 카탈란 수로 구해 봅시다.

안녕하세요. 오랫만입니다. 이번 시간에는 제가 출제한 가희와 비행기 문제를 보도록 하겠습니다. 문제를 다 이해하셨다면, 구하려고 하는 것은 그리 어렵지 않음을 알 수 있습니다. 김포 공항에서 김해 공항까지 수평 거리가 d일 때, 조건에 맞게 비행할 수 있는 가짓수를 구하는 것인데요. x인 지점에서 비행기의 고도가 h라고 해 보겠습니다. 그러면 x-1인 지점에서부터 고도가 1만큼 하강하거나, 혹은 고도가 1만큼 상승하는 이 두 가지 경우밖에 없습니다. 그래서, dp[x][h]를 x인 지점에서 고도가 h인 경우라고 정의하면, dp[x][h]는 dp[x][h-1] + dp[x][h+1]이 됩니다. 그런데, 예외가 있습니다. 중간에 착륙하는 경우는 없다고 했어요. 그렇기 때문에, x가 0이거나 d가 아닐 때, ..
알고리즘/ps 2022. 1. 6. 23:15
롯데 자이언츠와 가희 : 벤다이어그램을 그려서 도식화 시켜 봅시다.

이번 시간에는 오랫만에 코딩 테스트가 아닌, 제가 출제한 문제에 대해서 간단하게 해설해 보겠습니다. 사실, 이 문제는 선린고 대회 문제로 출제하려고 했지만, 모종의 이유로 반려된 문제입니다. 그렇지만, 백준에 낼 가치는 충분히 있다고 판단되어 올리게 되었습니다.이 자리를 빌어, 제 문제를 검수해 주신 분들에게 감사드립니다. 아마, 이 블로그의 글들을 유심히 보셨던 분들이라면 제가 키움과 롯데 자이언츠 팬임은 아실 수 있을 겁니다. 이 문제에 나타난 7월 28일을 제가 굳이 언급한 이유는 쓰리런으로 끝내기를 치신 그 분 때문입니다. 각설하고 가희가 9회 말을 보기 위해 풀어야 하는 수학 문제를 보도록 합시다. n개의 수가 최소 공배수가 L이고, 최대 공약수가 G인 가짓수를 구해야 하는 게 목표입니다. 보기..
알고리즘/ps 2021. 11. 24. 23:39
sort 함수의 custom compare 함수를 구현할 때 어떤 점도 조심해야 할까요?

요새 졸리네요. 코딩 테스트를 개최하면서 여러 코드를 보았는데요. 2회 코테가 의외로 1번부터 막히는 경우가 많았는데요. 아마도 정렬과 비교 함수의 메커니즘에 대해서 익숙하지 않아서 그러셨을 겁니다. strict weak ordering은 이펙티브 자바에서도 언급하는 주제이니 다른 조심해야 할 점을 언급해 볼게요. 이 질문과 이 질문은 제가 오늘 쓰려는 글과 관련이 깊습니다. 결론부터 말하자면, 정렬 문제에서 전처리 할 부분을 미리 전처리 하고 오면 로직이 단순해 집니다. 그러면 실수할 여지도 적습니다. 그리고 크기가 n인 배열을 정렬할 때 키 2개를 비교하는 compare 함수는 O(nlogn)번 호출됩니다. 이 글에서는 compare 함수가 어떻게 동작하나요? 에 대해서는 다루지 않습니다. 어떻게 정..
알고리즘/이론 2021. 11. 10. 00:42
리버스 가희와 프로세스 : 상황 도식화를 잘 시켜 봅시다.

가희배 코딩테스트 1회에서 나온 7번 문제는 가희와 프로세스 문제의 결과값이 주어졌을 때, 거꾸로 인풋 값을 만들어 보라는 문제였습니다. 항상 가능한 경우만 주었기 때문에 쉬울 거라고 생각했습니다. 그런데, 실제로 대회 때 문제를 푸신 분들은 그리 많지 않았고 골드 1로 평가되는 기염을 토하게 되었습니다. 사실 불가능한 경우까지 출력하라고 했는데, 진짜 그렇게 출제 했다면 100% 플레급으로 뛰었을 거라 생각합니다. 그러면 무엇이 이렇게 어렵게 만들었을까요? 문제에서 설명하는 알고리즘을 단순화 하는 것이 제일 어렵지 않았나 싶습니다. 게다가 실행 결과를 가지고 가능한 입력값을 만들라고 하니 당황할 수 밖에 없었을 겁니다. 사실 제가 맞닥트렸어도 매우 당황했을 겁니다. 일단, 가희와 프로세스의 나온 입력 ..
알고리즘/ps 2021. 11. 1. 04:31
in place 알고리즘에 대해서 간단하게 알아봅시다.

정렬 알고리즘을 배우면서, stable 한지 그렇지 않은지는 많이 본 거 같습니다. 그런데 in-place 한지 여부도 분명 다룬 거 같았습니다. 그런데, 저는 이 부분에 대해서 잘 신경을 쓰지는 않았는데요. 쉽게 간과할 정도로 무지했던 셈입니다. 정리할 겸 겸사겸사 알아보도록 하겠습니다. 먼저, in place 알고리즘은 추가적인 메모리를 쓰지 않는 알고리즘? 그런데 아주 약간의 메모리를 써도 되는 알고리즘 정도로 문서에서 언급하고 있어요. 제가 보는 교과서에서는 constant한 공간을 쓰면 in-place 알고리즘이라고 언급하고 있습니다만, 대충 인풋 크기에 비해 정말 작은 메모리를 쓴다. 정도로만 이해하고 넘어가셔도 좋겠네요. 대충 input size가 500만 정도라고 생각해 보면, int나 l..
알고리즘/이론 2021. 9. 27. 04:21
반응형