테크니션

https://school.programmers.co.kr/learn/courses/30/lessons/43162

DFS로 작성하여 스택이 다 빠지면 1씩 반환하여 그 수를 세도록 만들었다

def solution(n, computers):
    answer = 0
    stakk = []
    visited = []

    def serch(computers):
        while stakk:
            visited.append(stakk.pop(-1))
            start = visited[-1]
            for i in range(n):
                if computers[start][i] == 1 and i not in visited and i not in stakk:
                    stakk.append(i)
                    computers[start][i] = 0
                    computers[i][start] = 0
            for i in visited:
                computers[i][i] = 0
        return 1

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                stakk.append(i)
                answer += serch(computers)

    return answer

이렇게 하면 테스트케이스는 통과하는데 문제는 통과를 못한다

그래서 수정을 했다

def solution(n, computers):
    answer = 0
    stack = []
    visited = set()

    def search(computers):
        while stack:
            start = stack.pop()
            visited.add(start)
            for i in range(n):
                if computers[start][i] == 1 and i not in visited:
                    stack.append(i)
                    computers[start][i] = 0
                    computers[i][start] = 0
            computers[start][start] = 0
        return 1

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1 and i not in visited:
                stack.append(i)
                answer += search(computers)

    return answer

1. stakk을 stack으로 수정한 이유는 변수명을 명확하고 의미있게 하기 위해서입니다. stack은 일반적으로 스택 자료구조를 의미하기 때문에 보다 이해하기 쉽고 일반적인 표현입니다.
2. visited를 set()으로 초기화한 이유는 방문한 노드를 중복해서 방문하지 않도록 하기 위해서입니다. set()은 원소의 중복을 허용하지 않는 자료구조이므로 중복 방문을 방지할 수 있습니다.
3. serch 함수 내부에서 visited를 set()으로 변경한 이유는 방문한 노드를 빠르게 확인하기 위해서입니다. set()은 원소의 포함 여부를 빠르게 확인할 수 있으므로 visited에서의 탐색 시간을 줄일 수 있습니다. 또한, start를 stack.pop()으로 수정하여 스택의 마지막 요소를 가져오도록 하여 노드를 방문하게 되었습니다.
4. visited를 set()으로 변경하고, answer를 search 함수 호출 결과로 갱신한 이유는 방문한 노드의 개수를 적절히 카운팅하기 위해서입니다. visited는 중복 방문이 허용되지 않으므로 visited의 길이가 곧 방문한 노드의 개수가 됩니다. search 함수는 방문한 노드의 개수를 반환하므로 이를 answer에 누적하여 최종 결과를 계산할 수 있습니다.

https://www.acmicpc.net/problem/11047

그리디 알고리즘이란 매 순간의 최적의 해만 찾아가는 알고리즘이다

import sys
n = list(map(int, sys.stdin.readline().split()))
lst_coin =[]
for k in range(n[0]):
     j = int(sys.stdin.readline())
     if j < n[1]:
         lst_coin.append(j)
num_coi = 0
target = n[1]
while target>0:
    if target// max(lst_coin)>0:
        num_coi = num_coi + target//max(lst_coin)
        target = target -(target//max(lst_coin)) *max(lst_coin)
        lst_coin.remove(max(lst_coin))
    else:
        lst_coin.remove(max(lst_coin))
    print(num_coi)
    print(target)
    print(lst_coin)
print(num_coi)

답은 맞게 나오는데 틀렷다고 나온다

살려주세요

https://www.acmicpc.net/problem/10988

level

1

baekjoon

0

문자를 입력받아 리스트로 만들고

리스트 0번과 -1번을 비교해서

두개가 같으면 pop으로 날리는 과정을 반복해서

입력받은 문자 길이가 홀수면 마지막에 길이가 1인 리스트가 남고

입력받은 문자 길이가 짝수면 마지막에 길이가 0인 리스트가 남는지 확인해서 결과를 출력하였다

import sys
str = list(sys.stdin.readline())[:-1]
for i in range(int(len(str)/2)):
    if str[0] == str[-1]:
      str.pop(0)
      str.pop(-1)
if len(str) ==len(str)%2:
  print(1)
else:
  print(0)