우노

문제 링크 https://www.acmicpc.net/problem/1068 풀이 먼저, 각 노드의 부모 배열을 탐색하며, 지워야하는 노드와 해당 노드가 부모 노드인 자식 노드들의 값들을 모두 특정 값(-2)으로 변환합니다. 이후, 각 노드의 부모 배열을 다시 한 번 탐색하며, 값이 -2 가 아니며, 해당 노드를 부모로 하는 노드가 부모 배열에 없을 경우, 리프 노드의 개수를 +1 합니다. 코드 import sys # 트리의 노드의 개수 n = int(sys.stdin.readline()) # 0번 노드부터 N-1번 노드까지, 각 노드의 부모 arr = list(map(int, sys.stdin.readline().rstrip().split(" "))) # 지우려는 노드 remove_node = int(..

문제 링크 https://www.acmicpc.net/problem/1707 풀이 이분 그래프(Bipartite Graph)란? 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프입니다. 탐색을 진행하며, 현재 노드와 이웃한 노드의 색을 확인하고, 동일한 색으로 칠해져있다면, 이분 그래프가 아닌 것으로 판단합니다. 코드 import sys sys.setrecursionlimit(10**6) # 테스트 케이스의 개수 t = int(sys.stdin.readline()) # 현재 노드와 이웃한 노드 탐색 def dfs(node): global result for neighbor in graph[node]: # 이웃 노드에 색칠이 되어있지 않다면 if (visited[..

문제 링크 https://www.acmicpc.net/problem/11724 풀이 연결 리스트를 사용해 입력 간선 정보를 양방향으로 저장 1차원 배열을 사용해 각 노드가 어떤 그룹에 속해있는지를 저장 1번 노드부터 마지막 노드까지 순서대로 탐색하며, 현재 노드와 연결된 노드들을 모두 같은 그룹으로 처리 추가 사항 BOJ의 채점 서버에서, Python의 최대 재귀 깊이는 1,000으로 설정되어있습니다. 만약, 재귀 호출 횟수가 해당 값을 넘어가게되면 ReferenceError가 발생하게 됩니다. 따라서, sys.setrecursionlimit()을 사용해 최대 재귀 깊이를 변경해야합니다. 코드 import sys sys.setrecursionlimit(10**6) # 정점의 개수 N과 간선의 개수 M n..

문제 링크 https://www.acmicpc.net/problem/11725 풀이 2차원 연결 리스트를 사용해, 각 노드간 연결 정보를 양방향으로 모두 저장합니다. 루트 노드(1)부터 연결된 노드들을 확인하며, 연결된 노드의 부모 노드가 없을 경우, 현재 노드를 연결된 노드의 부모 노드로 저장합니다. 이후, 연결된 노드들을 기반으로 다시 DFS를 진행합니다. 추가 사항 BOJ의 채점 서버에서, Python의 최대 재귀 깊이는 1,000으로 설정되어있습니다. 재귀 호출 횟수가 해당 값을 넘어가게되면 RecursionError가 발생하게 됩니다. 따라서, sys.setrecursionlimit()을 사용해 최대 재귀 깊이를 변경해야합니다. 코드 import sys sys.setrecursionlimit(1..

문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 식의 계산은 연산자 우선..

문제 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다. 용어의 정의 '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 ..

문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 입력 조건 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 = 0 and ny < m): # 인접 노드에 음료수를 채울 수 있는지 확인 if (ice_board[nx][ny] == 0): # 인접 노드 방문 dfs(nx, ny) # 모든 위치에 음료수 채우기 for i in range(n): for j in range(m): # 해당 노드에 음료수를 채울 수 있다면 if (..

문제 링크 https://www.acmicpc.net/problem/9466 풀이 중요 변수 설명 done : 팀 매칭 결과 배열 0 : 아직 팀 매칭 결과를 모르는 학생 1 : 팀 매칭 결과를 아는 학생 visited : 방문 배열 0 : 아직 방문하지 않은 학생 1 : 방문한 학생 알고리즘 반복문을 통해, 현재 학생이 아직 방문한 적이 없는 학생이라면, 탐색 시작 현재 학생은 방문한 것으로 처리 현재 학생이 원하는 다음 학생이, 이전에 방문된 적이 없다면, 다음 학생을 탐색 현재 학생이 원하는 다음 학생이, 이전에 방문된 적은 있지만, 아직 팀 매칭이 끝나지 않은 학생이라면 현재 학생과 다음 학생을 기준으로, 연결된 사이클을 확인하며, 사이클에 속한 인원을 계산 4 → 7 → 6 → 4 인 경우, 팀..

문제 링크 https://www.acmicpc.net/problem/1987 풀이 이미 방문한 위치를 제외하고, 상하좌우로 최대한 얼마만큼 갈 수 있는지에 대한 문제이다. 방문 여부는 'alphabet' 1차원 배열을 사용해 저장했다. 알파벳은 'A' 부터 'Z' 까지의 문자로 이루어져있으며, 각 문자를 int형으로 변환하면, 10진수 65 ~ 90 의 값으로 이루어져있다. 따라서, 'A' 의 경우 int형 변환 후, 65를 빼면 0 이기 때문에, 0번째 index 를 'A'의 위치로 설정하고 'Z' 는 65 를 빼면 25 이기 때문에, 25번째 index 를 'Z'의 위치로 설정했다. 그리고 dfs 함수..

문제 링크 https://www.acmicpc.net/problem/1199 오일러 경로 및 오일러 회로 공통점 무향이나 유향 그래프가 있을 때, 그래프에 존재하는 모든 간선을 정확히 1번 씩만 방문하는 연속된 경로 차이점 시작점과 도착점이 다르면 오일러 경로 시작점과 도착점이 같으면 오일러 회로 오일러 경로 및 회로의 존재 여부 판단 무향(or 양방향) 그래프의 경우 차수가 홀수인 정점이 2개일 때, 오일러 경로 존재 즉, 시작점과 도착점의 차수만 홀수일 때 차수가 홀수인 정점이 0개일 때, 오일러 회로 존재 즉, 모든 정점의 차수가 짝수일 때 무향 그래프이기 때문에, 시작점과 끝점을 제외하고서는, 들어오는 간선이 있다면 반드시 나가는 간선이 하나 더 있어야한다. 따라서, 차수는 항상 2의 배수꼴을 가..