Tieck's IT Blog

알고리즘

[문자열][programmers]문자열 압축 - 2020 KAKAO BLIND RECRUITMENT

문제 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 ..

알고리즘

[문자열][programmers]이상한 문자 만들기

문제 문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 완성하세요. https://programmers.co.kr/learn/courses/30/lessons/12930 코딩테스트 연습 - 이상한 문자 만들기 문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 programmers.co.kr 이해 입력 s : 한 개 이상의 단어로 구성된 문자열 각 단어는 하나 이상의 공백문자로 구분 출력 수정된 문자열..

알고리즘

[문자열][programmers] 문자열 내 마음대로 정렬하기

문제 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다. https://programmers.co.kr/learn/courses/30/lessons/12915 코딩테스트 연습 - 문자열 내 마음대로 정렬하기 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱 programmers..

알고리즘

[문자열][programmers] 문자열 내림차순으로 배치하기

문제 문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요. s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다. https://programmers.co.kr/learn/courses/30/lessons/12917 코딩테스트 연습 - 문자열 내림차순으로 배치하기 문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요. s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 programmers.co.kr 이해 입력 s : str은 길이 1 이상인 문자열 출력 문자를 큰것부터 작은 순으로 정렬된 문자열 조건 대문자는 소문자보다..

알고리즘

[문자열][programmers] 문자열 다루기 기본

문제 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴한다. https://programmers.co.kr/learn/courses/30/lessons/12918?language=python 코딩테스트 연습 - 문자열 다루기 기본 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴하면 됩니다. 제한 사항 s는 길이 1 programmers.co.kr 이해 입력 s : 길이 1 이상, 길이 8 이하인 문자열 출력 frue fa..

알고리즘

[로드맵] 코딩테스트 학습 개괄

학습 방법 파이썬 알고리즘 인터뷰 (a.k.a 상길북) 백준 문제 프로그래머스 문제 구글링 1. 책 빠르게 읽기 2. 해당 알고리즘에 관한 문제 풀기 3. 코드 리뷰 / 구글링(심화 학습) 기타. 코드 스닙셋 만들기, 블로그에 정리하기 학습 현황 문자열 21.10.04 - 상길북( ~ 6장 문자열 조작) 1회 > 프로그래머스 문자열 기본 더보기 https://programmers.co.kr/learn/courses/30/lessons/12918?language=python 코딩테스트 연습 - 문자열 다루기 기본 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴하면..

알고리즘

[Greedy][programmers]탐욕법 lv1 체육복

1. 문제 학생들의 번호 : 체격 순서 (바로 앞 또는 바로 뒤의 학생에게만 체육복을 빌려줄 수 있다.) 2. 이해 입력 전체 학생의 수 : n 체육복 X 학생들의 번호가 담긴 배열 : lost 여벌 체육복 O 학생 번호가 담긴 배열 : reserve 출력 return 체육 수업을 들을 수 있는 학생의 최댓값 조건 1 < n < 31 (n은 자연수) 1 중복O이면 lost, reserve에서 제거 및 lost, reserve를 갱신 2. reserve의 모든 번호를 +-1 하여 can_rend list 만들기 (for문) 3. best can_rend list 찾기 4. answer = n - # of lost 4. 구현 try 1: 65점, fail 의도 : 선택된 번호가 가장 많은 알고리즘 구현 : ..

알고리즘

[Greedy]그리디 알고리즘

현재 상황에 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘은 말 그대로 '탐욕스럽게' 매 순간 최선의 선택을 하는 기법이다. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않기 때문에, 최적해를 찾지 못하는 경우도 생긴다. 이런 단점을 극복하기 위해 가장 좋은 것만 선택하는 방식으로 문제를 풀 수 있는지 고려해야한다. 부분의 최선이 전체의 최선이 되지 못하는 예외 경우가 있는 지 판단하는 것이 관건이다. 그리디 알고리즘은 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 그러나 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에, 여러 유형과 섞여 출제된다. 일반적으로 그리디 알고리즘은 크기가 가장 큰 단위나 기준을 먼저 사용한다. 대표적으로 거스름돈..

알고리즘

시간복잡도 / 공간복잡도

복잡도 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 " 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 " 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 " 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 " 일반적으로 시간 복잡도와 공간 복잡도는 거래 관계 trade-off 성립 - 시간을 비약적으로 줄이는 기법 존재 : Memoization 등 시간 복잡도 빅오 Big-O 표기법 가장 빠르게 증가하는 항만을 고려하는 표기법 즉, 함수의 상한만 나타낸다. 시간 복잡도 낮은 순서 시간 복잡도가 클수록 입력 데이터의 크기가 증가할수록 실행 시간이 급격하게 증가한다. 시간제한을 준수하기 위해 적절한 알고리즘을 선택해야 한다. 실행시간이 입력 자료의 수 N에 영..

알고리즘

[codeup]6096 : 바둑알 십자 뒤집기(py)

문제 : 가로 19칸, 세로 19칸인 바둑판 위에 놓여있는 바둑돌의 현황을 입력받는다. 흰색 돌과 검은색 돌은 0과 1로 서로 다르게 표현한다. 바둑돌이 놓인 임의의 위치(x,y)를 입력받는다. 입력받은 모든 가로줄x 돌의 색을 반대로 바꾼다. 그 후 입력받은 모든 세로줄y 돌의 색을 반대로 바꾼다. n개의 좌표를 입력받아 뒤집기한 결과를 출력하라. 단, n은 10이하의 자연수이다. 예시: #임의의 좌표를 n번 입력받아 순서대로 x좌표, y좌표에 할당 for i in range(n) : x,y=input().split() #세로줄 색 변경 #중첩리스트(2차원)에서 y번째 리스트의 값을 순서대로 접근 후 변경 for j in range(1, 20) : if d[j][int(y)]==0 : d[j][int(..