쑤야의 개발 블로그

파이썬으로 알고리즘을 풀기 위해 필요한 개념들을 정리합니다. 문자열 문자열의 대/소문자화. .upper() # 대문자 .lower() # 소문자 특정 문자를 기준으로 문자열 분리 .split(문자) 문자열의 리스트화 list(문자열) 리스트화된 문자열 다시 문자열로 변환하기 ''.join(문자열 배열) 알파벳으로만 구성되어있는지 확인 문자열.isalpha() 배열 원소 추가 배열.append(원소) 마지막 원소 삭제 배열.pop() del 배열[-1] 첫 번째 원소 삭제 삭제한 원소 = 배열.pop(0) #삭제한 원소를 반환한다. 조건을 충족하는 첫 번째 인덱스 찾기 arr.index(원소 값) 정렬 배열.sort() # 오름차순 배열.sort(reversed=True) # 내림차순 원소의 길이로 정렬 ..

Algorithm 2024. 2. 1. 12:26

https://school.programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 citations 데이터로 점검할 경우, citations에 속하지 않는 인용 횟수에 대해 점검할 수 없다. 주어진 범위 내에서 조건을 만족하는 최대 값을 찾는 것이 목표이므로, 이진 탐색을 사용할 수 있다. 로직 논문 인용 횟수의 최솟값인 0과 최댓값인 10000을 경계로 하여 이진 탐색을 수행한다. 조건을 만족하는 경우 max를 사용해서 갱신한다. 조건을 만족하는 경우 left 값을 mi..

Algorithm 2023. 12. 18. 13:04

접근 설명처럼 2차 배열 → 슬라이싱 및 1차 배열 변환으로 접근했다가는 시간초과가 발생한다. 인덱스 값을 활용하여 left부터 right 인덱스만 접근한다. 로직 인덱스를 n으로 나눴을 때의 몫과 나머지 중 큰 값에 1을 더한 값이 원소값이 된다. (직접 작성해보면 쉽게 찾을 수 있다) result 배열에 left부터 right 인덱스에 해당하는 값을 넣어준다. 코드 def solution(n, left, right): result = [] for i in range(left, right+1): result.append(max(i//n, i%n)+1) return result

Algorithm 2023. 12. 15. 15:21

접근 괄호 문제에서 올바른 괄호인지 판단하려면 스택 활용 문자열 회전이 필요하므로 이중 반복문 활용 로직 i는 시작점을 나타내는 인덱스, j는 현재 점검하고 있는 원소 인덱스 스택의 마지막 원소와 현재 원소를 합친 문자열이 (), [], {} 에 해당하는 올바른 괄호인지 확인 반복문이 종료된 후 스택이 비어있다면 올바른 괄호로 result 값 1 증가, 비어있지 않으면 올바르지 않은 괄호 코드 def solution(s): s = list(s) bracket = ["()","[]","{}"] result = 0 for i in range(0, len(s)): stack = [s[i]] j = 0 if i+1 == len(s) else i+1 while j != i: if len(stack) != 0 an..

Algorithm 2023. 12. 15. 14:38

접근 처음에 시간초과가 날 로직밖에 생각이 안났다. 문자열을 한 바퀴만 돌린다고 해도 100M이다. O(N log N)일 경우, 딱 마지노선이라 생각했기 때문에 무조건 O(N)으로 끝내야겠다고 생각했다. 문자열에서 조건이 맞으면 문자들을 제거해야 하기 때문에 빠르게 배열의 중간 원소를 제거할 수 있는 알고리즘과 자료구조가 무엇인지를 생각했다. 배열의 원소를 빠르게 제거해야 하는 경우 → 스택 활용 로직 문자열의 원소에 대해 반복문을 돌린다. 각 문자들을 스택에 저장한다. 스택의 마지막 문자와 현재 문자가 동일할 경우, 스택의 마지막 문자를 제거한다 → O(1) 반복문이 종료된 이후, 스택에 문자가 남아있는 경우 성공적으로 수행하지 못한 것. 반대로 빈 스택일 경우 성공적으로 수행할 수 있음을 의미한다. ..

Algorithm 2023. 12. 12. 14:56