B_log

두 수의 합 - 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라 - 입력 => nums = [2, 7, 11, 15], target = 9 - 출력 => [0,1] 풀이 1 : 브루트 포스(Brute Force) - 모든 경우를 전부 탐색한다. 1 2 3 4 5 def solution(nums:list, target:int) -> list: for i in range(len(nums)-1): for j in range(i+1,len(nums)): if nums[i] + nums[j] == target: return [i, j] cs - O(N^2)의 속도 풀이 2 : in 연산 사용 - in을 이용한 탐색 1 2 3 4 5 6 def solution(nums:list, target:int..

가장 긴 팰린드롬 부분 문자열 - 입력을 넣었을 때 가장 긴 팰린드롬 부분 문자열을 출력하라 ex) "babad" => "bab" "cbbd" => "bb" 문제 상황 - LCS의 경우 dp로 해결할 수 있으나 이 문제의 경우 dp를 사용하면 오히려 속도가 느리게 나온다. 그래서 투 포인터 방식을 사용해야 한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 def longestPalindrome(s:str) -> str: def expand(left:int, right:int) -> str: while left>=0 and right

defaultdict 객체 - defaultdict 객체는 존재하지 않는 키를 조회할 경우, 에러 메세지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성해준다. 결과는 collections.defaultdict 클래스를 갖는다. 1 2 3 4 5 6 7 8 from collections import defaultdict a = defaultdict(int) a['A'] = 5 a['C'] += 1 b = defaultdict(str) b['A'] = 5 b['C'] += "a" print(dict(b)) cs Counter 객체 - Counter 객체는 아이템에 대한 개수를 계산해 dict로 리턴한다. 1 2 3 4 5 6 from collections import Count..

점근적 실행 시간(Asymptotic Running Time) - 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 함수의 실행 시간의 추이를 의미한다. 시간복잡도(Time Complexity) - 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity) 빅오 별 특징 - O(1) : 1초가 걸린다는 것이 아니라 입력값이 아무리 커도 실행 시간이 일정하다는 뜻이다. 상수 시간이라는 것이 빠르다고 생각이 들 수 있지만 일정하다는 것이 포인트이므로 이 상수값 자체가 엄청나게 크다면 사실상 일정한 시간의 의미가 없다. 해시테이블의 조회 및 삽입이 이에 해당한다. - O(logN) : 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 ..

문제 app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/ Brackets coding task - Learn to Code - Codility Determine whether a given string of parentheses (multiple types) is properly nested. app.codility.com 문제 상황 - 전형적인 Stack 문제로 올바른 괄호 찾기 문제이다. 해결 전략 - 검색 속도가 빠른 dict를 이용해 짝을 구성하여 open bracket일 경우 stack에 저장, close bracket의 경우는 open bracket에서 pop하여 비교해서 같으면 제거, 다르면 잘못된 bracket이므로 ret..

인덴트 - PEP 8 이후로 추천하는 방식은 tab이나 2칸 space가 아닌 4칸 space이다. - parameter가 첫째줄에 시작하고, 다음줄로 내려갈 경우 아래와 같이 parameter 시작 위치 선을 맞춰준다. 1 2 foo = long_function_name(var_one, var_two, var_three, var_four) cs - parameter가 첫째줄에 시작하지 않을 때, 줄바꿈이 발생하면 indent로 구별해준다. 1 2 3 4 5 6 7 8 9 def function_name( param_1, param_2, param_3): print(1) foo = long_function_name( param1, param2 param3, param4) cs Naming Conventi..

프로그래밍 언어의 특징 제네릭 프로그래밍 - generic이란 파라미터의 타입이 나중에 지정되게 해서 재활용성을 높일 수 있는 프로그래밍 스타일 ex) Java(1.5ver. 이후), C++(템플릿 기능 활용) 동적 타이핑(Dynamic Typing) - 정적 타이핑과 달리 자료형을 컴파일이 아닌 런타임 시 결정하는 것으로, 자료형의 명시 없이 변수명만 가지고 선언 및 값을 전달하는 것이 가능하다. - 런타임 당시에 타입에 대한 결정을 진행하므로 프로그래밍 하는 입장에서 편할 수 있지만, 한 편으로는 런타임 동안 예상치 못한 에러가 발생할 수 있고 이를 발견하는데 큰 어려움을 겪을 수 있다. ex) Python, Ruby, Javascript 정적 타이핑(Static Typing) - 자료형(type)을..

문제 app.codility.com/programmers/lessons/6-sorting/triangle/ Triangle coding task - Learn to Code - Codility Determine whether a triangle can be built from a given set of edges. app.codility.com 문제 상황 - 주어진 배열을 삼각형 한 변 길이의 집합이라고 할 때 세 변으로 한개의 삼각형을 만들 수 있는 경우가 존재하면 1을 반환, 없으면 0을 반환한다. 해결 전략 코드 1 2 3 4 5 6 7 def solution(A): if len(A) A[i+2] : return 1 return 0 Colored by Color Scripter cs 해설 - 헷갈렸..