sujin's 개발 로그

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입력 1 2 예제 출력 1 1 예제 입력 2 10 예제 출력 2 3 소스코드 n = int(input()) dp = [0, 0, 1, 1] if n

2021 11월 23일 ~ 12월 4일 코딩 테스트 공부 계획표 마지막 겨울 방학 목표 1일 1커밋 백준 300문제 우테코 문제 기한 맞춰 해결해보기 + 첨삭 주간 일기쓰기 매일 7~8시간 취침 및 8시 이전 기상

11718번 그대로 출력하기 문제 입력 받은 대로 출력하는 프로그램을 작성하시오. 입력 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시작하지 않고, 공백으로 끝나지 않는다. 출력 입력받은 그대로 출력한다. 예제 입력 1 Hello Baekjoon Online Judge 예제 출력 1 Hello Baekjoon Online Judge 문제 해결 아이디어 1. 예외 처리 구문 : try ~ except try: (예외가 발생할수도 있는 코드) except 예외: (예외가 발생했을 경우 실행되는 코드) 2. EOFError 입력이 끝남(End Of File..

소수 판별 알고리즘 소수(Prime Number) -소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수입니다. 6은 1, 2, 3, 6으로 나누어떨어지므로 소수가 아닙니다. 7은 1과 7을 제외하고는 나누어 떨어지지 않으므로 소수입니다. -코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제됩니다. 소수의 판별 기본적인 알고리즘 # 소수 판별 함수(2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 (x - 1)까지의 모든 수를 확인하며 for i in range(2, x): # x가 해당 수로 나누어떨어진다면 if x % i == 0: return False# 소수가 아님 return True# 소수임 ..

서버와 클라이언트 클라이언트가 요청(Request)을 보내면 서버가 응답(Response)합니다. 클라이언트(Client) = 고객 -서버로 요청(Request)을 보내고 응답(Response)이 도착할 때까지 기다립니다. -서버로부터 응답을 받은 뒤에는 서버의 응답을 화면에 출력합니다. 예 1) 웹 브라우저 : 서버로부터 받은 HTML, CSS 코드를 화면에 적절한 형태로 출력합니다. 예 2) 게임 앱 : 서버로부터 받은 경험치, 친구 귓속말 정보 등을 화면에 적절한 형태로 출력합니다. 서버(Server) = 서비스 제공자 -클라이언트로부터 받은 요청(Request)을 처리해 응답(Response)을 전송합니다. 예 ) 웹 서버 : 로그인 요청을 받아 아이디와 비밀번호가 정확한지 검사하고 그 결과를 응..

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

최단 경로 문제 -최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미합니다. -다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 -각 지점은 그래프에서 노드로 표현 -지점 간 연결된 도로는 그래프에서 간선으로 표현 최단 경로 문제를 해결하는데 필요한 개념 우선순위 큐(Priority Queue) -우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조입니다. -예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우에 우선순위 큐를 이용할 수 있습니다. -Python, C++, Java를 포함한 대부분의 프로그래밍 언어에서 표준 라이브러리..

다이나믹 프로그래밍(Dynamic Programming) -다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. -이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. -다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성됩니다. -다이나믹 프로그래밍은 동적 계획법이라고도 부릅니다. -일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까요? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미합니다. 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어입니다. -다이나믹..

이진 탐색(Binary Search) 알고리즘 -순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 -이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로, 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함 이진 탐색의 시간 복잡도 O(logN) : 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 logN에 비례함 이진 탐색 소스코드 (Python) # 1. 재귀적 구현 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid]..

대표적인 데이터 구조 : 해쉬 테이블(Hash Table) 1) 해쉬 구조 Hash Table은 키(Key)에 데이터(Value)를 저장하는 데이터 구조입니다. Key를 통해 바로 데이터를 받아올 수 있으므로 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예 : Key를 가지고 바로 데이터(Value)를 꺼냄 보통, 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용(공간과 탐색 시간을 맞바꾸는 기법). 단, 파이썬에서는 딕셔너리 타입을 사용하면 되므로 해쉬를 별도로 구현할 이유가 없음 2) 알아둘 용어 -해쉬(Hash) : 임의의 값을 고정 길이로 변환하는 것 -해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 -해싱..