본문 바로가기

코딩 테스트291

081 순열의 순서 첫번째 코드 이 문제는 순열의 문제이고 손으로 많이 풀어본 문제라고 생각이 들었다.하지만 코드로는 처음 접해봐서 코드는 책을 참고했다. 여기서 중요한 것은 소문제1, 2번 문제를 푸는 방법이다. 책에서는 아래와 같이 설명한다. 소문제11. 주어진 값(k)와 현재 자리(n)-1에서 만들 수 있는 경우의 수를 비교한다.2. 1에서 k가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다.(순열의 순서를 1씩 늘림)3. k가 더 작아지면 순열에 값을 저장하고 k를 k-(경우의 수 * (cnt-1))로 업데이트 한다.4. 순열이 완성될 때까지 1~3을 반복하고 완료된 순열을 출력한다. 소문제21. 현재 자릿수의 숫자를 확인하고 해당 숫자보다 앞 숫자 중 미사용 숫자를 카운트한다.2. 미사용 숫자 개수 * .. 2024. 8. 20.
082 사전 첫번째 코드 이전의 조합 문제와 비슷한 문제지만,조합을 어떻게 꾸려 나가야할지에 대한 고민이 많이 필요할 것 같다. 코드는 책을 참고했고,헷갈렸던 부분은 m+n이 전체 개수임을 계속 까먹는 다는 것!! import sys input = sys.stdin.readline n, m, k = map(int, input().split()) dp = [[0 for _ in range(202)] for i in range(202)] for i in range(201):     for j in range(i+1):         if j == 0 or j == i:             dp[i][j] = 1         else:             dp[i][j] = dp[i-1][j] + dp[i-1][j-.. 2024. 8. 20.
숫자 문자열과 영단어 첫번째 코드 많은 입력이 있는 것을 보고 리스트를 이용하면 편하겠지만, 용량과 연습을 위해서 딕셔너리를 이용하기로 했다. 먼저 숫자와 관련된 것들을 딕셔너리에 저장한다.그리고 해당 key와 비교하여 같은 경우 그 키의 value값으로 바꾸어 문자열을 변경한다.정답은 문자열이 아니므로 int로 바꾸어 답을 낸다. def solution(s):     num = {'zero':0, 'one':1, 'two':2, 'three':3,              'four':4, 'five':5, 'six':6, 'seven':7,             'eight':8, 'nine':9}     for word, num in num.items():         s = s.replace(word, str(num).. 2024. 8. 19.
최소 공통 조상 최소 공통 조상 LCA (Lowest Common Ancestor) 임의의 두 노드를 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드 탐색 시 처음 공통으로 만나게 되는 부모노드 - BFS, DFS 사용- 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올리면서 같은 길이로 맞춤(이때 두 노드가 같으면 탐색 종료)최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때(2**k) 씩 올라가 비교하느 방식 -> (2**k)번쨰 위치의 부모 노드까지 저장해야 함 1. 부모 노드 저장 리스트 만들기정의: P[k][n] = n번 노드의 (2**k)번쨰 부모 노드 번호점화식: P[k][n] = P[k-1]P[[k-1][n]]- n의 (2.. 2024. 8. 18.
세그먼트 트리 세그먼트 트리 주어진 데이터의 구간 합, 데이터 업데이트를 빠르게 하기 위해 고안- 구간 합 구하기- 최대, 최소 구하기과정 - 토리 초기화 하기1. 리프 노드의 개수가 데이터의 개수(n) 이상이 되도록 트리 리스트 만들기(2**k) >= n 을 만족하는 k의 최소값을 구한 후(2**k) * 2 를 트리 리스트의 크기로 정의 2. 리프 노드에 원본 데이터 입력하기리프 노드의 시작 위치를 트리 리스트의 인덱스로 구함((2**k)를 시작 인덱스로 취함) 3. 1 ~ (2**k)-1 구간 채우기 (by. 질의)> 구간 합: A[n] = A[2n] + A[2n+1]> 최대: A[n] = max(A[2n], A[2n+1])> 최소: A[n] = min(A[2n], A[2n+1])의 방식으로 앞 리스트 채우기 - .. 2024. 8. 17.
옹알이 (2) 첫번째 코드 사실 첫번째라기에는 연속해서 발음하는 것이 불가능하다는 것을 보지 않았다...문제를 명확히 보도록 하자! 그리고 수정한 방법으로 아래와 같이 작성하였다. 연속한 경우 발음이 되지 않으므로 해당 문자열을 작성한다.그리고 해당 단어가 있는 경우 'x'로 대체한다. 똑같은 방법으로 발음이 가능한 경우 해당 값을 삭제한다.그 결과 모든 값이 없는 경우 발음이 가능한 경우이므로 count에 1을 더한다. def solution(babbling):     count = 0     can_speak = ['aya', 'ye', 'woo', 'ma']     cant_speak = ['ayaaya', 'yeye', 'woowoo', 'mama']          for i in range(len(babbl.. 2024. 8. 16.
728x90

티스토리툴바