CS/자료구조&알고리즘10 [백준] 2373번 세 용액 들어가며두 용액을 이분탐색으로 풀어서 이 문제도 이분탐색으로 풀어야하나? 라는 생각이 당연하게 들었다. 근데 보통 left, right로 나눠서 3개의 포인터(?)를 가지고 답을 구해나가야하는데 이건 세가지인데? 이런 혼란이 생겼다. 그래서 아 그럼 2개씩 뽑아서 구한 조합의 합을 먼저 구하고 원본 배열 (nC2 + n) 합쳐서 이분탐색을 돌리면 3개의 합이 나오지 않을까? 라고 생각했다. 근데 3개의 원소를 어떻게 기록하지...이처럼 생각이 많았던 문제이다. 브루트포스, 조합을 거쳐갔지만 결국 이분탐색으로 풀었다. 문제 풀이우선 이분탐색이지만 주의할 점은 3개의 용액의 합을 비교해서 풀어야한다는 것이다. 그래서 2중으로 반복문이 돌아가겠지만 이분 탐색이므로 O(nlgn)이 될것으로 예상된다.1. 먼저.. 2024. 5. 7. TreeSet을 써보자 보호되어 있는 글 입니다. 2024. 4. 26. [백준] 9252번: LCS2 https://www.acmicpc.net/problem/9252 9252번: LCS 2LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.www.acmicpc.net 들어가며LCS 문제를 DP로 풀어야한다는 것은 알고 있었지만 길이가 아닌 LCS 문자열을 구하는 과정에서 어려움이 있었습니다. 우선 LCS가 뭔지 간단하게 보고 예제의 결과가 어떻게 나왔는지 과정을 보고 문제 풀이 방식에 대해 설명하겠습니다! LCS(Longest Common Subsequence)란?최장 공통 부분 수열이라는 의미로, 주어진 여러 .. 2024. 4. 26. [프로그래머스]모음 사전 (level 2, 완전 탐색) from itertools import product def solution(word): answer = 0 word_list = generate_words() word_list.sort() # 사전순 정렬 for i, w in enumerate(word_list): if w == word : answer = i + 1 return answer def generate_words(): char_list = ['A', 'E', 'I', 'O', 'U'] words = [] for length in range(1, 6): # 1부터 5까지 길이의 문자를 만들 것임 for p in product(char_list, repeat=length): # repeat: 반복 횟수 -> 길이가 length인 조합을 생성함.. 2024. 3. 11. 이전 1 2 3 다음
