Tieck's IT Blog

알고리즘

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

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

알고리즘

시간복잡도 / 공간복잡도

복잡도 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 " 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 " 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 " 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 " 일반적으로 시간 복잡도와 공간 복잡도는 거래 관계 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(..