B_log

문제 문제 상황 - 최대로 2명이 탑승 가능한 보트에 사람을 태워 최소 횟수로 움직이는 경우를 계산한다. 해결 전략 - 역순으로 정렬하여 사람들을 태우는 데 몸무게가 큰 사람과 가장 몸무게가 적은 사람을 묶어 태운다. 이 때 보트의 탑승 가능 몸무게를 초과하지 않게 한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 def solutio..

문제 문제 상황 - 최소합 문제와 비슷하지만 다르다. 최소합 문제의 경우 dfs와 pruning을 이용하여 전역변수를 조정하는 방향으로 더해나갔다. 이 경우는 모든 열 번호가 겹치면 안되는 것이었다. 하지만 현재 문제는 자기 자신의 위치와 바로 위만 보면 된다. 즉, 자기 자신이 속한 줄과 그 바로 윗줄만 보면 되는 문제이므로 2줄 위의 줄은 영향을 못미친다. 해결 전략 - 범위가 최대 100,000 이므로 O(N^2)만 되도 100억이 된다. log100000 이 약 16.6 이므로 O(NlogN) 혹은 O(N*M) 안에 해결해야 할 것 같다.(이 경우 M이 4로 고정되있으므로 O(N)의 개념이다.) - 특정 row를 기준으로 특정한 col이 있을 때 바로 윗줄에서 그 col값을 제외한 값 중 가장 큰..

문제 문제 상황 - 주어진 전체 사각형에서 가장 큰 정사각형을 찾는다. 해결 전략 - 단순 검색을 통해 구현하면 속도가 O(N^3)로 매우 느리다. 한 변의 길이가 최대 1000이므로 1,000,000,000의 속도는 시간을 초과할 수 밖에 없다. - 속도 이슈를 해결하기 위해 dp를 사용한다. 기존에 루트 탐색같이 사방을 확인해서 더하는 구조는 사각형이란 특성을 계산할 수 없다. 그래서 단위 사각형을 2x2로 만들어 확인한다. - 2x2사각형의 2행 2열을 기준점으로 잡아 우선 위와 왼쪽 요소를 보고 작은 숫자를 선택한다. 그리고 1행 1열과 그 결과를 비교하여 더 작은 값을 계산하고 1을 더해 2x2에 저장한다. 여기서 더하는 1은 2x2에 존재하는 1을 의미한다. 코드 1 2 3 4 5 6 7 8 ..

문제 문제 상황 - 가장 작은 요소들을 꺼내 변화를 주면서 다시 넣는 구조이다. - 가장 작은 요소를 꺼내기 위해 계속 정렬하는 것이 아니라 넣을 때부터 순서를 맞춰 넣어주는 작업을 해야한다. - 일반적인 리스트를 활용해 while 구문 안에서 sort할 경우 O((N^2)logN)이 되므로 너무 느린 속도가 된다. 해결 전략 - heap 자료 구조를 활용해 크기를 정렬하며 문제를 해결한다. - 파이썬의 경우 내장함수로 heap 자료구조를 가지고 있어 활용하기 쉬웠다. - heap 정렬의 경우 O(NlogN)의 속도로 정렬된다. 하지만 while안에서 계속 sort하는 경우와 달리 한번만 해주면 계속 가장 작은 경우들만 뽑기 때문에 전체 속도는 O(N)에 가깝게 나온다. 코드 1 2 3 4 5 6 7 8..

문제 문제 상황 - 알파벳 문자열을 검색하며 연속 2개인 것을 제거해주고 모두 제거가 되면 1, 아니면 0을 반환한다. 해결 전략 - 스택을 활용해 제거가 되는지 확인한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 def solution(s): # s를 전체 순회하며 stack에 저장하며 제거 stack = [] for i in range(len(s)): # 스택에 요소가 존재할 때 if stack: if s[i] == stack[-1]: stack.pop() else : stack.append(s[i]) else : stack.append(s[i]) return 0 if stack else 1 cs 해설 - 쉬운 문제 새로 학습한 것 & 실수 - . 출처 - https://progra..

문제 문제 상황 - 주어진 그림에서 특정 시점에 같은 블록이 2x2로 존재하면 그 요소를 삭제하고 동시에 그 위에 있던 요소를 아래로 밀어 과정을 반복한다. 지워지는 블록이 모두 몇 개인지 판단한다.- 해결 전략 - 우선 리스트를 좀 더 편하게 사용하기 위해 주어진 배열을 90도 회전시켜 아래로 빈칸을 채우는 것이 아니라 왼쪽으로 채우는 구조로 바꾼다. - 배열을 회전시키는 함수, 정해진 조건 하에서 사방을 확인하는 함수, solution 함수 세개로 분할해 문제를 해결하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45..

문제 - https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브�� programmers.co.kr 문제 상황 - 1. 대소문자의 차이는 무시한다. 2. 입력으로 들어온 2글자 이상, 1000글자 이하의 문자는 2글자씩 끊어서 다중 집합으로 만든다. 3. 공백, 숫자, 특수문자 등은 처리하지 않고 무시하고 넘어간다. 4. 중복이 허용되기 때문에 파이썬의 set 자료형을 쓸 수 없다. 해결 전략 - 자카드 유사도를 구하는 함수와..

😅 문제 🤔 문제 상황 - 주어진 리스트를 보면 리스트 내부의 순서가 뒤죽박죽이고 순서가 중요하므로 단순히 정렬해서는 의미가 없다. - 주어진 리스트가 하나의 긴 string이고 부호가 {} 로 되어있으므로 리스트화 하기가 까다롭다. - split의 조건으로 '},{'를 사용하였다. 🧐 해결 전략 - 리스트를 정수화해서 담아준 뒤, 2차원으로 탐색하며 결과 요소에 없다면 새로 담는 식으로 풀이하였다. 🎰 코드 1 2 3 4 5 6 7 8 9 10 11 def solution(s): a = s[2:-2].split('},{') for i in range(len(a)): a[i] = list(map(int, a[i].split(','))) a.sort(key = len) result = [] for i in..