알고리즘 썸네일형 리스트형 백준 9252 : LCS https://www.acmicpc.net/problem/9252DP 문제이다.진짜 모르겠어서, 낙담해버려 알고리즘을 4일 쉬게 만든 문제이다. 생각의 흐름우선 완전 탐색으로 하면 얼마나 걸릴까 생각을 해보았다.기본적으로 어떤 글자를 선택할 지를 결정하고, 비교하는 과정으로 진행한다고 가정했다.이때 어떤 글자를 선택하는 경우의 수가 곧 최종 시간 복잡도라고 봐도 되겠다.따라서$2^{1000} \times 2^{1000} = 2^{1001}$라는 어마어마한 수치가 나온다. 그래 우선 완전탐색은 안된다.그리고 예시를 따라가다보면, 그리디처럼 맹목적인 하나의 규칙이 있어보이는 것도 아니다.결국 완전탐색은 하면서도 효율적으로 해야하는 DP라는 감을 잡았다. 문제는 부분문제로 어떻게 쪼개야할 지 전혀 감이 오지 .. 더보기 백준 2217 : 로프 https://www.acmicpc.net/problem/2217 그리디 문제이다.풀이를 찾는데 살짝 헤맸는데, 그 과정을 주르륵 써보도록 하겠다.생각의 흐름알고리즘 분류 찾아서 들어간거라 그리디라는 건 알고 있었지만,완전탐색을 하게되면 얼마나 걸릴까 생각해보았다. 가능한 모든 로프의 경우의 수를 찾는 것이기 때문에,각 로프마다 (넣는다, 안넣는다) 2개의 선택지가 있어서 $O(2^n)$이 된다.$N$이 최대 100,000이었기 때문에 최소한 $NlogN$정도의 복잡도는 필요했다. 그래서 다음 단계로 그리디하게 생각해보기로 했다. 첫번째 삽질가장 처음했던 가정은, "값이 큰 로프부터 넣다가, 최대 중량 값이 작아지는 시점에 그만둔다" 였다.로프 값이 $t_{1} > t_{2} > t_{3} > ... >.. 더보기 백준 1026 : 보물 https://www.acmicpc.net/problem/1026비교적 간단한 그리디 유형 문제이다.생각의 흐름완전탐색을 이용하려면, B의 원소를 배열하는 경우의 수 = 최대 100! 까지 간다.100 팩토리얼은 진짜 오바기 때문에, 그리디를 생각하게 되었다. 간단~하게 생각하면 그냥$(A의 제일 큰 수 \times B의 제일 작은 수) + (A의 2번째로 큰 수 \times B의 두번째로 작은 수) + ...$이렇게 나아가면 될 것 같았다. 그렇다면 이게 답이라는 것을 어떻게 증명할 것인가?일단 최적해가 존재한다고 가정하고 생각을 해보았다.최적해를 수식으로 표현한 뒤에, 만약 그 수식대로 계산되지 않으면 무슨 일이 일어날 지에 대해서 생각해봤다.증명A의 원소를 a와 아래첨자로, B의 원소를 b와 아래첨.. 더보기 백준 1931 : 회의실 배정 https://www.acmicpc.net/problem/1931유명~한 문제이다.근데 안풀어본 것 같아서이참에 증명 과정도 알아보기로 했다. 일단 완전탐색을 하기에는... 지수 복잡도로 간다.회의를 배정하냐 마냐를 선택해야하기 때문에 $O(2^n)$가 된다. 그러면 이제 그리디를 생각해볼 수 있겠는데,1. 제일 짧은 것부터 고르기2. 제일 먼저 끝나는 것부터 고르기3. 제일 나중에 끝나는 것부터 고르기 뭐 사실 답이 2번이라는 건 알고 있었지만, 최소한 1번 3번의 반례와 2번이 정당한 이유를 제시하고 싶었다. 1번 반례우선 1번의 반례를 제시해보겠다.몇몇개의 블로그에서는 제일 짧은 것부터 고른다고 해서, 그 다음으로 짧은 게 선택 불가능하면 거기서 끝내버리는 예시를 제시했었다.근데 내 생각에 가장 짧.. 더보기 백준 1193 : 분수찾기 https://www.acmicpc.net/problem/1193내 풀이간단한 구현 문제이다. 입력값인 X가 10,000,000이므로 $O(n)$ 정도로 끝내야 한다. X번째 수를 알기 위해서는 위치에 대한 정보가 필요하다.1. 몇번째 대각선에 X번째 수가 위치하는지, 2. 몇번째 대각선에서 (위나 아래로부터) 또 몇번째 위치에 있는지를 알아야 한다. 1. 몇번째 대각선에 X번째 수가 위치하는지는 X에서 첫번째 대각선의 원소 개수를 빼고X에서 두번째 대각선의 원소 개수를 빼고X에서 세번째 대각선의 원소 개수를 빼다가...X가 0보다 작아지는 그 대각선의 위치를 구하면 된다. 그런데 나는 이 "대각선의 원소 개수"가 공차가 1인 등차수열이길래"총 대각선의 원소 개수"를 구하기 위해$\frac{n(n+1)}.. 더보기 당신의 기울기는 얼마입니까? : 시간복잡도와 공간복잡도 꾸준히 노력하는 것혹시 여러분들은 꾸준히 노력하고 있는 것이 있나요?예를 들자면, 알고리즘 풀이, 운동, 독서 또는 미라클 모닝과 같은 챌린지 말입니다. 만약 있다면, 여러분들의 실력 혹은 능력이 얼마나 빠른 속도로 늘었나요?누군가는 어떤 분야에 소질이 있어 빠른 속도로 높은 퍼포먼스를 낼 수도 있고,누군가는 난생 처음 해보는 분야라서 조금은 더딜 수도 있겠죠. 저 같은 경우에는, 최근 수영을 배우고 있습니다.일주일에 3번, 겨우 45분만 투자하고 있는데요.원래도 물에서 노는 것을 좋아하고 물에서 뜨거나 눈을 뜨는 재롱(?) 등은 할 수 있는 상태여서인지제 생각보다도 빠르게 실력이 늘고 있는 것 같습니다. 이와 유사하게, 알고리즘에서는 문제를 얼마나 빨리 해결할 수 있는지를 "시간복잡도"라고 표현합니다... 더보기 취업을 위한 코테 톺아보기 아래 내용은 책 "이것이 취업을 위한 코딩테스트다"의 내용을 바탕으로 추가조사한 내용을 정리한 것입니다.개발자 취업을 위한 여정동아리 신규부원 뽑기저는 별거 아니지만 교내 개발 동아리에서 운영진으로 참여한 경험이 있습니다.나름 수준 높은(?) 동아리라서 서류 + 면접을 통해서 신입 부원을 선발했었고, 선발자로서 2번의 경험을 해보았었죠. 한 번은 해당 기술 파트의 교육자 또는 멘토로서 참여했었고, 또 한 번은 동아리의 운영을 담당하는 운영자로서 참여했었습니다.총 합쳐서 50번 정도는 면접을 봤던 것 같고 그 반대로 면접자로서도 한 번 참여했었었죠. 그 동아리는 생긴 지 얼마 안되었기 때문에, 시스템이라고 할 게 그렇게 완벽하지 않았습니다.말하자면, 아무나 들어오면 동아리가 망하는 상황이었죠.막상 당시에는.. 더보기 코딩 테스트를 여행하는 개발자를 위한 모든 준비법 개요제목으로 어그로를 끌어보고 싶어서 이렇게 작성했지만...이 글은 그저 제가 코테를 준비하기 위해서 환경을 세팅한 내용을 정리한 글입니다. 저는 현재 당장의 취업에 있어서 코딩테스트를 통과할 지 말지 확신이 없는 흔한 골레기입니다.. 마지막으로 백준을 풀어본 게 언제인지도 기억이 안납니다.그래도 돈을 벌어야하고 취업은 해야하잖아요?주변 동기들은 졸업도 전에 취업하는 친구들이 몇몇 보이기 시작하고,개발자 취업은 계속 어렵다고 하고 정작 내세울 포트폴리오가 하나도 없는 것 같고,AI는 이제 나보다 코딩 훨씬 잘하는 것 같고,이 세상에 내가 왜 필요한 지 모르겠고.... 이런 상황에서 코딩테스트 공부 준비를 본격적으로 해봐야겠다고 생각한 것은 용기 있는 결정이 아니라상황에 이끌려 도달한 종점일지도 모르겠습니.. 더보기 이전 1 2 다음
