컴공 공부

점수 하락... 

저번 진단테스트에서 DP에 대한 학습이 더 필요하다고 해서 DP를 한 문제 풀어보고 진단 테스트를 응시했다.

그런데 DP를 풀어보기도 전에 DFS에서 막혀버렸다.ㅎㅎ

당분간은 학업에 집중하고 겨울방학 때 Backtracking, DFS 문제를 더 풀어야겠다.

동전 거슬러주기 

문제 링크: https://www.codetree.ai/missions/2/problems/coin-change?&utm_source=clipboard&utm_medium=text

쉬운 난이도의 문제라 14분만에 해결했다.

아래는 본인이 작성한 테스트케이스를 완벽히 통과한 코드이다.

n, m = map(int, input().split())
coins = list(map(int, input().split()))
dp = [-1 for _ in range(m+1)]
dp[0] = 0  # 해당 금액에서 가능한 최소 동전의 개수

def in_range(i):
    return i >= 0 and i <= m

for i in range(1, m+1):
    for coin in coins:
        if in_range(i-coin) and dp[i-coin] != -1:
            if dp[i] == -1:
                dp[i] = dp[i-coin] + 1
            elif dp[i-coin] + 1 < dp[i]:
                dp[i] = dp[i-coin] + 1 

print(dp[m])

점수 유지중...

부족한 DP를 공부하지 않아서 계속 같은 점수를 유지하고 있다.

DP에 대한 학습이 더 필요하다고 나왔다.

앞으로는 DP를 먼저 공부하고 나서 남은 Backtracking, DFS, BFS문제를 풀어야겠다.

2명의 도둑 

문제 링크: https://www.codetree.ai/missions/2/problems/two-thieves?&utm_source=clipboard&utm_medium=text

4시간 넘게 고민을 하고 토론탭에서 도움을 받아 해결했다.

31번 테스트케이스가 통과되지 않았었는데, 내 경우에는 고른 영역의 무게가 C보다 클 때 처리하는 방법이 문제였다.

나는 처음에 무게가 가장 큰 물건을 우선적으로 포함하도록 했었다.

예를 들어 [9, 8, 4, 3, 2, 1] 영역을 골랐는데 C가 23이라면 9, 8, 4, 2가 선택되도록 했었다.

하지만 이렇게 하는 것이 항상 최대의 가치를 선택하게 하는 것은 아니었다.

그래서 모든 경우의 수를 고려해 최대 가치를 찾도록 코드를 수정하였더니 테스트케이스를 통과할 수 있었다.

아래는 본인이 작성한 테스트케이스를 완벽히 통과한 코드이다.

N, M, C = map(int, input().split())
rooms = [
    list(map(int, input().split()))
    for _ in range(N)
]

def findMaxVal(weights, selected_w, weight, value):
    '''최대 가치를 찾는 함수'''
    global C, max_value
    if len(weights) == 1:
        if weight + weights[0] <= C and value + weights[0]**2 > max_value:
            max_value = value + weights[0]**2
        elif weight <= C and max_value < value:
            max_value = value
        return
    findMaxVal(weights[1:], selected_w + [weights[0]], weight + weights[0], value + weights[0]**2)
    findMaxVal(weights[1:], selected_w, weight, value)

def thief1(cur_i):
    global max_value, selected_i, selected_j
    if cur_i == N:
        return
    cur_j = 0
    while cur_j <= N - M:
        weight = 0
        weights = []
        for k in range(M):
            weight += rooms[cur_i][cur_j + k]
            weights.append(rooms[cur_i][cur_j + k])
        if weight <= C:
            value = 0
            for i in range(M):
                value += weights[i] ** 2
            if value > max_value:
                max_value = value
                selected_i, selected_j = cur_i, cur_j
        else: # 무게가 C보다 크면
            before_maxV = max_value
            findMaxVal(weights, [], 0, 0)
            if before_maxV < max_value:
                selected_i, selected_j = cur_i, cur_j
        cur_j += 1
    thief1(cur_i + 1)

def thief2(cur_i):
    global max_value, selected_i, selected_j
    if cur_i == N:
        return
    cur_j = 0
    if cur_i == selected_i:
        while cur_j <= selected_j - M:
            weight = 0
            weights = []
            for k in range(M):
                weight += rooms[cur_i][cur_j + k]
                weights.append(rooms[cur_i][cur_j + k])
            value = 0
            if weight <= C:
                value = 0
                for i in range(M):
                    value += weights[i] ** 2
                if value > max_value:
                    max_value = value
            else: # 무게가 C보다 크면
                before_maxV = max_value
                findMaxVal(weights, [], 0, 0)
            cur_j += 1

        cur_j = selected_j + M
        while cur_j <= N - M:
            weight = 0
            weights = []
            for k in range(M):
                weight += rooms[cur_i][cur_j + k]
                weights.append(rooms[cur_i][cur_j + k])
            value = 0
            if weight <= C:
                value = 0
                for i in range(M):
                    value += weights[i] ** 2
                if value > max_value:
                    max_value = value
            else: # 무게가 C보다 크면
                before_maxV = max_value
                findMaxVal(weights, [], 0, 0)
            cur_j += 1

    else:
        while cur_j <= N - M:
            weight = 0
            weights = []
            for k in range(M):
                weight += rooms[cur_i][cur_j + k]
                weights.append(rooms[cur_i][cur_j + k])
            value = 0
            if weight <= C:
                value = 0
                for i in range(M):
                    value += weights[i] ** 2
                if value > max_value:
                    max_value = value
            else: # 무게가 C보다 크면
                before_maxV = max_value
                findMaxVal(weights, [], 0, 0)
            cur_j += 1
    thief2(cur_i + 1)

res = 0
max_value = 0
selected_i, selected_j = 0, 0
thief1(0)
res += max_value

max_value = 0
thief2(0)
res += max_value

print(res)

다시 최고 점수 달성!

이전에 찍었던 최고 점수와 동일한 점수가 다시 나왔다!

DP에 대한 학습이 더 필요하다고 나왔다.

앞으로 계속해서 Backtracking, DFS 문제들을 풀어나가면서 완벽하게 만들고 dp를 공부해야겠다. 

2명의 도

문제 링크: https://www.codetree.ai/missions/2/problems/two-thieves?&utm_source=clipboard&utm_medium=text

4시간 넘게 고민을 했지만 아직도 해결하지 못했다.

아래는 본인이 작성한 테스트케이스를 80% 정도 통과한 코드이다.

N, M, C = map(int, input().split())
rooms = [
    list(map(int, input().split()))
    for _ in range(N)
]

def thief1(cur_i):
    global max_value, selected_i, selected_j
    if cur_i == N:
        return
    cur_j = 0
    while cur_j <= N - M:
        weight = 0
        weights = []
        for k in range(M):
            weight += rooms[cur_i][cur_j + k]
            weights.append(rooms[cur_i][cur_j + k])
        value = 0
        if weight <= C:
            for i in range(M):
                value += weights[i] ** 2
        else: # 무게가 C보다 크면
            # 최대한 큰 무게들로 이루어진 조합을 찾는다.
            weights.sort()
            weight = 0
            for i in range(M-1, -1, -1):
                if weights[i] <= C - weight:
                    value += weights[i] ** 2
                    weight += weights[i]
                if weight == C:
                    break
        if value > max_value:
            max_value = value
            selected_i, selected_j = cur_i, cur_j
        cur_j += 1
        print("v:", value)
    thief1(cur_i + 1)

def thief2(cur_i):
    global max_value2
    if cur_i == N:
        return
    cur_j = 0
    if cur_i == selected_i:
        while cur_j <= selected_j - M:
            weight = 0
            weights = []
            for k in range(M):
                weight += rooms[cur_i][cur_j + k]
                weights.append(rooms[cur_i][cur_j + k])
            value = 0
            if weight <= C:
                for i in range(M):
                    value += weights[i] ** 2
            else: # 무게가 C보다 크면
                # 최대한 큰 무게들로 이루어진 조합을 찾는다.
                weights.sort()
                weight = 0
                for i in range(M-1, -1, -1):
                    if weights[i] <= C - weight:
                        value += weights[i] ** 2
                        weight += weights[i]
                    if weight == C:
                        break
            if value > max_value2:
                max_value2 = value
            cur_j += 1

        cur_j = selected_j + M
        while cur_j <= N - M:
            weight = 0
            weights = []
            for k in range(M):
                weight += rooms[cur_i][cur_j + k]
                weights.append(rooms[cur_i][cur_j + k])
            value = 0
            if weight <= C:
                for i in range(M):
                    value += weights[i] ** 2
            else: # 무게가 C보다 크면
                # 최대한 큰 무게들로 이루어진 조합을 찾는다.
                weights.sort()
                weight = 0
                for i in range(M-1, -1, -1):
                    if weights[i] <= C - weight:
                        value += weights[i] ** 2
                        weight += weights[i]
                    if weight == C:
                        break
            if value > max_value2:
                max_value2 = value
            cur_j += 1

    else:
        while cur_j <= N - M:
            weight = 0
            weights = []
            for k in range(M):
                weight += rooms[cur_i][cur_j + k]
                weights.append(rooms[cur_i][cur_j + k])
            value = 0
            if weight <= C:
                for i in range(M):
                    value += weights[i] ** 2
            else: # 무게가 C보다 크면
                # 최대한 큰 무게들로 이루어진 조합을 찾는다.
                weights.sort()
                weight = 0
                for i in range(M-1, -1, -1):
                    if weights[i] <= C - weight:
                        value += weights[i] ** 2
                        weight += weights[i]
                    if weight == C:
                        break
            if value > max_value2:
                max_value2 = value
            cur_j += 1
    thief2(cur_i + 1)

max_value = 0
selected_i, selected_j = 0, 0
thief1(0)
print(max_value)

max_value2 = 0
thief2(0)
print(max_value2)

print(max_value + max_value2)

정체중...

아무래도 일주일에 한 문제씩만 풀고 있다보니

당연히 실력 향상은 크게 되지는 않았다.

이번에는 4문제밖에 풀지 못했는데 생각보다 점수가 높게 나와서 의외였다.

DFS에 대한 학습이 더 필요하다고 나왔다.

앞으로 계속해서 Backtracking, DFS 문제들을 풀어나가면서 완벽하게 만들어야겠다.

사다리 타기 

문제 링크: https://www.codetree.ai/missions/2/problems/ladder-game?&utm_source=clipboard&utm_medium=text

3시간 넘게 고민을 하다가 해설을 참고해서 아이디어를 얻은 후 나만의 방식으로 다시 코드를 작성했다.

아래는 본인이 작성한 테스트케이스를 통과한 정답 코드이다.

n, m = tuple(map(int, input().split()))
lines = list()
for _ in range(m):
    a, b = tuple(map(int, input().split()))
    lines.append((b, a))
lines.sort()


def go(person, lines):
    '''한 사람의 결과(위치)를 반환'''
    global n
    cur_b, cur_j = 1, person
    while (True):
        found = False
        for line in lines:
            if line[0] >= cur_b and (line[1] == cur_j or line[1] == cur_j-1):
                found = True
                cur_b = line[0] + 1
                if line[1] == cur_j:
                    cur_j += 1
                else:
                    cur_j -= 1
                break
        if not found:
            break
    return cur_j


def ghostLeg(lines):
    '''게임의 결과를 반환'''
    global n
    global m
    result = [-1 for _ in range(n)]
    for person in range(1, n+1):
        pos = go(person, lines)
        result[pos-1] = person
    return result


def lineCmb(i, cmb):
    '''가능한 가로줄 조합들을 모두 찾아준다.'''
    global cmbs
    if i == m:
        cmbs.append(cmb)
        return
    cmb.append(lines[i])
    lineCmb(i+1, cmb[:])
    cmb.pop()
    lineCmb(i+1, cmb[:])


init_res = ghostLeg(lines)
min_m = m  # 최소 가로줄 수


cmbs = list()
lineCmb(0, [])

for cmb in cmbs:
    if len(cmb) < min_m and init_res == ghostLeg(cmb):
        min_m = len(cmb)

print(min_m)

최고기록 달성!! 

많이는 아니지만 Backtracking 문제를 몇 문제 풀었더니,

실력 진단 테스트를 하면서 그동안 막혔던 Backtracking 문제를 잘 풀 수 있었다.ㅎㅎ

dp에 대한 학습이 더 필요하다고 나왔다.

그렇긴 하지만 아직 Backtrackin, DFS, BFS 문제들을 다 풀어서 완벽하게 하고,

dp를 학습할 계획이다.

겹치지 않게 선분 고르기 

문제 링크: https://www.codetree.ai/missions/2/problems/select-segments-without-overlap?&utm_source=clipboard&utm_medium=text

고민은 좀 한 문제지만 1시간 반 안에 넉넉히 풀 수 있는 문제인 것 같다.

아래는 본인이 작성한 테스트케이스를 통과한 정답 코드이다.

n = int(input())
lines = []
for _ in range(n):
    x1, x2 = map(int, input().split())
    lines.append([x1, x2])

def selectMaxLine(selectedLines, i):
    global maxCnt
    if len(selectedLines) > maxCnt:
        maxCnt = len(selectedLines)
    
    if i >= n:
        return

    isOverlap = False
    for line in selectedLines:
        if (line[0] <= lines[i][0] and lines[i][0] <= line[1]) or (line[0] <= lines[i][1] and lines[i][1] <= line[1]) or (lines[i][0] < line[0] and lines[i][1] > line[1]):
            isOverlap = True
            break
    if not isOverlap:
        selectMaxLine(selectedLines + [lines[i]], i+1)
    selectMaxLine(selectedLines, i+1)


maxCnt = 0
selectMaxLine([], 0)
print(maxCnt)

Backtracking을 더 공부하자!!

3번째 문제에 아직 제대로 공부하지 않은 Backtracking이 나와서 풀지 못했다. 

실력 진단 결과 Backtracking을 공부해야 한다고 나왔다...!

아직 Intermediate Low의 1단원 Simulation만 끝내고 2단원인 Backtracking은 절반만 푼 상태였는데,

역시 진단 결과가 엄청 정확한 것 같다.

강력한 폭발 

문제 링크: https://www.codetree.ai/missions/2/problems/strong-explosion?&utm_source=clipboard&utm_medium=text

이 문제는 1시간 반 좀 넘게 걸린 문제다.

오랜만에 Backtracking을 푸려니 감이 잘 안 잡혔다.

그리고 Backtracking은 계속 재귀호출을 하기 때문에,

코드의 흐름을 파악하기가 힘들어서 조금 어려웠다.

아래는 본인이 작성한 테스트케이스를 통과한 정답 코드이다.

n = int(input())
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]
maxCnt = 0

def in_range(i, j):
    return i >= 0 and i < n and j >= 0 and j < n

bombs = []
for i in range(n):
    for j in range(n):
        if grid[i][j] == 1:
            bombs.append([i, j])

dis, djs = [[-2, -1, 1, 2], [-1, 0, 1, 0], [-1, -1, 1, 1]], [[0, 0, 0, 0], [0, 1, 0, -1], [-1, 1, 1, -1]]
def maxExplode(grid, bombs, cnt):
    global maxCnt
    if len(bombs) == 0:
        if cnt > maxCnt:
            maxCnt = cnt
        return

    i, j = bombs[0][0], bombs[0][1]
    for k in range(3): #3종류의 폭탄
        next_grid = [
            grid[i][:] for i in range(n)
        ]
        next_grid[i][j] = 2
        cnt2 = 1
        for index in range(4):
            new_i, new_j = i + dis[k][index], j + djs[k][index]
            if in_range(new_i, new_j) and next_grid[new_i][new_j] == 0:
                next_grid[new_i][new_j] = 2
                cnt2 += 1
        maxExplode(next_grid, bombs[1:], cnt+cnt2)

maxExplode(grid, bombs, 0)
print(maxCnt)

처음에는 maxExplode함수를 아래와 같이 작성하여 시간 초과로 인해 테스트케이스를 통과하지 못했다.

출력을 통해 확인해 봤더니 원하는 대로 동작을 다 한 다음에, 불필요한 동작을 하고 있었다.

그래서 왜 return이 안되고 불필요한 동작을 추가적으로 하는지에 대해 생각해보았다.

생각해보니 for bomb in bombs로 반복했던게 문제였다.

재귀호출을 하기 때문에 for bomb in bombs로 반복해주면 안된다.

그래서 for bomb in bombs를 지우고, 바로 아래 문장도 그에 맞게 바꾸었더니 정답으로 처리되었다.

def maxExplode(grid, bombs, cnt):
    global maxCnt
    if len(bombs) == 0:
    	#출력을 통해 확인
    	for i in range(n):
        	print(grid[i])
        print()
        if cnt > maxCnt:
            maxCnt = cnt
        return
	
    for bomb in bombs: #잘못된(정답과 다른) 부분
        i, j = bomb[0], bomb[1] #잘못된(정답과 다른) 부분
        for k in range(3): #3종류의 폭탄
            next_grid = [
                grid[i][:] for i in range(n)
            ]
            next_grid[i][j] = 2
            cnt2 = 1
            for index in range(4):
                new_i, new_j = i + dis[k][index], j + djs[k][index]
                if in_range(new_i, new_j) and next_grid[new_i][new_j] == 0:
                    next_grid[new_i][new_j] = 2
                    cnt2 += 1
            maxExplode(next_grid, bombs[1:], cnt+cnt2)