dingdong coding

프로그래머스 Level1 전체 풀이 JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고) 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 s는 길이 1 이상 200 이하인 문자열입니다. s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다. 숫자는 단어의 첫 문자로만 나옵니다. 숫자로만 이루어진 단어는 없습니다. 공백문자가 연속해서 나올 수 있습니다. # JadenCase 문자열 만들기 def solution(s): answer = '' arr..

1. 모험가 길드 • 문제 한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. 동빈이는 회대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다. ** 모든 모험가를 특정한 그룹에 넣을 필요는 없습니다. ** • 입력조건 - 첫째 줄에 모험가의 수 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) - 둘째 줄에는 각 모험가의 공포도 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분..

• 서로소 집합 (Disjoint Sets) : 공통 원소가 없는 두 집합을 의미합니다. • 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조입니다. • 서로소 집합 자료구조는 두 종류의 연산을 지원합니다. • 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산입니다. • 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산입니다. • 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 합니다. • 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정은 다음과 같습니다. 1. 합집합(Union) 연산을 확인하며, 서로 연결된 두 노드 A, B를 확인합니다. 1) A와 B의 루트 노드 A'..

• 최단경로 알고리즘 : 가장 짧은 경로를 찾는 알고리즘 • 다양한 문제 상황 • 한 지점에서 다른 한 지점까지의 최단경로 • 한 지점에서 다른 모든 지점까지의 최단경로 • 모든 지점에서 다른 모든 지점까지의 최단경로 • 각 지점은 그래프에서 노드로 표현 • 지점간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 • 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단경로를 계산합니다. • 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작합니다. • 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않습니다. • 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됩니다. • 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복합니다. • 알고리즘의..

• 다이나믹 프로그래밍 : 메모리를 적절히 사용사여 수행 시간을 비약적으로 증가시키는 방법 • 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. • 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성된다. 다이나믹 프로그래밍은 동적 계획법이라고도 부른다. 일반적인 프로그래밍 분야에서 동적(Dynamic)이란 : 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법' 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미없이 사용된 단어 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용이 가능하다. 1. 최적 부분 구조 (Optimal Substructure) : 큰 문..

‣ 순차탐색(Sequential Search) : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서 데이터를 하나씩 확인하는 방법 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1# 현재의 위치 반환(인덱스는 0부터 시작하므오 1더하기) print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") input_data = input().split() n = int(input_data[0]) # 원소의 개수 target = input_data[1] # ..

정렬 알고리즘 ‣ 정렬(Sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것 ‣ 선택정렬(Selection Sort) : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 # 선택정렬 소스코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] #스와프 print(array) 선택 ..

그래프 탐색 알고리즘 DFS/BFS ‣ 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 ‣ 스택 : FILO (First In Last Out) 입구 = 출구 ( Python의 List append, pop ) print(stack [ : : -1]) # 최상단 원소부터 출력 print(stack) # 최하단 원소부터 출력 ‣ 큐 : FIFO (First In First Out) 입구 ≠ 출구 ( Python의 deque 라이브러리 사용 append, popleft ) from collections import deque queue = deque() ### print(queue) # 먼저 들어온 순서대로 출력 queue.reverse() print(queue) # 나중에 들어온 원소부터 출력..

구현 (Implementation) : 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 - 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용 → 열(Column) ↓ 행(Row) 1. 상하좌우 (예제) 2. 시각 (예제) 3, 문자열 재정렬 (예제 Youtube 강의) 4. 왕실의 나이트 (실전문제) 5. 게임개발 (실전문제) [ 예제 ] 상하좌우 ※ 문제 여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에..

그리디 (탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 1. 거스름돈 (예제) 2. 큰 수의 법칙 (실전문제) 3. 숫자 카드 게임 (실전문제) 4. 1이 될 때까지 (실전문제) [ 예제 1 ] 거스름돈 ※ 문제 카운터에는 거스름돈으로 사용할 500원,100원,50원,10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야할 동전의 최소 개수를 구하라. 단 N은 항상 10의 배수이다. # 거스름 돈 n = 1260 count = 0 # 큰 단위의 화폐부터 차례대로 확인하기 array = [500, 100, 50, 10] for coin in array: count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기 // : ..