알고리즘&자료구조(algorithm& data structure)
-
[프로그래머스]해시-위장 문제 풀이알고리즘&자료구조(algorithm& data structure)/프로그래머스(programmers) 2021. 1. 3. 16:36
programmers.co.kr/learn/courses/30/lessons/42578?language=javascript 코딩테스트 연습 - 위장 programmers.co.kr 1. 종류별로 구분한다. 2. 종류1 2개, 종류2 1개 인 경우를 생각해보자. 2.1 종류1에서 하나를 뽑거나 안 뽑을 수 있다. 따라서 경우의 수는 하나를 뽑는 경우는 두 가지 + 안 뽑는 경우는 1 =>3 2.2 종류2에서 하나를 뽑거나 안 뽑을 수 있다. 하나 뽑는 경우는 한 가지 + 안 뽑는 경우 1 => 2 2.3 2.1의 경우의수와 2.2의 경우의 수를 곱하면 3*2인 6이 된다. 즉, 종류 1에는 {"a","b"}, 종류 2에는 {"z"} 가 있었다고 하면 위에서 가정한 조합은 다음과 같다. {"a", "b" ,..
-
[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가 된다고 가정하였습니다. 예를 들어 (()))..
-
[프로그래머스 / 고득점 kit] 탐욕법: 조이스틱 ver2알고리즘&자료구조(algorithm& data structure)/프로그래머스(programmers) 2019. 7. 24. 03:52
0. 문제링크 1. 풀이방법 설명 2. 코드첨부 0. 문제링크 https://programmers.co.kr/learn/courses/30/lessons/42860# 코딩테스트 연습 - 조이스틱 | 프로그래머스 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 예를 들어 아래의 방법으로 JAZ를 만들 수 있습니다. - 첫 번째 위 programmers.co.kr 1. 풀이..
-
[프로그래머스 / 고득점 kit] 탐욕법: 조이스틱- ver 1알고리즘&자료구조(algorithm& data structure)/프로그래머스(programmers) 2019. 7. 24. 01:54
스틱 움직임을 시작시에 오른쪽과 왼쪽으로 구분하여 풀어가면서 더 복잡해 지는 경우가 발생한다. 1.오른쪽으로 가다가 왼쪽으로 되돌아 가는경우. 2.왼쪽으로 가다가 오른쪽으로 되돌아 가는경우. 해결 : 애초에 오른쪽으로 가는것을 기준으로 하고 되돌아 가야 할 때 되돌아 가도록 짜면 될 것 같다. 코드 첨부: i = 0 alpha_dict = {} for x in "ABCDEFGHIJKLMNOPQRSTUVWXYZ": if i
-
[programmers/ 고득점 kit] 정렬: 가장 큰수알고리즘&자료구조(algorithm& data structure)/프로그래머스(programmers) 2019. 7. 16. 21:52
이 문제를 풀면서 permutation, compare function 등 여러가지 학습을 할 수 있었다. 결국, 정렬을 위하여 직접 더해본 것을 비교해 봐야함을 알 수 있었다. 여러가지 경우를 다 체크하다 보면 시간이 오래 걸리므로 핵심이 되는 비교의 기준을 잡는 것이 중요했다. 입력데이터로 [12,121], [21,212] ,[0,0,0,1000], [20,201] 등 여러 데이터가 있었다. 최종적으로 테스트 했던 결과를 문제 링크 아래에 첨부해둔다. 1. 문제링크 https://programmers.co.kr/learn/courses/30/lessons/42746 알고리즘 연습 - 가장 큰 수 | 프로그래머스 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 ..
-
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:
-
[programmers/ 고득점 kit] 해시: 베스트 앨범알고리즘&자료구조(algorithm& data structure)/프로그래머스(programmers) 2019. 7. 13. 11:30
dictionary data type을 활용하여 푸는 문제 python에서 stl의 compare와 같은 구현을 통하여 원하는 방식으로 sort할 수 있다. python 3.x 버전 부터는 sorted 인자로 key = cmp_to_key(보조 함수이름)를 통하여 구현 가능. dict를 sort 할 때 sorted(dict, ...) 로 구현하면 key만 가지는 list가 리턴되니 조심하자. 아래에는 1.문제링크, 2.code, 3.테스트 케이스 순으로 첨부하였다. 1.문제링크 https://programmers.co.kr/learn/courses/30/lessons/42579 알고리즘 연습 - 베스트앨범 | 프로그래머스 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을..