The Way

*.. .*. *.. 와 같은 식으로 n * n 크기의 board가 주어질 때, manhattan distance를 기준으로 정삼각형을 이루는 세 쌍의 *의 수를 구하는 문제이다. 모든 쌍을 다 해보려면 시간 복잡도는 $O(n^6)$이고, 점을 두 개만 고르면 나머지 한 점의 가능한 위치는 정해지므로 이 방법을 사용한다 해도 시간 복잡도는 $O(n^4)$이다. n = 300이므로, 조금 더 나은 방법을 찾을 필요가 있다. 먼저 적절한 관찰을 통해 정삼각형이 가지는 특징을 알아낼 필요가 있다. 한 변의 길이가 d인 정삼각형은 적절한 90도 단위의 회전을 통해, 좌표가 $(p, q), (p + x, q + (d - x)), (p + y, q + (d - y))$ $(0 \le x \le d, 0 \le y ..

2차원 평면에 검은 점과 하얀 점이 각각 N개씩 찍혀 있다. (으레 기하 문제가 그렇듯 임의의 세 점이 한 직선 위에 있지는 않다고 치자) 이제 우리는 각각의 검은 점에 하얀 점 하나씩을 선분으로 이어 주려고 한다. 단, 선분끼리 교차하지 않아야 한다. 총 N개의 선분을 그어 모든 하얀 점과 검은 점들을 이어줄 수 있을까? 대충 이어보면 생각보다 잘 이어지긴 한다. 하지만 모든 점들을 이어주는 것이 항상 가능할까? 예를 들어서 N = 10만 정도이고 검은 점과 하얀 점이 복잡하게 얽혀 있는 경우에도 가능할까? 결론을 먼저 말하면 가능하다. 이를 증명하는 방법은 여러 가지가 있는데, 이 중 매우 깔끔하면서 재미있는 방법을 하나 소개한다. 많은 내용의 출처는 SW Expert Academy - Learn -..

문제는 아주 심플하다. N * M짜리 배열에서, 1≤i

쿨...쿨... 4번 풀고 싶다...

매일 저녁 6시경에 하루 3백준(≥플레 1문제, 골드 1문제, ≤실버 1문제)을 랜덤으로 뽑아서 풀고 있는데, 보통 플레 이상은 풀 확률이 반반 정도 되는 편. 그 중 간만에 재미있는 문제 하나를 발견해서 기록을 남겨본다. 초기 0, 1, 2가 들어있는 집합이 있고 이 집합의 원소 중 x, y 둘을 골라(같아도 됨) $x^2 - y$를 집합에 추가해주는 operation을 가해줄 수 있다. 최대 43번의 operation을 가해서 $10^{18}$까지의 숫자를 만드는 것이 문제의 목표이다. 정답은 뭐 크게 어렵지 않고, p를 만들려면 $x^2 \ge p$를 만족하는 가장 작은 x를 찾고, y는 $x^2 - p$를 사용하면 된다. 이후 x, y 만들기를 목표로 이 과정을 반복하면 된다. p의 크기는 최대 ..

드디어 백준에도 인터랙티브 문제들이 생겼다. Codeforces에 이따금 출현하는 인터랙티브와는 사뭇 다른 느낌인데, 코포에서는 입출력을 통해 통신(?)을 한다면 백준은 함수 호출을 통한 인터랙티브를 사용한다. 삼성 B형에도 이따금 출제되는 유형이기도 하니, 코딩테스트를 목표로 하는 사람이라면 한번쯤 풀어보아도 좋을 듯 하다. 뒹굴면서 페북을 보다가, 인터랙티브 테스트 대회라고 있길래 후다닥 해보았다. 비공식 대회지만 처음으로 1등했다.. ㅋㅋ 내가 잘했다기보다는 잘하는 사람들이 크게 관심을 안가진 덕이 크다. 백준 18158. What an Easy Problem 생략. 문제를 잘 읽읍시다. 18158.cpp 백준 18159번. Have You Ever Sorted an Array? 1~n으로 구성된 ..

대회 망한 4솔따리지만 꾸역꾸역 써봅니다... 서론) 작년에 대회를 같이 나갔던 팀원들은 다들 군대라든가, 타 대학원이라든가 멀리 떠나갔고, 새로운 팀원들 2명을 구해서 3달간 그래도 정기적으로 연습을 해보았다. 이번에는 i) 문제 푸는 것을 재미있어하고, ii) 열심히 할 사람들을 기준으로 팀원을 구했는데, 그리 좋은 기준이었는지에 대해서는 의문이 든다. 팀원들이 석달간의 연습을 통해 코포 블루 중위권(1700점 정도)까지는 올라와주는 것이 목표였지만, 실력이 생각보다 잘 늘지 않아 결국 1500점도 아닌 1200점 언저리에 위치한 팀원들을 보고 그닥 대회에 대한 의욕이 많이 생기지는 않았다... 여담으로 만약 한 번의 기회가 더 주어진다면 이번에는 수학을 잘 하는 사람들 위주로 팀원을 구해보지 않을까..

잠이 잘 안와서 가볍게 쓰는 글. 유니콘의 이동 경로대로 문자열을 만들 때 가능한 경우의 수를 구하는 문제. 유니콘은 나이트랑 비슷하게 움직이는데, 나이트는 (2칸, 1칸)을 움직이는 대신 유니콘은 (3칸 이상, 2칸 이상)을 움직여야 한다. 유니콘이 이동할 수 있는 곳들을 보드판에 나타내보면 다음과 같다. 상당히 예쁜 모양. 같은 맥락에서, 색칠된 위치에 유니콘이 있었다면 다음 턴에 Uni의 위치로 이동가능하다는 말도 된다. 결국 맨 처음에 문자열의 0번 위치와 같은 문자들이 놓인 보드판에 경우의 수 1씩을 할당하고, 그 다음부터는 문자열과 같은 문자가 쓰여진 보드판에 저 위치의 경우의 수의 합을 차례로 할당하면 된다. 보드판 크기가 300이고 L은 26이므로 복잡도는 단순 구현시 $300^4 \tim..

주어진 종이를 여러 번 적당히 잘 접어서 만들 수 있는 가장 큰 수를 찾는 문제이다. 접어서 같은 위치에 겹치게 되는 숫자는 합해주면 된다. N과 M이 12 이하이므로, 완전 탐색 문제라는 것은 어렵지 않게 알 수 있다. 다만 완전 탐색 치고 생각보다 까다롭다. 가로를 접는 경우의 수와 세로를 접는 경우의 수는 순서로 따지면 각각 넉넉잡아 11!개 정도이고, (실제로는 7만 4000개 정도이다), 겹쳐진 상태만 고려한다고 해도 $2^{12}$ 가지이다. 둘을 곱해주면 $2^{24}$ 정도로 시간초과나기 딱 좋은 수치이다. 약간 관찰을 해 보면 겹쳐진 상태가 $2^{12}$가지 보다는 훨씬 더 적다는 것을 알 수 있다. 예컨대 길이 4개짜리를 접어서, 1, 3, 4번만 겹치도록 만드는 것은 불가능하다. 그..

아직 미필이기 때문에 지원 자격은 안되지만, 어떤 문제가 나오는지 궁금해서 쳐봤다.오후 2시~오후 7시까지 5시간동안 진행되며, 7문제를 풀면 된다.https://www.welcomekakao.com/competitions/102/2020-kakao-blind-recruitment 난이도는 대개 기업의 코딩테스트가 그렇듯 어려운 편은 아니다.나는 약속도 있었고, 괜히 한명의 탈락자를 만드는 불상사가 발생할까봐 오후 5시에 시작해서, 2시간동안 7문제 중 5문제를 풀었다. 10분 정도 더 있었으면 6문제를 풀었을 듯... 한 가지 느낀 점은 기업 코딩테스트라 코딩스타일을 "통용적으로 좋은 스타일로 여겨지도록" 작성할 필요성이 있다.예를 들어서 그냥 백준을 풀 때는 전역변수를 사용할 때 전혀 망설임이 없었지..