아이테킨의 끄적끄적

LCS는 임의의 두 문자열에서 가장 긴 subsequence의 길이를 구하는 문제다. 처음 접해보는 개념이라 2시간정도 혼자서 고민하다가 다른 사람의 정리된 블로그를 보면서 이해하였다. 이미 만들어 놓은 결과위에 새로운 문제들을 이어서 푼다는 DP의 특징을 기억하고 있을 필요가 있다. 위의 표에서 (2,3), (2,6), (3,2), (3,5), (4,3), (4,6), (6,7)은 모두 행과 열의 문자가 같다. 이렇게 행과 열의 문자가 같은 셀의 값은 왼쪽 대각선 위에 있는 수에서 1을 더한 값이 되는 규칙을 찾을 수 있다. 1. 각각의 문자열에서 가장 최근에 추가된 문자가 같을 경우 왼쪽 대각선 위의 셀에서 각각 같은 문자열이 추가되었으므로 +1을 해준다. 예) (3,5)셀 : CAP와 A에서 C가 ..

조합 공식을 이용해서 풀 수 있는 문제였다. 고등학교때 이후로 머리속에서 꺼내보지 않았던 개념이라 인터넷으로 다시 조합공식을 찾아보기도 했다....하핳 펙토리얼(fac)함수를 정의하고 정의한 함수를 이용해서 조합 공식을 만들어서 풀었다. # 1010번 : 다리놓기 # 조합(Combination)공식을 이용해서 쉽게 풀 수 있다. t = int(input()) def fac(n): num = 1 for i in range(1,n+1): num *= i return num for _ in range(t): m,n = map(int,input().split()) bridge = fac(n) // (fac(m)*fac(n-m)) print(bridge)

# 2193번 : 이친수 # 재귀방법으로 피보나치 수열을 만들면 시간복잡도가 크기 때문에 시간초과가 난다. # tablatoin 방법으로 만들면 시간면에서 훨 효율적이다. n = int(input()) table = [0]*91 table[1] = 1 table[2] = 1 for i in range(3,n+1): table[i] = table[i-1] + table[i-2] print(table[n]) n=1 : 1 n=2 : 1 n=3 : 2 n=4 : 3 n=5 : 5 n=6 : 8 ... 처음엔 그냥 숫자들을 적어보다 보니 규칙을 발견할 수 있었다. 피보나치 수열과 같은 규칙이었다. 재귀방법으로 문제를 풀게 되면 시간복잡도가 커지고 시간초과가 난다 tablation방법으로 피보나치 수열을 구현하면..

# 2774번 부녀회장이 될 테야 T = int(input()) for _ in range(T): k = int(input()) n = int(input()) f0 = [x for x in range(1,n+1)] for _ in range(k): for i in range(1,n): f0[i] += f0[i-1] print(f0[-1])

점수가 큰 과제를 뒤에서부터 채워나가는 방법으로 과제를 해결하도록 계획을 세워야 한다. (처음엔 점수가 큰 과제부터 한다거나 마감일이 빠른 과제부터 끝내는 방법을 생각해보았지만 답은 아니었다.) 마감일 | 점수 4 | 60 4 | 40 1 | 20 2 | 50 3 | 30 4 | 10 6 | 5 이렇게 과제와 마감일이 주어져있을 때 가장 점수가 높은 과제부터 마감일부터 뒤로 계획을 세워준다. 60점 과제는 4일째 50점 과제는 2일째 40점 과제는 4일째에 이미 60점짜리를 해야하므로 3일째 30점 과제는 3일째, 2일째 이미 다른 과제가 있으므로 1일째 20점,10점 과제는 남은 기간이 없으므로 패스 5점 과제는 6일째 이런 식으로 이런 알고리즘을 구현하는 데엔 heap 자료구조를 사용하는 것이 유용하..

구글링에서 본 것중 가장 직관적이고 쉬운 풀이를 가져왔다. names = input() name_cnt = [0 for _ in range(26)] for name in names: name_cnt[ord(name)-65] += 1 odd = 0 odd_alpha = '' alpha = '' for i in range(26): if name_cnt[i] % 2 == 1: odd += 1 odd_alpha += chr(i+65) alpha += chr(i+65) * (name_cnt[i] // 2) if odd > 1: print("I'm Sorry Hansoo") else: print(alpha+odd_alpha+alpha[::-1]) # 참고 : https://alpyrithm.tistory.com/1..

우선 입력할 때 input으로 하니 시간초과가 떳다. -> sys라이브러리의 stdin.readline사용. 로직 1. 강의시간을 시작시간으로 정렬. 2. 맨 처음 강의시간의 종료시간과 두번째 강의의 시작시간을 비교 - 시작시간보다 종료시간이 느리면 새로운 강의실 배정 -> room에 heapq.heappush로 추가. - 시작시간보다 종료시간이 빠르면 기존 강의실의 종료시간 수정 -> room에 heapq.heappop 으로 기존 강의실 종료시 간을 제거하고 heapq.heappush로 새로운 종료시간 추가 굳이 heap자료구조를 사용해야 하나 생각을 해보았다. 우선 heap 자료구조가 시간복잡도 측면에서 list보다 효율적이고 heap을 사용하면 최소힙을 계속 유지해주기도 한다. # 11000번: 강..

1. 다 자라는데 가장 오랜 기간이 걸리는 나무를 첫 날 심어줘야 하기 때문에 나무를 내림차순 정렬 2. 심는데 1일, 다 자라고 나서 1일 총 2일 필요 + 심는 날짜 별로 일수 추가 3. 제일 늦게 완성되는 날짜 일수 출력. 예 - [2,3,4,3]의 나무가 있는 경우 1. 나무 [4,3,3,2]로 정렬 2. 각 나무 완성에 필요한 일수 계산 -> [2,3,4,5]를 각각 자리별로 더해줌. 3. 더해진 리스트에서 최대값 출력 # 9237번 : 이장님 초대 n = int(input()) li = list(map(int,input().split())) li.sort(reverse=True) li2 = [i+2 for i in range(n)] ans = [x+y for x,y in zip(li,li2)]..

1. 먼저 '.' 을 기준으로 입력값을 구분할 수 있도록 split함수를 사용하였다. 2. 구분된 리스트의 각 값들의 길이가 홀수이면 -1을 출력할 수 있도록 해준다. 이 때, flag변수를 설정해서 구분하였다. 3. 먼저 'AAAA'를 4로 나눈 몫만큼 곱해주고 나머지에 2로 나눈 몫만큼 'BB'에 곱해준다. 사실 지금 생각해보니 2로 나눈 몫은 항상 1이 될 수 밖에 없다. (결과는 같다.) 참고 print함수를 사용해서 list를 차례대로 출력하려고 할 때 *를 리스트 앞에 붙여주면 띄어쓰지 않고 출력해준다. 이 때 sep, end같은 print내부 옵션도 당연히 사용 가능하다. # 1343번 : 폴리오미노 li = input().split('.') ans = [] flag = 0 for i in ..

가장 높은 레벨이 가장 큰 점수를 얻어야 하는 문제인데 최소한의 횟수를 사용해야 하므로 점수 조정시 다음 레벨과의 점수 차이를 1로 만들어 주면 된다. 문제를 풀 때 주의해야 할 점은 높은 레벨에서부터 비교하면서 점수를 낮춰주어야 한다. 낮은 레벨부터 점수를 낮추게 되면 [5,5,5] > [4,5,5] > [4,4,5] 이런 식으로 점수가 오름차순이 되지 않을 수 있다. 실제로 처음에 이렇게 풀었다가 틀렸었다... # 2847번 : 게임을 만든 동준이 n = int(input()) levels = [] for _ in range(n): levels.append(int(input())) levels.reverse() cnt = 0 for i in range(n-1): while levels[i]