💻 프로그래밍/알고리즘
-
2019 카카오 1차 코딩테스트 문제 3 (자물쇠와 열쇠)💻 프로그래밍/알고리즘 2019. 11. 10. 23:59
1. 문제 (정답률: 7.4%) 고고학자인 “튜브”는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다. 자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 ..
-
2019 카카오 1차 코딩테스트 문제 1 (문자열 압축)💻 프로그래밍/알고리즘 2019. 11. 10. 21:13
1. 문제 (정답률: 25.9%) 데이터 처리 전문가가 되고 싶은 “어피치”는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 “aabbaccc”의 경우 “2a2ba3c”(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, “abcabcdede”와 같은 문자열은 전혀 압축되지 않습니다. “어피치”는 이러한 단점을 해결하기 위해 문자열을..
-
LCS (Longest Common Subsequence) 최장 공통 부분 수열💻 프로그래밍/알고리즘 2019. 6. 23. 16:42
안녕하세요! 코딩하는 JAY입니다. 오늘은 오랜만에 알고리즘 포스팅을 하려고 합니다:D 오늘 포스팅할 내용은 LCS, 최장 공통 부분 수열입니다. 주의해야할 점은 LCS가 두개라는 점입니다. 1. 최장 공통 부분 수열 = Longest Common Subsequence 2. 최장 공통 부분 문자열 = Longest Common Substring 이 두개의 차이저을 아래 예시로 말씀드리겠습니다. 1. ABCD, ABZC = AB 2. ABCD, ABZC = ABC 1번과 2번 예시의 차이점을 아시겠나요? 아마 차이점을 바로 눈치채셨을것 같아요 ㅋㅋㅋ 1번은 두개의 문자열을 비교했을때, 연속적인 문자열을 추출합니다. 2번은 공통된 부분 수열을 추출합니다(연속X) 여기서 핵심은 연속이냐? 아니냐 입니다 ㅎㅎ ..
-
[python]백준 알고리즘 11403 경로찾기💻 프로그래밍/알고리즘 2018. 1. 7. 00:05
안녕하세요! 코딩하는 JAY입니다. 다들 2018년 새해계획은 잘 세우셨나요?!ㅎㅎㅎ거창한게 아니더라도 새해에 각오, 목표 하나씩 세우면 동기부여도 되고 좋은 것 같습니다. (좋아연~:D)오늘 부터 '백준 알고리즘' 문제 포스팅을 하려고 합니다! 알고리즘에 대해서 많이 부족하기도 하고, 소프트웨어 개발할때 많은 도움이 될 것 같아서 올해부터 꾸준히 하려고 합니다. ※ 11403번 경로찾기오늘 풀어볼 문제는 '경로찾기'입니다. DFS(깊이우선탐색) 문제인데요. 예제입력1을 기준으로 문제를 설명하면 이렇습니다. (i, j)가 1일 경우 i에서 j로 가는 경로가 있다는 의미 입니다. 오른쪽 그림을 보면 이해하기 쉬우시죠?! 자, 여기서 i에서 j로 가는 경로가 있으면 j에서 i로 가는 경로도 있다는 의미입니다..
-
카카오 1차 온라인 코딩테스트 7번 문제(17.09.16)💻 프로그래밍/알고리즘 2017. 10. 20. 08:13
안녕하세요~ 코딩하는 JAY 입니다!! 오늘은 대망의 마지막 7번문제를 포스팅하겠습니다. (끼야옭~~~~~~~~) 7번문제는 가장 어려웠던 문제인 것 같습니다. 흠... 어렵다기 보다는 생각이 조금 필요한 문제였던 것 같아요. 일단 문제를 한번 보죠~ 문제 및 풀이 링크 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/ 7. 추석 트래픽(난이도: 상)이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 ..
-
카카오 1차 온라인 코딩테스트 6번 문제(17.09.16)💻 프로그래밍/알고리즘 2017. 10. 16. 23:41
안녕하세요! 개발하는 JAY입니다~ 오늘하루 즐거우셨나요?? 저는 요새 유일한 낙이 블로그 포스팅과 알고리즘 문제 푸는 겁니다:D 여러분들도 힘들고 많은 고민들 있으시겠지만, 그래도 우리 조금만 더 힘내서 더 좋은 개발자가 되봅시다!! 고생한 만큼 낙이 온다고도 하잖아요~^^ 자! 오늘은 6번문제를 한번 풀어보도록 하겠습니다. 문제 및 풀이 링크 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/ 6. 프렌즈4블록(난이도: 상)블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 “프렌즈4블록”. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 ..
-
카카오 1차 온라인 코딩테스트 5번 문제(17.09.16)💻 프로그래밍/알고리즘 2017. 10. 15. 21:40
안녕하세요! 개발하는 JAY입니다. 추석연휴가 끝나서 이번 포스팅은 조금 늦게 올리네요 ㅠㅠ(추석후유증이 정말 큽니다..크흑) 마지막 문제까지 이제 얼마 안남았네요! 힘차게 달려봅시다!! 이번 포스팅은 5번문제를 풀어보겠습니다. 문제 및 풀이 링크 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/ 5. 뉴스 클러스터링(난이도: 중)여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다.개발의 방향을 잡기 위해 튜브는 우선 최근..
-
카카오 1차 온라인 코딩테스트 4번 문제(17.09.16)💻 프로그래밍/알고리즘 2017. 10. 8. 20:59
안녕하세요 JAY입니다~!! 오늘은 카카오 1차 온라인 코딩테스트 4번 문제를 풀어보겠습니다. 4번 문제는 조금 생각을 정리해야지 풀 수 있기 때문에 집중하시고 문제풀어 보시는게 좋습니다!! 문제 및 풀이 링크 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/ 4. 셔틀버스(난이도: 중)카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 ‘크루’라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객..