코딩 맛집

이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부 book.naver.com '문자열 뒤집기' 문제 입니다. 특정 문자열이 주어지고, 문자열은 0과 1로만 이루어진 문자열 입니다. 0 -> 1 로 뒤집거나, 1 -> 0 으로 뒤집을 수 있습니다. 연속적으로 뒤집는것을 한번의 행동이라고 했을때, 주어진 문자열을 최소 몇번 뒤집어야 문자열을 전부 뒤집을수 있을까요? 1. 접근 1. 문자열을 전부 돌면서 2. 연속적인 수를 카운트 합니다. 3. 0이 연속적인 경우 4. 1이 연속적인 경우 5. 둘중 더 작은 값을 출력 합..

이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부 book.naver.com 바닥이 세로(2) x 가로(N) 으로 되어 있는 바닥을 덮을 때, (1 x 2), (2 x 1), (2 x 2) 덮개로 채울 수 있는 모든 경우의 수를 출력 하는 문제 입니다. 결과 값이 클 수 있으므로 796,796으로 나눈 나머지를 출력 하는 문제 입니다. 이 문제의 점화식은 (i - 1) 인 경우는 (2 x 1) 타일 하나 만 덮을 수 있는 경우가 존재 합니다. (i - 2)의 경우는 (1 x 2) 2개 로 덮는 경우와, (2 x 2)..

이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부 book.naver.com 바닥이 세로(2) x 가로(N) 으로 되어 있는 바닥을 덮을 때, (1 x 2), (2 x 1), (2 x 2) 덮개로 채울 수 있는 모든 경우의 수를 출력 하는 문제 입니다. 결과 값이 클 수 있으므로 796,796으로 나눈 나머지를 출력 하는 문제 입니다. 이 문제의 점화식은 (i - 1) 인 경우는 (2 x 1) 타일 하나 만 덮을 수 있는 경우가 존재 합니다. (i - 2)의 경우는 (1 x 2) 2개 로 덮는 경우와, (2 x 2)..

이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부 book.naver.com '개미 전사' 문제에 대해서 풀어 보겠습니다. 1차원으로 나열된 메뚜기 창고 에서 각 식량의 갯수가 주어졌을 때, 최소 한칸 이상 떨어져 있어야 식량 창고를 털 수 있습니다. 이 털 수 있는 최대 식량의 갯수를 출력 하는 문제 입니다. 1. 접근 1. 짝수인 창고 칸만 털 경우 2. 홀수인 창고 칸만 털 경우 3. 두 경우 중 더 큰 경우 출력 처음에는 위와 같이 접근 했다. 하지만, 창고가 2칸 떨어져서 털 경우와 임의로 더 큰 경우가 있..

이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부 book.naver.com 두 배열 A, B가 주어지고, 두 배열의 크기 N이 주어지고, 배열 A의 원소와 배열 B의 원소 하나씩 바꿔치기를 K번 할수 있습니다. K번 바꿔치기를 수행하고 배열 A의 합의 최대값을 구하는 문제 입니다.(상세한 조건은 책을 참고해 주세요.) 1. 접근 먼저, 굉장히 쉬은 정렬 문제라고 생각하고, 다음과 같이 접근을 시도 했습니다. 1. K번 반복 수행을 하면서 2. 배열 A, B를 정렬 하고 3. 배열 B의 원소값이 배열 A의 원소값 보..

이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부 book.naver.com 이 책에서 '게임 개발' 이라는 문제에 대해서 구현 해보려고 합니다. 문제를 간략히 설명해 보면, N x M의 게임 맵의 대한 정보가 주어지고, 1은 바다, 0은 육지로 되어 있는 게임 맵에서 게임 캐릭터의 위치 (x, y) 정보가 주어지고, 캐릭터가 바라보고 있는 방향(북-0/동-1/남-2/서-3) 정보가 주어졌을 때, 게임 메뉴얼 대로 동작 한 후, 캐릭터가 이동한 최소 칸 수를 구하라는 문제 입니다. 1. 먼저 메뉴얼(*메뉴얼의 내용은..

'이것이 취업을 위한 코딩 테스트다 with 파이썬' 의 수록된 문제를 풀어 보겠습니다. 문제 제목은 '미로 탈출' 문제 입니다. 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부 book.naver.com 2차원 미로 속의 값이 0인 칸은 피하고, 1인 칸으로 만 이동해서, 출발점 : (0, 0), 도착점 : (N * M) 까지의 최소칸의 갯수를 구하는 문제 입니다. 구현하기 전에 먼저 고민 했습니다. 1. BFS와 DFS를 이용해서 탐색을 하는데, 최소 칸은 어떻게 구할수 있을지... 2. BFS와 DFS를 모두..

카카오 가사 검색 문제를 풀어 보았습니다. 아래 링크(프로그래머스) 에서 풀어 보실수 있습니다. 코딩테스트 연습 - 가사 검색 programmers.co.kr 처음의 다양한 접근 방법을 생각해 봤습니다. 1. word의 길이와 query의 길이가 같은 것들만 순차 탐색으로 찾는 접근 2. word들을 모두 합쳐서 하나의 문자열에서 query의 패턴을 kmp로 찾는 접근 하지만, 2가지 방법 모두 실패 하였습니다. 1번 방법은 일반 테스트는 모두 통과하지만, 효율성 테스트에서 실패 2번 방법은 완전히 매칭되는 단어를 찾는 문제이여서, 완전히 접근 방법 부터 틀렸습니다.(문제에서 접두사, 접미사 라는 단어가 나오길래, kmp를 의심;;) 다시, 이번엔 구글의 도움을 받아서 시도 했습니다. 1. 길이 별로 단..

1. 이진 탐색(Binary Search) 이진 탐색은 값이 정렬 되어 있는 상태에서 중앙 값을 이용해서 찾고자 하는 데이터의 위치를 탐색하는 알고리즘 입니다. 전체 탐색 범위(첫번째 인덱스, 마지막 인덱스)와 중앙 인덱스 알고 있다면, 중앙 인덱스의 값과 찾고자 하는 데이터의 값을 비교 해서, 더 작다면 왼쪽만 탐색, 더 크다면 오른쪽만 탐색 합니다. 따라서 우리는 3가지 변수를 알고 있어야 합니다. 첫번째 인덱스 : head 마지막 인덱스 : tail 중앙 인덱스 : mid = (head + tail) / 2 여기서, 중앙 인덱스의 나머지 값은 버리고, 몫만 사용 합니다. 2. 이진 탐색(Binary Search) 순서 위 그림과 같이, 찾고자 하는 target 값은 9 입니다. (target < a..

오늘은 플로이드 와샬(Floyd Warshall) 알고리즘에 대해서 포스팅 하겠습니다. 1. 플로이드 와샬 핵심 아이디어 플로이드 와샬(Floyd Warshall)도 다익스트라 알고리즘(Dijkstra algorithm)과 같이 특정 노드까지의 최단 거리를 구할 수 있는 알고리즘 입니다. 다익스트라 알고리즘(Dijkstra algorithm)은 one-to-all 알고리즘 입니다. 따라서 하나의 특정 노드로 부터 모든 노드까지의 최단 거리를 구할 수 있습니다. 하지만, 플로이드 와샬(Floyd Warshall) 알고리즘은 all-to-all 알고리즘 이므로, 모든 노드에서 부터 모든 노드 까지의 최단 거리를 구할수 있습니다. 각 노드 마다의 거리를 2차원 배열로 표현해 주고, 자기 자신의 노드까지 거리는..