→

[백준] 1268 | 임시 반장 정하기 [파이썬/python]

문제link: https://www.acmicpc.net/problem/1268학생의 수와 학생들이 1학년부터 5학년까지 몇 반이었는지가 제시된다. 한 번이라도 같은 반이 된 적 있는 학생 수가 가장 많은 학생을 임시 반장으로 선출하려 할 때, 임시 반장이 될 학생의 번호를 출력하는 문제이다.임시 반장이 될 수 있는 학생 수가 여러 명인 경우 가장 작은 번호를 출력한다. 접근한 번이라도 같은 반이 된 적 있는 학생 수를 세야 하므로, 한 사람과 1학년부터 5학년까지 쭉 같은 반이었든 1학년 때만 같은 반이었든 동일하게 취급한다.또, 임시 반장이 될 수 있는 학생 수가 여러 명인 경우 가장 작은 번호를 출력해야 한다. (모든 학생의 한 번이라도 같은 반이 된 적 있는 학생 수가 같을 때는 1번을 출력해야 ..

문제link: https://www.acmicpc.net/problem/1991주어진 트리를 전위 순회, 중위 순회, 후위 순회하고 결과를 출력하는 문제이다. 접근트리의 각 노드를 방문하며 순회 방법에 맞는 순서로 노드를 리스트에 저장해주었다.전위 순회의 경우 루트-왼쪽 자식-오른쪽 자식 순으로 순회하므로, 루트 노드 값을 리스트에 저장 후 왼쪽 자식 노드와 오른쪽 자식 노드를 차례로 방문한다.중위 순회의 경우 왼쪽 자식-루트-오른쪽 자식 순으로 순회하므로, 왼쪽 자식 노드에 방문한 후 리스트에 루트 노드 값을 저장하고, 이후 오른쪽 자식 노드에 방문한다.후위 순회의 경우 왼쪽 자식-오른쪽 자식-루트 순으로 순회하므로, 왼쪽 자식 노드와 오른쪽 자식 노드에 모두 방문한 후 루트 노드 값을 리스트에 저장한..

문제link: https://www.acmicpc.net/problem/5430배열의 초기값과 수행할 함수를 입력받아 결과를 구하는 문제이다.함수 R은 배열을 뒤집는 함수이다.함수 D는 배열의 첫 번째 값을 삭제하는 함수이다.배열이 비어 있을 때 함수 D를 실행할 경우 에러가 발생한다. 에러가 발생하는 경우에는 error를 출력한다. 접근문제를 풀고 난 후 다시 보니 deque를 사용하는 것이 훨씬 효율적이었을 것 같다. 삭제 연산의 개수가 많아봤자 배열 크기를 넘지 않는다.리스트와 인덱스를 이용해 문제를 풀었다. 최종적으로 배열 순서를 뒤집어야 하는지, 처음과 끝에서 값을 몇 개씩 잘라내야 하는지를 계산한 후 슬라이싱을 통해 결과를 출력했다. 배열이 '[1,2,3]' 이런 형식의 문자열로 주어진다. 자..

문제link: https://www.acmicpc.net/problem/33684요리사들이 소스를 섞을 수 있는 최대 횟수를 구하는 문제이다. 입력받는 값은 소스의 개수 N과 소스 맛의 상한 K, 각 소스의 맛 A1, A2..., An이다.N개의 소스가 존재하며, 각 소스의 맛은 정수로 표현된다. i번 소스의 맛은 정수 Ai이다.소스를 섞을 때, 요리사는 서로 다른 두 소스를 택해 하나의 소스에 다른 소스를 추가한다. 이때 섞인 소스의 맛은 두 소스의 맛을 더한 값이다. i번 소스에 j번 소스를 더하는 연산은 Ai = Ai + Aj로 표현할 수 있다. (j번 소스를 덜어 i번 소스에 넣은 것이기 때문에 j번 소스의 맛은 변하지 않는다.) 또, 소스는 재사용 가능하다. 이미 섞인 소스를 다시 다른 소스와 ..

문제link: https://www.acmicpc.net/problem/11403가중치가 없는 방향 그래프 G를 입력받아 모든 정점 (i, j)에 대해 i에서 j로 가는 길이가 양수인 경로가 있는지 구하는 문제이다. 접근i에서 j로 가는 간선이 존재하고, j에서 k로 가는 간선이 존재한다면, i에서 출발해 j를 거쳐 k에 도달하는 것이 가능하다. 이 점을 유의해 코드를 작성했다. 정점의 개수가 100개 이하이므로 삼중 for문을 돌리는 것도 무리없이 가능하다. 코드import sysinput = sys.stdin.readlineN = int(input())graphs = [list(map(int, input().split())) for _ in range(N)]for i in range(N): fo..

문제link: https://www.acmicpc.net/problem/14940지도 상의 모든 지점과 목표지점간의 거리를 구하는 문제이다.갈 수 있는 땅은 1, 갈 수 없는 땅은 0으로 표현된 지도가 제시된다. 접근처음부터 0으로 표현된 땅은 0, 1이어도 도달하지 못하는 땅은 -1로 표현해야 하기 때문에 이에 맞게 거리를 저장할 리스트를 초기화한다.목표지점에 대한 최단거리를 구해야 하므로 BFS를 활용했다. 목표지점에서부터 출발해 지도 내 이동 가능한 땅을 순회하며 거리를 저장한 후 출력했다. 코드import sysfrom collections import dequeinput = sys.stdin.readline#목표지점(2로 표시된 지점) 좌표를 반환하는 함수def find2(): for i ..

문제link: https://www.acmicpc.net/problem/2178미로가 주어질 때, (1, 1)에서 출발해서 (N, M)에 도달할 때까지 거치는 칸의 최솟값을 구하는 문제이다.1로는 이동할 수 있고, 0으로는 이동할 수 없다. 접근문제에서는 미로를 N*M 사이즈 배열로 표현하고 있는데, (1, 1)부터 (N, M)까지의 좌표가 존재한다. 0이 아닌 1부터 시작함에 유의해야 한다.(1, 1)에서 출발해, 이동 가능한 곳만 골라 미로를 순회해 답을 구했다. BFS를 활용했다. 코드import sysfrom collections import deque#input = sys.stdin.readlineN, M = map(int, input().split())maps = [list(map(int, i..

문제link: https://www.acmicpc.net/problem/1697수빈이가 동생을 찾는 데 걸리는 시간을 구하는 문제이다.수빈이의 위치가 X일 때, X-1, X+1, X*2로 이동할 수 있으며 한 번 이동할 때마다 1초가 걸린다. 접근수빈이의 위치 N과 동생의 위치 K가 주어지는데, K가 N보다 작을 수도 있음을 꼭 고려해야 한다!처음에는 DP로 풀까 했는데 코드가 복잡해지는 것 같아서(실력부족 때문일 수도 있다😅) BFS를 응용한 코드로 바꾸었다. 코드import sysinput = sys.stdin.readlineN, K = map(int, input().split())v = [0 for _ in range(K*2+1 if K > N else N*2+1)]tmp = set()tmp.ad..

문제link: https://www.acmicpc.net/problem/1389친구 관계를 입력받은 후 케빈 베이컨의 수가 가장 적은 사람을 출력하는 문제이다. 접근이차원 리스트를 만든 후, 리스트[a][b]에 a, b 사이 거리를 저장하도록 했다. a와 b가 친구 사이일 경우1, a==b인 경우 0, 친구가 아닌 경우 float('inf')로 초기화했고, 이후 [a][b] 값과 [a][x] + [x][b] 값을 비교하며 두 사람 간 거리 값을 업데이트하도록 했다. 문제에 제시되는 사람 수가 최대 100명이므로 삼중 for문을 활용했다.가장 적은 케빈 베이컨의 수가 아니라, 케빈 베이컨 수가 가장 적은 사람을 출력하는 문제이므로 케빈 베이컨 수를 비교할 때 케빈 베이컨 수와 사람 번호를 함께 저장해야 한..

문제link: https://www.acmicpc.net/problem/21736캠퍼스 지도를 입력받아, 도연이가 캠퍼스에서 만날 수 있는 사람의 수를 출력하는 문제이다.I는 출발점(현재 도연이가 위치하는 곳)이다.P는 사람이다.O는 빈 공간이다.X는 벽으로, 막혀 있기 때문에 이동할 수 없다. 접근도연이가 캠퍼스에서 만날 수 있는 사람의 수를 출력해야 하므로, I에서부터 출발해 I와 연결된 공간만 순회하면 된다. 따라서 I의 좌표를 찾아 따로 저장해두었다.X를 제외한 공간을 순회하며 P의 개수를 세고, 답을 출력하도록 했다.처음에는 재귀를 활용해 DFS로 구현했는데, 시간 초과가 발생해 BFS로 다시 구현했다.더보기(DFS로 구현한 코드) import syssys.setrecursionlimit(100..