본문 바로가기

분류 전체보기

컴린이 일기장/Today I Learned 2022. 4. 15. [TIL] 프로그래머스 - 입국심사 / 코테에 활용할 수 있는 Pythonic한 코드 조각 / 당분간 계획 [Today I Learned] # 프로그래머스 - 입국심사 문제 설명 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록..
컴린이 일기장/Today I Learned 2022. 4. 14. [TIL] 이진 탐색 알고리즘 (feat. 백준- 나무 자르기) / 파라메트릭 서치 / bisect [Today I Learned] # 이진 탐색 알고리즘 (이분 탐색) - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 시작점, 끝점, 중간점(소수점 이하 제거)을 이용해 탐색 범위 명시 + 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법- 연산 횟수는 log2N에 비례, 시간 복잡도는 O(logN) 보장 # 재귀적 구현 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 if array[mid] == target: return mid elif array[mid] > target: return b..
컴린이 일기장/Today I Learned 2022. 4. 11. [TIL] 파이썬 sort()와 sorted() 차이 / 프로그래머스 - K번째수, 가장 큰 수 [Today I Learned] 프로그래머스 고득점 Kit 정렬 문제가 레벨도 낮고 3문제 밖에 안되길래, 쭉 풀어봤다. 그에 앞서 파이썬 sort()와 sorted() 차이를 잘 모르겠어서, 간단히 공부했다. # sort() / sorted() - sorted()는 새롭게 정렬된 리스트를 return, 원래 리스트에는 영향을 주지 않음 -하지만 sort()는 리턴이 따로 없고 입력을 출력으로 덮어씀 - sorted()는 문자열에도 사용가능한것과 달리 sort()는 리스트에만 사용할 수 있음 - 어떤 기준으로 정렬할 것인지 아래와 같이 key 옵션을 지정할 수 있다 # 데이터의 길이를 기준으로 정렬 sorted(data, key=len) # 프로그래머스 - K번째수 문제 설명 배열 array의 i번째 숫..
컴린이 일기장/Today I Learned 2022. 4. 8. [TIL] 프로그래머스 - 타겟 넘버 (bfs/dfs) / 정렬 알고리즘 (1) - 이론 [Today I Learned] # 프로그래머스 - 타겟 넘버 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 ..
컴린이 일기장/Today I Learned 2022. 4. 6. [TIL] DFS & BFS (feat. 스택, 큐 , 재귀 함수) - (2) 적용 [Today I Learned] # 이코테 - 음료수 얼려 먹기 문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다 입력 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1
컴린이 일기장/Today I Learned 2022. 4. 6. [TIL] DFS & BFS (feat. 스택, 큐 , 재귀 함수) - (1) 이론 [Today I Learned] # 스택 - 선입후출 자료구조 - Python에서는 List로 구현 stack = [ ] stack.append(5) # [5] stack.append(2) # [5,2] stack.pop() # [5] stack.append(1) # [5,1] stack.append(4) # [5,1,4] print(stack[::-1]) # 최상단 원소부터 출력 ; [4,1,5] print(stack) # 최하단 원소부터 출력 ; [5,1,4] # 큐 - 선입선출 자료구조 - Python에서는 Collections.deque(덱)으로 구현 - List로도 구현할 수 있지만 시간 복잡도 이슈. (특정 인덱스의 원소 꺼내는 pop 연산 후에, 전체적으로 인덱스 재조정하는 과정 필요.) f..
컴린이 일기장/Today I Learned 2022. 4. 4. [TIL] 구현(Implementation) - 시뮬레이션, 완전 탐색 / 이코테 - 상하좌우, 시각, 왕실의 나이트, 문자열 재정렬 [Today I Learned] # 구현 - 풀이를 떠올리는 건 쉽지만 소스코드로 옮기기 어려운 문제들 - 2차원 공간 → 행렬(Matrix) 많이 등장 (파이썬은 2차원 리스트) - 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용됨 # 이코테 - 상하좌우 여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다.가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다.여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가이동할 계획이 적힌 계획서가 놓여 있다 계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D ..
컴린이 일기장/Today I Learned 2022. 3. 26. [TIL] 그리디 알고리즘(탐욕법) / 프로그래머스 - 체육복 [Today I Learned] # 그리디 알고리즘 (탐욕법) - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 - 일반적인 상황에서는 최적의 해를 보장할 수 없을 때가 많음 - 다만 코딩 테스트에서의 그리디 문제는 대부분 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨 ex. 거스름돈 문제 # 프로그래머스 - 체육복 https://programmers.co.kr/learn/courses/30/lessons/42862 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순..

티스토리툴바