분류 전체보기 (68) 썸네일형 리스트형 [백준 12904] A와 B python 문제 문자열 S, T가 주어질 때 2가지 규칙에 의해 S를 T로 변경할 수 있는지 출력하는 문제이다. 풀이 기본 아이디어 S의 길이 마지막 문자열이 A라면 A를 제거한다. 문자열을 뒤집고 뒤에 B를 추가한다. -> 마지막 문자열이 B라면 B를 제거하고, 문자열을 뒤집는다. 파이썬 구현 문자열을 뒤집고, 마지막 문자열을 제거하는 동작을 해야하므로 리스트 이용 통과된 풀이 s = list(input()) # 문자열 S t = list(input()) # 문자열 t success = False while len(s) != len(t): if t[-1] == 'A': # 규칙 1 t.pop() elif t[-1] == 'B': # 규칙 2 t.pop() t = t[::-1] if s == t: # 성공 여부 체.. [Algorithm] 재귀 Recursion 재귀 recursion 재귀 알고리즘의 기본 재귀란 ? 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀를 사용하면 프로그램을 간결하고 효율성 좋게 작성할 수 있음 재귀 호출 recursive call '자기 자신과 똑같은 함수'를 호출한다. ex - 팩토리얼 구하기 factorial() 함수는 n - 1의 팩토리얼 값을 구하기 위해 다시 자기 자신과 똑같은 factorial() 함수를 호출한다. def factorial(n: int) -> int: """양의 정수 n의 팩토리얼을 구하는 과정""" if n > 0: return n * factorial(n - 1) else: return 1 if __name__ == '__main__': n = int(input('출.. [kaggle] Kaggle API 사용하기 mac 1. 아나콘다에 Kaggle 패키지 설치 conda install -c conda-forge kaggle conda install kaggle 2. Kaggle 사용자 토큰 받기 Account에 가서 create API Toke을 클릭하면 kaggle.json파일이 다운로드 된다. 3. kaggle.json mkdir -p ~/.kaggle mv kaggle.json ~/.kaggle/kaggle.json .kaggle이라는 폴더를 생성해준 후 다운받은 json 파일을 이동시킨다. 4. 동작 확인 kaggle competitions list 캐글에서 현재 진행되고 있는 경진대회 목록을 보여준다. 5. 원하는 데이터 다운받기 먼저 다운받을 수 있는 데이터 리스트를 확인한다. kaggle datasets l.. [백준 9020] 골드바흐의 추측 python 문제 문제 요약 : 모든 짝수를 두 소수의 합으로 나눌 수 있다는 골드바흐의 추측에 맞게 주어진 짝수 n에 대하여 골드바흐 파티션을 출력하는 문제이다. 풀이 기본 아이디어 : n을 반으로 나눈 다음 n에서 반으로 나눈 수와 가까운 소수를 뺐을 때 나머지가가 소수이면 골드바흐 파티션이 된 것 ! 소수인지 판별 에레토스테스테네스의 체 사용 ( 백준 1929 번 ) 루프 사용 반복 변수 : tmp , n//2 부터 시작 반복 변수 갱신 : 0이 되기 전 까지 -1 종료 조건 : n- tmp 했을 때 소수가 나온다. 반(n // 2) 만 체크하는 이유 가장 차이가 적은 파티션을 찾아야 하니까. 0부터 (n // 2)까지 반만 체크해도 n-tmp가 소수인지 체크하기 때문에 결국 0부터 n까지 전체가 다 체크되니까.. [Algorithm] 탐색 Searching 탐색 범위를 반씩 좁혀가는 탐색 순차 탐색 Sequential Search : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음. 순차 탐색 소스코드 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기) print("생성할 원소 개.. [Algorithm] 정렬 Sorting 정렬 sorting : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색 Binary Search가 가능해진다. 정렬은 이진탐색의 전처리 과정이기도 하다. '알고리즘의 효율성' 측면에서 정렬은 중요하다. 선택 정렬 selection sort : 매번 '가장 작은 것을 선택'한다. 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하여 정렬이 완료되는 것을 알 수 있다. 스와프(Swap): 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업. 파이.. [Algorithm] 복잡도 Complexity 복잡도 복잡도는 알고리즘의 성능을 나타내는 척도이다. 동일한 기능을 수행하는 알고리즘이 있다면 복잡도가 낮을수록 좋은 알고리즘이다. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 중요하다. 따라서 최악의 경우의 시간 복잡도를 우선적으로 고려해야한다. Cf) Memorization 메모이제이션 : 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법 시간 복잡도와 공간 복잡도의 Trade-off 메모리를 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가.. [Algorithm] 알고리즘 설계와 분석의 기초 알고리즘 설계와 분석의 기초 알고리즘이란 문제를 해결하기 위한 단계적 절차를 말한다. 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 점근적 분석 점근적 분석이란 입력이 충분히 큰 경우에 대한 분석을 말한다. 컴퓨터는 빠른 처리 능력을 가지므로 입력의 크기가 작을땐 속도의 차이가 뚜렷하지 않다. 하지만, 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다. 좋은 알고리즘 = 성능이 좋은 = 효율적인 = 같은 시간에서 더 빠른 알고리즘이다. 알고리즘 표현법 순서도를 이용한 표현 여러 종류의 상자와 상자를 이어 주는 화살표를 이용해서 명령 순서를 표현 간단한 알고리즘은 쉽게 표현할 수 있지만, 복잡한 알고리즘은 표현하기 어려운 경우가 많.. 이전 1 2 3 4 5 6 7 8 9 다음
