본문 바로가기

분류 전체보기

[C] 소수 판별하기 / 에라토스테네스의 체 / 소인수 분해 1. 소수 판별하기 소수는 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미한다 정수를 입력하였을 때 이를 판별할 수 있는 가장 단순한 알고리즘을 알아보도록 하자 1, 2 예외 처리 후, 3 ~ n-1의 모든 수를 순회하며 n의 약수가 있는지 확인하는 방법이 있다 최적화 1) √n * √n = n 이므로, n-1까지 순회하는 대신, √n까지만 순회한다 최적화 2) 2를 예외 처리한다면 그 외 모든 짝수는 합성수이므로 배제한다 두 가지의 최적화를 거친 후, 코드는 다음과 같다 #include #include #include //bool, true, false #include //sqrt() _Bool isPrime(int n) { if (n 더보기
[점프 투 파이썬 6장 연습 문제] 문자열 압축하기 / Duplicate Numbers / 모스 부호 해독 1. 문자열 압축하기 input ) aaabbcccccca output ) a3b2c6a1 반복문을 이용하여 문자를 하나씩 탐색하며 기준 문자를 설정한다 기준 문자와 다른 경우에는 기준 문자를 업데이트 시킨 후, cnt 값을 1로 초기화 한다 기준 문자와 같은 경우에는 cnt 값을 +1 한다 코드는 다음과 같다 str = input() length = len(str) word = '' cnt = 1 for i in range(0, length): word = str[i] # for word in str 로 표현 가능 if(i+1 < length): if(word == str[i+1]): cnt += 1 else: print("%c%d" % (word, cnt), end="") # 문자열 포맷팅 cnt =.. 더보기
[백준 12015번][C] 이진 탐색(Binary Search)을 이용한 LIS(최장 증가 수열) 최장 증가 부분 수열, LIS(Longest Increasing Subsequence)는 임의의 수열에서 몇 개의 수를 제거하여 만든 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 말한다 예를 들어 다음 수열이 주어졌다고 하자. 10 20 10 30 20 50 위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다. 10 10 30 20 (20, 20 제거) 10 30 20 50 (20, 10 제거) 20 10 30 (10, 20, 50 제거) 10 20 50 (10, 30, 20 제거) ... 이들 중 네번째 수열은 오름차순으로 정렬되어 있다. 이를 '증가 부분 수열'이라고 한다. 그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다. 부분수열 10 20 3.. 더보기
[Python] 클래스의 "self" 개념 클래스 함수를 선언할 때에도 def fun(self[ , .. ]) self가 들어가고 이를 어떻게 이해할 지 모를 수 있다 간단하게 말하면, 클래스에 의해서 생성된 인스턴스를 지칭한다고 할 수 있다 다음 예시를 보자 class Ex: def __init__(self, num): self.num = num 라는 클래스 Ex에 ex1 = Ex(27) 인스턴스 ex1를 이렇게 선언하면 다음과 같이 수행된다 self.num = num self는 ex1이라는 인스턴드를 받게 되므로 다음과 같이 바뀐다 ex1.num = num 그리고 이는 값이 27이므로 다시 다음과 같이 바뀐다 ex1.num = 27 인스턴스와 입력값을 연결해 주는 것이 self이다 지칭의 의미라고 생각하면 이해가 빠를 것이다 더보기
[Python] while문, for문으로 피라미드 출력하기 1) while 문 이용 i = 0 while 1: i += 1 if i > 5: break print(' ' * (5-i), end="") print("*" * (i*2-1)) """ 출력: * *** ***** ******* ********* """ Line 1 - 인덱스 변수 i를 선언한다 Line 2 - i가 5를 넘어가면 빠져나가는, 무한 루프 while 문을 선언한다 Line 5 - 4, 3, 2, 1, 0 으로 줄어드는 만큼 빈칸을 출력한다 후에 , end="" 로 이어서 출력함을 입력해줌 Line 6 - 1, 3, 5, 7, 9 로 늘어나는 만큼 *을 출력한다 2) for 문을 이용 for i in range(1,6): print(' ' * (5 - i), end="") print("*" .. 더보기

티스토리툴바