[알고리즘 스터디] 1주차 결산

0921

def three_vowel_or_consonat(s: str):   //3중 반복을 확인하는 함수
    vowels = set('aeiou')

    if len(s) < 3:
        return True
    v = c = 1
    
    for i in range(1, len(s)):
        cur_v = s[i] in vowels
        prev_v = s[i-1] in vowels
        if cur_v and prev_v:    
            v += 1; c = 1
        elif not cur_v and not prev_v:  
            c += 1; v = 1
        else:
            v = c = 1
        if v >= 3 or c >= 3:      
            return False
    return True

def repeat(s: str):   //이중 반복을 확인하는 함수(지정된 모음 'e', 'o'는 허용)
    allowed_vowel = 'e', 'o'
    count = 1
    prev = s[0]

    for ch in s[1:]:
        if ch == prev:
            count += 1
            if count >= 3:
                return False
        
        else:
            if count == 2 and prev not in allowed_vowel:
                return False
            prev = ch
            count = 1

    if count == 2 and prev not in allowed_vowel:
        return False
    
    return True

def func(password): 
    vowels = set('aeiou')
    status = True

    status = status and any(ch in vowels for ch in password)     
    status = status and three_vowel_or_consonat(password)     
    status = status and repeat(password) 

    return status


while(True):
    password = input()
    if(password == 'end'):
        break

    comp = func(password)
    print(f"<{password}> is{' not' if not comp else ''} acceptable.")

풀이과정 :

1. 기본 함수 func: 입력받은 비밀번호의 허용/비허용 여부를 판단하는 함수를 만든다. 해당 함수에서 직접적으로 판단하는 조건은 ‘모음이 포함되었는가?’만이다
2. 이중 반복 확인 함수 repeat: 허용되는 모음을 미리 설정한 뒤, 문자열의 첫번째 글자(prev)를 지정해 뒤 글자와 비교한다. 이후 시행이 끝나면 prev는 다음 글자로 옮긴다. 만약 중간에 잘못된게 없으면 True를 return한다.
3. 삼중 반복 확인 함수 three_vowel_and_consonat: 현재 글자와 이전 글자의 모음 여부를 확인하는 두 변수를 만든다. 이후 조건문과 반복문을 통해 삼중 반복이 존재하는지 확인한다.

배운 점:

3중 반복 함수를 만들며 기본적인 탐색 알고리즘 사용법을 알게 되었다.

시행 횟수가 꽤 많은데, 문제를 풀며 사소한 실수가 많았다(출력문에 <>처리 안함, 온점 안 찍음, return True에서 return 안 씀…)문제를 풀며 성급한 성격을 고쳐야 할 것 같다

코드에서 사소하게 줄일 수 있을 것 같은 부분이 보이는데(모음 set 반복 등…) 고민하며 줄이는 습관을 들이고 싶다

지금 와서 보니까 status 초기 설정 True로 굳이 안해도 될 것 같다. 함수들에서 전부 마지막에 True 리턴이 있기에...

 

0922

def func(maxnum, num):
    lst = [i+1 for i in range(maxnum)]
    newlst = []
    idx = 0

    while lst:   
        idx = (idx + num - 1) % len(lst) 
        newlst.append(lst.pop(idx))

    
    return newlst
            
maxnum, num = map(int, input().split())

resultLst = func(maxnum, num)

print(f"<{', '.join(map(str, resultLst))}>")

풀이과정 :

함수에서 1~maxnum을 차례대로 담은 기존 리스트와 새로운 답안 리스트를 만든다. lst가 공백이 아니라면, 반복문 내에서 답안 리스트에 답을 채우는 걸 반복한다

배운 점: 예전에 시도했다가 못 푼 문제였는데, 그때는 len(lst)≥num인 케이스와 아닌 케이스로 구분하느라 많이 꼬였었다.

 

0923

#include <iostream>
using namespace std;

int main(void) {
    int E, S, M;
    cin >> E >> S >> M;

    int year = 1;
    while (true) {
        int e = (year % 15 == 0) ? 15 : year % 15;
        int s = (year % 28 == 0) ? 28 : year % 28;
        int m = (year % 19 == 0) ? 19 : year % 19;

        if (e == E && s == S && m == M) {
            cout << year;
            break;
        }
        year++;
    }

    return 0;
}

풀이과정 : year % 15를 통해 약수 개수를 따지지 않고 단순히 같은지만 비교했다. 실패시 year++을 통해 정답이 나올 때까지 계속 반복했다…

배운 점: 더 효율적인 알고리즘이 존재할 수도 있지만, 해당 코드의 시간 복잡도가 O(152819)로 작은 편이기에 그냥 노가다 방식을 선택했다. 아마 문제의 티어가 높았으면 새로운 방식을 생각해야 할 것 같다

 

0924

def binary_search(total, win):    
	nowZ = (win * 100) // total   
	low, high = 1, 10**9    
	result = -1
	    
	while low <= high:        
		mid = (low + high) // 2        
		newZ = ((win + mid) * 100) // (total + mid)
		if newZ > nowZ:            
			result = mid            
			high = mid -1        
		else:            
			low = mid + 1        
		return result
		
	total, win = map(int,input().split())
	num = binary_search(total, win)
	print(num)

풀이과정 : 수를 입력 받은 후 이분 탐색 함수로 보낸다

문제의 제한 조건대로 low는 1, high는 10^9로 잡은 뒤, newZ가 nowZ보다 커질 때까지 중앙값을 옮겨가며 탐색한다. 이때 시간 복잡도는 O(logN)이 된다

참고 블로그: https://velog.io/@kimdukbae/이분-탐색-이진-탐색-Binary-Search

배운 점: 이분 탐색을 적용시키는 방법을 배웠다.

처음에 nowZ 연산에 int((win / total) * 100)을 사용했는데, 예시 입출력에는 문제가 없어도 백준 내부에서 틀림으로 처리하기에 고쳤다.

 

0925

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int func(const vector <int>& arr){
	if (arr.empty()) return 0;
	
	int maxSum = arr[0];
	int pMax = arr[0];
	
	for(size_t i = 1;i < arr.size(); i++){
		pMax = max(pMax + arr[i], arr[i]);
		maxSum = max(maxSum, pMax);
		}
	
	return maxSum;
}

int main(void) {
    int num(0), inputNum(0);
	vector <int> arr;
	cin >> num;
	
	for(int i = 0; i < num; i++){
		cin >> inputNum;
		arr.push_back(inputNum);
    }
	cout << func(arr);

    return 0;
}

풀이과정 : 단순하게 입력받은 값의 최대 부분합을 찾는 알고리즘을 작성하면 된다

1. pMax : 직전까지의 부분합에 현재 원소를 이어붙이는 경우
2. arr[i] : 새로운 부분합을 현재 원소에서부터 새로 시작하는 경우

를 비교해 계속 갱신하면 된다

참고 블로그: https://velog.io/@foreknowledge/배열의-최대-부분합-알고리즘-Maximum-subarray-problem

배운 점: 최대 부분합 알고리즘을 처음 사용해봤다

 

0926

num = int(input())
stack = []

for i in range(num):
    str = input()
    truth = False

    for j in range(len(str)):
        if str[j] == '(':
            stack.append('(')

        elif str[j] == ')':
            if len(stack) == 0:
                stack.append(')')
                break
            if len(stack) != 0:
                stack.pop()

    if len(stack) == 0:
        truth = True
    stack = []
    print('YES') if truth == True else print('NO')

풀이과정 : 스택의 성질을 사용하여 풀었다. ‘(’ 입력이 들어올 때만 스택에 값을 추가한다. 만일 ‘)’ 값이 들어온다면, 스택에서 값을 지운다(단, 스택이 비어있을 경우 스택에 값을 추가한 뒤 반복문을 탈출한다) 입력값을 탐색하는 과정이 끝났다면 스택에 몇 개의 값이 들어있는지 확인한다. 스택의 값이 0이라면 ‘(’이 입력된 횟수==’)’이 입력된 횟수이기에 이 경우에만 YES를 출력한다. 이후 스택을 다시 비운다

배운 점: 스택을 유연하게 이용하는 방법을 알게 되었다. 마지막에 스택을 다시 비워주는 것을 생각해내지 못해 자꾸 엉뚱한 답변이 나왔기에, 이런 사소한 점들을 잘 체크해야 할 것 같다