잡식성 개발자

백트래킹(Backtracking)은 해를 찾는 도중에 가능성이 없는 부분을 차단하여 불필요한 탐색을 줄이는 알고리즘입니다. 파이썬에서는 다음과 같이 백트래킹 알고리즘을 구현할 수 있습니다. 예제: N-Queen 문제 N x N 크기의 체스판 위에 N개의 퀸을 놓는 문제입니다. 퀸은 가로, 세로, 대각선 방향으로 모두 공격할 수 있으므로, 서로 공격할 수 없도록 N개의 퀸을 놓는 문제입니다. 백트래킹 알고리즘을 사용하여 퀸을 놓을 수 있는 모든 경우의 수를 구합니다. def is_available(candidate, current_col): current_row = len(candidate) for queen_row in range(current_row): if candidate[queen_row] == ..

분할정복(Divide and Conquer) 알고리즘은 큰 문제를 작은 문제로 분할한 후, 각 작은 문제를 해결하고, 이를 합쳐서 큰 문제를 해결하는 알고리즘입니다. 파이썬에서는 다음과 같이 분할정복 알고리즘을 구현할 수 있습니다. 예제: 이진 탐색 주어진 정렬된 리스트에서 특정한 값의 위치를 찾는 문제입니다. 이진 탐색은 리스트의 중간 위치의 값을 검사하여 찾고자 하는 값이 리스트의 중간 위치보다 큰지 작은지를 비교하여 검색 범위를 절반으로 줄여가면서 값을 찾아갑니다. def binary_search(lst, x): start = 0 end = len(lst) - 1 while start x: end = mid - 1 else: start = mid + 1 return -1 # 정렬된 리스트에서 5의 ..

팰린드롬(회문)이란 앞뒤가 똑같은 문장으로 , 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬(Palindrome)이라고 한다. 우리말로는 '회문'이라 부르며, 문장 중에서는 대표적으로 '소주 만 병만 주소'를 예로 들 수 있다. 기본적인 palindrome 유형의 문제는 어떻게 해결하는지 다음의 예제를 통해 알아보자. 주어진 문자열이 팰린드롬인지 확인하여 맞다면 True, 아니라면 False를 출력하라. 단 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다. // 입력 1 : "A man, a plan, a canal: Panama" // 입력 2 : "race a car" 풀이 1 : 리스트로 변환 여기서는 직접 문자열을 입력받아 팰린드롬 여부를 판별해 본다..