체유의 IT일지

일자: 2024년 08월 29-30일알고리즘: 탐욕법  문제 설명어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.제한 조건number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.k는 1 이상 number의 자릿수 미만인 자연수입니다. 접근 방법가장 큰..

아직 이해 ❌일자: 2024년 08월 28,30일알고리즘: 탐욕법   문제 설명조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서) 예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다. - 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자..

시작 전 programmers에서는 SQL 문제만 거의 다 풀어봤고, 코데는 백준으로만 준비해봤다백준은 뭔가 정이 안 가는 느낌..(?) 이라서이번엔 programmers로 코딩테스트 공부를 해보려 한다 !!약 1년 만에...? 코딩 테스트 준비..ㅎㅎㅎ  SQL만 풀면 문제 풀이가 부족하다고 리포트를 안보여주는 구나...암튼 ! 본격적인 코딩 테스트 준비 전 순위는 118,125위이고하반기 목표: 5,000위 내로 진입 (사실 어느정도인지 가늠이 안돼서.. 일단 목표는 높게 !!)  일자: 2024년 08월 27일알고리즘: 탐욕법 기초 문제## 대소문자 바꾸기.swapcase()   알고리즘 고득점 Kit그리디 - 1. 체육복 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다..

파이썬에서 데이터프레임을 다루는 함수들 중 groupby, aggregate, pivot_table을 복습하고 예시문제들로 활용법을 연습해보자. Groupby groupby는 데이터를 그룹화하는 함수이다. df.groupby('그룹화할 컬럼') 옵션 axis: 그룹화 적용 축 level: 멀티 인덱스가 있을 경우의 레벨 지정 dropna: 결측값 계산에서의 제외 여부 df = pd.DataFrame({ 'key': ['A', 'B', 'C', 'A', 'B', 'C'], 'data1': [0, 1, 2, 3, 4, 5], 'data2': [4, 4, 6, 0, 6, 1] }) key를 기준으로 그룹화하고 그룹화는 평균값으로 계산 df.groupby('key').mean() Aggregate aggrega..

파이썬에서 고급함수 lambda, map, filter를 사용해서 코드를 더욱 간결하고 효율적으로 짤 수 있다. lambda lambda argument : expression 파이썬에서는 def로 함수를 정의한다. 만약 함수를 정의할 때 def 대신에 lambda를 사용한다면 보다 간결하게 정의할 수 있다. def 함수 def add(x, y): return x + y lambda 함수로 변경 lambda x, y: x + y 2줄의 코드를 lambda 함수를 사용해서 한 줄로 간결하게 정의할 수 있다. 모든 def 함수를 lambda로 변경해서 사용하는 것은 아니다. def의 함수가 길고 복잡한 형태라면 lambda 함수는 한 줄로 나열하기 때문에 오히려 가독성이 떨어지는 경우도 많다. 다소 간단한 ..

이진 탐색 알고리즘 정렬되어 있는 리스트에서 탐색 범위 좁히면서 하나씩 → 시작점, 끝점, 중간점을 이용하여 탐색 범위 좁혀나감 단계마다 탐색 범위를 2로 나누는 것과 동일해서 연산 횟수는 log2N에 비례 → 시간복잡도: O(logN) 활용 파이썬 라이브러리 from bisect import bisect_left, bisect_right bisect_left(a, x) : 배열 a에 v를 삽입할 가장 왼쪽 인덱스 반환 bisect_right(a, x) : 배열 a에 v를 삽입할 가장 오른쪽 인덱스 반환 → 값이 특정 범위에 속하는 데이터 개수를 구할 수 있음. 파라메트릭 서치 최적화 문제를 결정문제(yes or no)로 바꾸어 해결하는 기법 ex. 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 ..

수 정렬하기2 분류: 정렬 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 5 5 4 3 2 1 예제 출력 1 1 2 3 4 5 💡문제 해결 IDEA 1) 수는 중복되지 않기 때문에 계수 정렬은 x 2) 퀵 정렬로 시도 -> 메모리 초과 3) 삽입 정렬로 시도 -> 시간 초과 4) 계수 정렬로 시도 -> 걍 틀림.... 5) 퀵 정렬을 다시 정리 -> 약 25%까지 가다가..

영역 구하기 분류: 그래프 탐색 이론 (DFS/BFS) 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성..

동전0 분류: 그리디 알고리즘 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 예제 입력 1 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 출력 1 6 #1차 시도 N,..

그리디 알고리즘 탐욕 알고리즘이라고도 부름 "현재 상황에서 지금 당장 좋은 것만 고른다" -> 최적의 해를 보장할 수 없을 때가 많음 ex. 거스름돈 문제 [500, 100, 50, 10] => 가장 큰 화폐단위부터 Q. 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적해를 보장하는 이유? (정당성 분석) A. 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이기에 작은 단위의 동전을 종합해 다른해가 나올 수 없기 때문 그리디 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 함 문제1. 곱하기 혹은 더하기 문제: 각 자리 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' ..