cedis 님의 블로그

📋 문제 소개문제 설명분할 정복(Divide and Conquer) 방식으로 배열의 최댓값을 찾는다. 배열을 반으로 나누고, 각 부분의 최댓값을 재귀적으로 구한 후 비교한다.INPUT정수 배열 arr, 시작 인덱스 left, 끝 인덱스 rightOUTPUT배열의 최댓값 (정수)예제입력arr = [3, 5, 1, 8, 2, 9, 4]left=0, right=6출력9💡 힌트Base case: left == right일 때 arr[left] 반환. 배열을 반으로 나눠 재귀 호출 후 max()로 비교.① 문제 이해항목내용문제분할 정복으로 배열의 최댓값을 구한다.입력정수 배열 arr, 시작 인덱스 left, 끝 인덱스 right예제[3,5,1,8,2,9,4] → 9② 핵심 아이디어Divide → Conquer..

week 03 start#이분탐색#BinarySearch#탐색#크래프톤정글#베이직#3주차#Python📋 문제 소개문제 설명정렬된 배열에서 특정 값(target)을 찾아 해당 인덱스를 반환한다. 배열을 반으로 나누어 탐색 범위를 절반씩 줄이는 이분 탐색 알고리즘을 직접 구현한다.INPUT정렬된 정수 배열 arr, 찾을 값 targetOUTPUTtarget의 인덱스 (없으면 -1)예제입력arr = [1, 3, 5, 7, 9, 11, 13]target = 7출력3💡 힌트left, right 포인터와 mid = (left+right)//2 사용. arr[mid]와 target 비교해 범위 조정.① 문제 이해항목내용문제정렬된 배열에서 target 값의 인덱스를 반환. 없으면 -1.입력정렬된 정수 배열 arr,..

첫 번째 WIL을 쓴다. 2주가 지났고, 블로그엔 28개의 글이 쌓였다.숫자보다 중요한 건 그 안에서 내가 무엇을 배웠는가이다.📌 이번 주 목표 3가지✅ 목표 1. 주어진 알고리즘 문제를 모두 풀고, 블로그에 게시한다.✅ 목표 2. 파이썬 문법을 의미 있는 코드를 작성할 수 있는 수준까지 익힌다.✅ 목표 3. 내 코드와 풀이 방식을 팀원에게 설명할 수 있는 능력을 기른다.세 가지 모두 달성했다. 다만 "달성"의 의미가 각기 달랐다. 목표 1은 양적 완료였고, 목표 2는 언어 전환의 고통이었으며, 목표 3은 설명하려다 내 이해 부족이 드러나는 경험이었다.📊 핵심 역량별 WIL1️⃣ 문제해결 (Problem Solving)정의: 주어진 문제를 정의하고 논리적으로 해결하는 능력이번 주 제공된 알고리즘 22..

📌 문제 요약알파벳으로 이루어진 단어에서 가장 많이 사용된 알파벳을 대문자로 출력하라.단, 최다 빈도 알파벳이 여러 개이면 ?를 출력한다.💡 핵심 아이디어① 대문자로 통일 (.upper()) ② 딕셔너리로 빈도수 집계 ③ 최댓값 알파벳이 1개인지 확인대소문자 구분 없이 세야 하므로 입력을 먼저 .upper() 처리🐍 코드 분석word = input().upper() # 대문자 통일count = {}for ch in word: count[ch] = count.get(ch, 0) + 1 # 빈도수 집계max_cnt = max(count.values()) # 최대 빈도수# 최대 빈도 알파벳 목록candidates = [k for k, v in count.items()..

📌 문제 요약각 테스트케이스마다 정수 R과 문자열 S가 주어지면, S의 각 문자를 R번씩 반복한 문자열을 출력하라.예: R=3, S="ABC" → "AAABBBCCC"💡 핵심 아이디어문자열을 순회하며 각 문자에 * R 연산으로 반복 → 이어붙이기Python에서 문자열 * n 은 해당 문자열을 n번 반복한 새 문자열을 반환🐍 코드 분석T = int(input())for _ in range(T): R, S = input().split() R = int(R) result = "" for c in S: # 각 문자 순회 result += c * R # R번 반복해서 이어붙이기 print(result)⚠️ 자주 하는 실수실수설명S * R 전체 반복..

📌 문제 요약각 케이스마다 학생 수와 점수들이 주어질 때, 평균을 초과하는 학생의 비율을 소수점 3자리로 출력하라.평균 초과 (strictly greater) 이므로 평균과 같은 점수는 포함하지 않음💡 핵심 아이디어① 합계 → 평균 계산 ② 평균 초과 학생 카운트 ③ 비율(%) 출력출력 형식: "%.3f%%" — %% 는 % 문자 자체를 출력하는 이스케이프🐍 코드 분석num = int(input())for _ in range(num): a = list(map(int, input().split())) cnt = a[0] # 첫 번째 값: 학생 수 scores = a[1:] # 나머지: 점수 목록 avg = sum(scores) / cnt ..

📌 문제 요약정수 N이 주어지면, 재귀함수를 N번 중첩하여 정해진 형식의 문장을 출력하라.깊이(depth)마다 ____(언더바 4개)를 depth번 앞에 붙인다.🔁 재귀 구조 이해recursion(depth)├─ depth == N 이면 → 베이스 케이스 (재귀 종료)│ "재귀함수는 자기 자신을 호출하는 함수라네" 출력└─ 아니면 → 이야기 3줄 출력 후 recursion(depth+1) 호출 호출 후 "라고 답변하였지." 출력핵심: recursion(depth+1) 호출 이후에도 코드가 실행됨 → 재귀 반환 시 출력 발생🐍 코드 분석n = int(input())print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")def recursion(depth): c = "..

📌 문제 요약N개의 자연수 중 소수가 몇 개인지 출력하라.소수: 1과 자기 자신만을 약수로 가지는 수 (단, 1은 소수 아님)💡 소수 판별 원리약수의 개수가 정확히 1개이면 소수.1부터 n-1까지 반복하면 약수 중 1만 세이므로, 약수 카운트 == 1 이면 소수.더 빠른 방법: 2부터 √n까지만 나눠보기 → 이 문제는 입력이 작아서 완전탐색도 OK🐍 코드 분석n = int(input())a = list(map(int, input().split()))count = 0for num in a: divisors = 0 for d in range(1, num): # 1 ~ num-1 탐색 if num % d == 0: divisors += 1 if d..

📌 문제 요약9개의 서로 다른 자연수가 주어질 때, 최댓값과 그 위치(1-index)를 출력하라.입력: 9줄, 각각 자연수 한 개 | 출력: 최댓값 / 위치(1-index)💡 핵심 아이디어리스트에 9개 값을 저장한 뒤, 순회하면서 현재 최댓값보다 크면 갱신 + 인덱스 기록.⚠️ 인덱스는 0-based 이므로 출력 시 +1 필요🐍 코드 분석a = []for i in range(9): a.append(int(input()))max_val = a[0] # 첫 번째 값으로 초기화max_idx = 0for j in range(9): if a[j] > max_val: # 더 큰 값 발견 max_val = a[j] max_idx = jprint(max_val)pri..

01 하노이 탑 📌 02 외판원 순회실버 2 · DFS 백트래킹[백준 10971] 외판원 순회 2완전탐색 + 가지치기cedis · 2026.03 | Python · DFS · 백트래킹 · 완전탐색도시들을 한 번씩 방문하고 출발지로 돌아오는 최소 비용 경로를 찾는 문제다. 이름은 거창하지만 핵심은 단순하다. 모든 경우를 탐색하되, 쓸모없는 경로는 일찍 잘라낸다. 그게 바로 백트래킹 + 가지치기다.🔗 문제 링크: 백준 10971번 - 외판원 순회 2N개의 도시를 모두 방문하고 시작 도시로 돌아오는 최소 비용을 구하라.W[i][j]: i→j 비용 (0이면 연결 안 됨). N ≤ 10① 문제 이해: 그래프로 보기N=4, 도시가 0~3번이라 하자. 인접행렬로 비용이 주어진다.W0123001015201509..