알고리즘&자료구조(algorithm& data structure)/문제풀이(problem solving)
-
[2020 카카오공채 코딩테스트 1번(문자열 압축) 풀이]알고리즘&자료구조(algorithm& data structure)/문제풀이(problem solving) 2020. 3. 12. 20:11
카카오공채 코딩테스트 1번 문제 풀이입니다. 문자열 압축 문제이며 서브 스트링을 반복문을 활용하여 체크하면 됩니다. python의 슬라이싱 기능을 적극 활용하면 되는 문제입니다. 최소단위 1부터 최대단위 문자열길의/2 까지 확인하면 됩니다. 즉 문자가 9개인 문자열이라면 1개 단위부터 4개 단위까지 체크하면 됩니다. 모든 단위에 대해서 문자열 압축을 진행한 후 최소값을 찾아야 하기 때문에 모든 케이스를 커버하는 일반적인 문자열 압축 함수를 만들면 되겠습니다. 문자열의 길이가 문자열에 의해 결정되므로 길이를 입력으로 하는 함수를 만들면 편리합니다. 즉, 입력은 체크 단위, 출력은 압축된 문자열을 하는 함수 모듈을 만들어 사용하면 되겠습니다. 내부 코드 구현은 서브스트링을 특정 구간에 대해서 일치하는지 확인..
-
[2020 카카오공채 코딩테스트 2번(괄호 변환) 풀이]알고리즘&자료구조(algorithm& data structure)/문제풀이(problem solving) 2020. 3. 12. 19:55
카카오 공채 코딩테스트 2번 풀이 글입니다. 2번 문제는 설명에 주어진 그대로를 구현하는 문제이며 재귀, 함수에 대한 개념이 명확하게 있어야 풀 수 있습니다. 우선 문제 설명을 이해하는 것이 제일 어려웠습니다. 예시에서 u의 변환 부분이 추가 되는 것이 '('와 ')' 사이인지 뒤인지 모호하게 설명되 있어서 이 부분을 명확하게 캐치하는 것이 핵심입니다. 저는 다양한 테스트 케이스를 직접 확인해가면서 문제의 설명을 정확하게 이해하였습니다. 우선 균형잡힌 괄호 문자열을 파악하는 함수를 만들어 2번을 해결합니다. 애초에 주어진 문자열이 '('와 ')' 의 짝이 맞으므로 저는 문자열 처음 부터 (의 개수와 ) 을 각각 카운트하여 같게 되는 지점을 균형잡힌 문자열 u가 된다고 가정하였습니다. 예를 들어 (()))..
-
permutation알고리즘&자료구조(algorithm& data structure)/문제풀이(problem solving) 2019. 7. 14. 23:07
input data : ['1','2','3'] output data: ['123','132','213','231','312','321'] 핵심 아이디어 '1'을 피봇으로 놓고 ['2','3']에 대해 함수 호출 -- > ['23','32']가 리턴 될 것 예상 '2'을 피봇으로 놓고 ['1','3']에 대해 함수 호출 종료 조건은 아이템이 하나인 경우이며 코드의 수정에 따라 1. [['1','2','3'],['1','3','2'], ...] 와 2. ['123','132' ... ]로 나뉨. 재귀를 이용해야 하나 코드 구현이 생각보다 어려움. code: