본문 바로가기

알고리즘 & 코딩테스트

 (48)
Programmers Lv.1 "크기가 작은 부분문자열" 주어진 문자열 t에서 p의 길이만큼 앞에서 부터 순차적으로 잘라 하나의 리스트에 다 담는다. 그 뒤 각 요소에 대해 크기를 비교하여 정답을 추출해주면 된다~! def solution(t, p): answer, temp= 0, [] for idx in range(0, len(t)-len(p)+1): temp.append(t[idx:idx+len(p)]) for target in temp: if int(target)
Programmers Lv.1 "최소직사각형" 문제를 잘 읽어보면 주어진 가로길이의 최댓값, 세로길이의 최댓값을 선택하는 단순한 문제가 아님을 알 수 있다. 즉, 각 명함의 크기가 가로, 세로의 전환도 고려해야한다는 것. 가장 심플한 해결방법은 주어진 sizes를 반복을 하되 큰값을 가로와 세로 중 어디로 할 것인지 임의로 정한뒤 순차적으로 비교하여 최대의 수치를 저장해주면 된다. 아래 코드를 보면 이해가 될 것이다. def solution(sizes): w = 0 h = 0 for element in sizes: if element[0] > element[1]: element[0], element[1] = element[1], element[0] if element[0]>w: w = element[0] if element[1]>h: h = elem..
Programmers Lv.1 "시저 암호" 시저암호를 만드는 알고리즘은 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 말하는데 알파벳의 순서를 일정거리만큼 밀어서 대응시키는것이 중점이다. 다만, 맨 마지막 알파벳은 맨 처음 알파벳과 이어지는것을 유의해서 구하면 되는데, 필자는 아스키 코드값을 기억하고 있기에 (A가 65, a가 97이다.) 이 테이블을 이용하여 알고리즘을 구현했다. def solution(s, n): answer = '' for i in list(s): if i != " ": if i.isupper() : answer += chr(ord(i)+n) if ord(i)+n < 91 else chr(ord(i)-26+n) elif i.islower() : answer += chr(ord(i)+n) if ord..
진법 변환 (Base Conversion) 진법이란 무엇일까요? 진법이란 수를 표기하는 기수법의 하나로 몇 개의 기본 숫자를 이용하여 수를 표시하는 방법이다. 자리값이 올라감에 따라 수가 일정하게 커지는 규칙을 이용하고 수를 표시한다. 아라비아 숫자에 해당하는 1~9까지의 숫자를 사용하여 수를 나타내는 방식을 10진법이라고 하고 프로그래밍 영역에서는 2진법, 8진법, 16진법이 존재한다. 모든 진법은 숫자의 위치에 따라 가중치가 달라진다. 아래 그림을 보자. 예를들어 `12345 = (1 \times 10^4)+(2 \times 10^3)+(3 \times 10^2)+(4 \times 10^1)+(5 \times 10^0)`와 같은것이다. 주의깊게 봐야하는 부분은 각 진법간의 변환인데, 차례대로 알아보자. 10진수를 `N`진수로 변환하는 방식을 ..
약수의 개수와 최대공약수, 최소공배수 (Count of Divisor & GCD, LCM) 수론에서 약수(=divisor) 혹은 인수(=factor)는 어떤 수를 나누어떨어지게 하는 수를 말한다. 두 정수 `a,\;b`에 대하여 `b=ac`를 만족하는 정수 `c`가 존재한다면 `a`를 `b`의 약수라고 말하고 `a|b`로 표기한다. 모든 정수는 1과 -1을 약수로 가진다. 또한 모든 정수는 자기자신과 그 반수(더했을 때 0이 되는 수)를 약수로 가진다. 예시를 들면 이렇다. 12의 모든 양의 약수는 1,2,3,4,6,12이다. 약수는 음수일 수 있으며, 12의 모든 음의 약수는 -1, -2, -3, -4, -6, -12이다. 이제는 성질을 알아보자. 약수를 논할때 빠질 수 없는것이 바로 배수와의 관계이고, 가장 빈번하게 등장하는 개념이 최대공약수와 최소공배수일 것이다. 요거까지 정리해보자. 우..

티스토리툴바