취미와 밥줄사이

공간 복잡도 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현할 수 있다. 시간 복잡도: 얼마나 빠르게 실행되는지 공간 복잡도: 얼마나 많은 저장 공간이 필요하는지 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘이다. 시간과 공간은 반비례적인 경향이 있다. 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함 총 필요 저장 공간 고정 공간(알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수(일정한 양의 메모리 공간) 가변 공간(알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간 입력값의 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 의미 S(P) = c + Sp(n) c: 고정공간 Sp(n)SP(n): 가변 공간 고정 공간은 상수이므로 공간 복잡도는 ..

선형 검색(Linear Search) 순차 검색(Sequential Search)이라고도 한다. 데이터가 모인 집합(배열, lined List)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘 데이터를 정렬할 필요가 없음 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있음 10개의 데이터가 있을 경우 마지막에 있는 데이터를 찾는 경우 10번의 비교가 필요하지만 100만개의 데이터가 있는경우 100만번의 비교가 필요함 선형검색은 linked list에서 자주 쓰임 def linear_search(sequence, key): for i in range(len(sequence)): if sequence[i] == ..

문제 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 개를 칠판에 써주었다. 그 다음에 크기가 큰 수를 말해보라고 했다. 상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734와 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다. 두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 칠판에 적은 두 수 A와 B가 주어진다. 두 수는 같지 않은 세 자리 수이며, 0이 포함되어 있지 않다. 출력 첫째 줄에 상수의 대답을 출력한다. 예..

문제 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다. 입력 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열은 공백으로 시작하거나 끝날 수 있다. 출력 첫째 줄에 단어의 개수를 출력한다. 예제 입력1 The Curious Case of Benjamin Button 예제 출력1 6 예제 입력2 The first character is a blank 예제 출력2 6 풀이 sentences = input().spli..

문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. 예제 입력1 Mississipi 예제 출력1 ? 예제 입력2 zZa 예제 출력2 Z 풀이 words = input().upper() # 입력받은 문자열을 소문자로 변환 unique_words = list(set(words)) # 중복제거 하기 위한 set / to list cn..

문제 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다. S에는 QR Code "alphanumeric" 문자만 들어있다. QR Code "alphanumeric" 문자는 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\$%*+-./: 이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 반복 횟수 R(1 ≤ R ≤ 8), 문자열 S가 공백으로 구분되어 주어진다. S의 길이는 적어도 1이며, 20글자를 넘지 않는다. 출력 각 테스트 케이스에 대해 P를 출력한다. 예제 입력1 2 3 A..

문제 N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. 출력 입력으로 주어진 숫자 N개의 합을 출력한다. 예제 입력1 1 1 예제 출력1 1 예제 입력2 5 54321 예제 출력2 15 풀이 N = int(input()) strNumber = input() sumNumber = 0 for i in list(strNumber): sumNumber = sumNumber + int(i) print(sumNumber) REFEERENCE https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1..

문제 알파벳 소문자, 대문자, 숫자 0-9중 하나가 주어졌을 때, 주어진 글자의 아스키 코드값을 출력하는 프로그램을 작성하시오. 입력 알파벳 소문자, 대문자, 숫자 0-9 중 하나가 첫째 줄에 주어진다. 출력 입력으로 주어진 글자의 아스키 코드 값을 출력한다. 예제 입력1 A 예제 출력1 65 풀이 asc = input() print(ord(asc)) # ord 함수는 문자를 아스키 코드로 # chr 함수는 아스키 코드를 문자로 변환해준다. REFERENCE https://velog.io/@believe9678/%EB%B0%B1%EC%A4%80-11654-%ED%8C%8C%EC%9D%B4%EC%8D%AC 백준 11654 (파이썬) https://www.acmicpc.net/problem/11654ord함..