본문 바로가기

알고리즘

 (19)
나의 코딩테스트 공부법 안녕하세요. 게임클라이언트로 근무하고 있는 두부입니다. 최근 홍정모 교수님이 알고리즘의 중요성에 대해 많이 이야기해주셨는데, 제가 이번에 쓰는 대상은 교수님이 말씀하신 근본적인 알고리즘과는 거리가 좀 있을지 모르겠지만, 그래도 코딩테스트 문제풀이를 준비하시는 분들에게 저의 경험과 공부방법을 공유해보고자 이런 글을 작성하게 되었습니다. ​ 평소 조금씩 알고리즘을 공부해오다가 어느날 이직이 하고싶어서 국내 이런저런 회사에 코딩테스트를 봤는데 보는 곳 마다 합격해버리고 심지어 한 회사에서 제가 코딩테스트 제일 잘 본 편이라는 말까지 듣게되는 경험을 하게 되었습니다. 제가 본 회사중에 코딩테스트 컷이 높은 회사가 없기도 하였지만.. 뒤늦게 알고리즘 시작한 사람으로써 이렇게 공부하고 이정도 결과를 만들었다는 걸 ..
[cpp]사라지는 발판 - 2022 카카오 블라인드 채용 플레이어 A와 플레이어 B가 서로 게임을 합니다. 당신은 이 게임이 끝날 때까지 양 플레이어가 캐릭터를 몇 번 움직이게 될지 예측하려고 합니다. 각 플레이어는 자신의 캐릭터 하나를 보드 위에 올려놓고 게임을 시작합니다. 게임 보드는 1x1 크기 정사각 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 있습니다. 발판이 있는 곳에만 캐릭터가 서있을 수 있으며, 처음 캐릭터를 올려놓는 곳은 항상 발판이 있는 곳입니다. 캐릭터는 발판이 있는 곳으로만 이동할 수 있으며, 보드 밖으로 이동할 수 없습니다. 밟고 있던 발판은 그 위에 있던 캐릭터가 다른 곳으로 이동하여 다른 발판을 밞음과 동시에 사라집니다. 양 플레이어는 번갈아가며 자기 차례에 자신의 캐릭터를 상하좌우로 인접한 4개의 칸 중에서..
[cpp]자물쇠와 열쇠 - 2020 카카오 블라인드 채용 고고학자인 “튜브”는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다. 자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 ..
[cpp]카카오프렌즈 컬러링북 - 2017 카카오코드 예선 그동안 푼 문제들을 하나씩 정리해서 조회수를 올려야겠다. 카카오 문제 위주로 올리면 많이 보겠지? 이 문제는 대표적인 BFS/DFS 문제로 정말 흔하게 많이 나오는 문제이다. 처음에 접근하기 힘들 수는 있지만, 유형만 익혀두면 쉽게 풀 수 있는 문제이니 이러한 유형을 꼭 익혀주도록 하자. 문제를 보자마자 기본 템플릿을 지워버려서 몰랐는데 전역변수 사용시 함수 안에서 초기화를 해야한다고 한다. 풀이 1. 최대 영역 구하기 그림의 영역 구분은 '상하좌우로 연결되어 있는지' 를 기준으로 한다. 따라서 탐색의 시작 좌표를 기준으로 상하좌우로 같은 색깔이 몇개나 있는지 체크해주면 된다. 이때 탐색은 (0,0) 영역부터 (m,n)영역까지 순차적으로 이동하며 수행한다. 같은 공간을 두번 체크하지 않도록 2차원 boo..
백준14502번 - 연구소(C++, 삼성 SW 역량 테스트 기출 문제) 삼성 A형을 목표로 백준 문제풀이를 진행하고 있습니다. 처음 삼성 문제를 풀때 '이렇게 풀어도 되나?' 싶을 정도로 무식하게 구현하다가 제출한 문제에 '맞았습니다'가 뜨는걸 보고 삼성 A형 스타일 문제가 어떤 느낌인지 알게 되었습니다.. 괜히 머리 굴리면서 효율적인 문제풀이 방법을 생각하기 보다는 그냥 있는 그대로 구현하는게 정답이였습니다. 다만 구현이 좀 복잡하기 때문에 main함수에 무식하게 구현하기 보다는, 기능 하나하나를 함수화하여 푸는게 간편하다고 느껴졌습니다. 아래 문제집에서 이제 겨우 4문제를 푼 어린이지만.. 1일 1문제씩 풀어서 2월달에 A형 시험을 꼭 합격해보도록 하겠습니다. 문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon) www.acmicpc.net #include #d..
수식최대화 - 2020 카카오 인턴십 코딩테스트(파이썬) 나도 카카오 문제를 풀어봤다! 문제 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다. 해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산 문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 ‘미션’은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다. 단, 연산자의 우선순위를 새로 정의할 때 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > ..
백준 200문제 달성 후기 2021.08.16 백준 알고리즘 200문제 달성 이전까지는 뭐를 공부해야할지도 몰라서 그냥 눈에 보이는 문제들만 풀어왔다면, 200문제 정도 푸니까 이제 뭐가 부족하고 어떤걸 공부해야할지 감이 오는듯 하다. 구현문제는 나름 자신있었는데.. 조금 어려운 구현문제를 보다보니까 내가 구현을 잘한다고 착각하고 있었다는걸 깨달았다. 풀때는 제일 재밌는데 조건 하나씩 틀리기 시작하면 진짜 멘붕.. 그래도 어떻게 풀어야할지 감이 하나도 안오는 DP보다는 구현이 편하다 ㅜ 문제 난이도 분포 거의 브론즈문제를 풀어서 해결한 문제 수를 뻥튀기 시켰다. 무려 4가지 언어를 백준에서 연습했어서(C#, C++, JS, Python) 브론즈 문제의 비중이 유독 높은것같다. 앞으로의 목표는 실버문제를 옛날 브론즈 문제 풀듯이 슉..
172번 Factorial Trailing Zeroes 풀이(c++) 풀이 해설을 요청하신 분이 있어서.. 이 문제는 'trailing zero'을 구하는 문제이다. 숫자의 가장 뒤에 연속해서 붙어오는 0의 갯수를 세는 문제라고 말해도 될것같다. (단 0인경우에는 숫자를 세지 않는다) 처음에는 주어진 숫자를 문자열로 바꿔서 맨 뒤에 있는 0의 갯수를 세는걸로 생각했지만, 더 효율적인 방법이 있을거라 판단하고 생각하다보니 한 가지 규칙을 발견하게 되었다. n! = x * 10^r 맨 뒤에 연속해서 오는 숫자가 r이라고 할 때, 위와 같은 수식으로 문제를 바꿔서 표현할 수 있다. 오히려 '맨 뒤에 있는 0의 갯수'보다 위 식이 훨씬 간결하고 정확하게 문제를 정의하고 있다. 즉, n!을 소인수분해하여 나오는 10의 갯수가 이 문제의 정답이 된다. 10을 소인수분해하면 '2*5'..

티스토리툴바