3주차

1) 문제풀이

3273번: 두 수의 합 (acmicpc.net)

3273번: 두 수의 합

n = int(input())
array = list(map(int,input().split()))
target = int(input())
array.sort()
start = 0
end = n-1
count = 0
while start<end:
    if array[start] + array[end] < target:
        start += 1
    elif array[start] + array[end] == target:
        count += 1
        end -= 1
    else:
        end -= 1

print(count)

우선 이 문제는 투 포인터 알고리즘으로 풀 수 있다. 투 포인터 알고리즘은 n의 가짓수가 많을 때 이진탐색과 같이 생각해볼 수 있는 알고리즘이다. 시간복잡도는 O(N)으로 n이 10만이여도 가능하다.

 

두 수의 합 문제는 우선 입력받은 리스트를 정렬하고, 투 포인터를 시작과 끝에 배치하면 쉽게 풀 수 있다. target의 값보다 작을 경우는 start인덱스를 높이고 target의 값이 클 경우는 end인덱스를 낮추는 방법으로 풀 수 있다.

 

하지만, 이번 문제는 조건이 상당히 널널하므로 다른 방법으로도 풀 수 있다.

이처럼 매번 값을 dictionary에 저장하고 더해서 target이 되는 값의 갯수를 count에 추가하는 방식으로도 풀 수 있다.

n = int(input())
dic = {}
array = list(map(int,input().split()))
target = int(input())
count = 0
for i in array:
    if i in dic:
        print(target-i)
        if (target-i) in dic:
            count += dic[target-i]
        dic[i] += 1
    else:
        if (target-i) in dic:
            count += dic[target-i]
        dic[i] = 1

print(count)

 

1182번: 부분수열의 합 (acmicpc.net)

1182번: 부분수열의 합

n, s = map(int,input().split())
array = list(map(int,input().split()))
count = 0

def DFS(v,sm):
    global count
    if v == n:
        if sm == s:
            count += 1
        return
    DFS(v+1,sm+array[v])
    DFS(v+1,sm)

DFS(0,0)
if s == 0:
    print(count-1)
else:
    print(count)

부분수열의 정의는 2주차 문제중 이진탐색 알고리즘을 다루는 문제에서 찾아볼 수 있다. 이번 문제에서는 DFS를 활용해서 값을 더하던지 더하지 않던지 하는 방법으로 풀 수 있다. N의 최댓값이 20이므로 시간복잡도는 2^20, 약 100만으로 널널하게 풀 수 있다.

이 문제에서 s가 0일땐 모두 더하지 않는 경우가 발생(공집합)할 수 있으므로 count에서 -1을 해줬다.

 

1912번: 연속합 (acmicpc.net)

1912번: 연속합

n = int(input())
array = list(map(int,input().split()))
check = [array[0]]
for i in range(1,len(array)):
    if check[i-1] < 0:
        check.append(array[i])
    else:
        check.append(array[i]+check[i-1])
print(max(check))

연속합 이 문제는 DP로 풀 수 있다. DP문제는 항상! 전 결과값을 다음에서 이용한다는 점이 중요하다.

이 문제도 마찬가지이다. array앞에서부터 계산을 하는데 결과값을 담은 check리스트를 이용한다. 해당 인덱스 전까지의 합이 양수이면 더하는게 이득이므로 더하게 되고, 해당 인덱스 전까지의 합이 음수이면 현재 자신의 값을 기록하는게 더 큰 값을 저장하는 것이므로 자신의 값만 check 리스트에 저장한다.

 

결과적으로 check에는 각 인덱스까지의 연속합중에서 가장 큰 값만이 저장된다.

 

코딩테스트 연습 - 불량 사용자 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 불량 사용자

def solution(user_id, banned_id):
    def checkStr(user,banned):
        length = len(banned)
        for i in range(length):
            if banned[i] == '*':
                continue
            else:
                if user[i] != banned[i]:
                    return False
        return True
    visited = [False for _ in range(len(user_id))] 
    check = []
    def DFS(v,store):
        if v == len(banned_id):
            a = sorted(store)
            if a not in check:
                check.append(a)
            return
        for i in range(len(user_id)):
            if len(user_id[i]) != len(banned_id[v]):
                continue
            if checkStr(user_id[i],banned_id[v]) and visited[i] == False:
                visited[i] = True
                store.append(user_id[i])
                DFS(v+1,store)
                store.pop()
                visited[i] = False
    DFS(0,[])
    return len(check)

우선 이 문제는 불량사용자가 될 수 있는 경우의 수를 출력해야 하는 문제이다. 우선, 불량 사용자 아이디와 일치하는지를 확인해주는 checkStr 함수를 선언해주고, DFS 내부에서 이 함수를 통해서 걸러준다. DFS는 visited 변수를 통해서 방문 했는지를 측정해주고, 깊이를 통해서 출력을 해준다. store는 각각의 경우의 수를 저장해주는 리스트이고 특정 깊이가 되면 정렬을 해주고 check 리스트에 저장해준다. (정렬해주지 않으면 가짓수 오류가 생김)