→

문제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..

문제link: https://www.acmicpc.net/problem/30804문제에서는 탕후루에 꽃힌 과일의 종류를 숫자(1~9)로 구분하여 제공한다. 막대의 앞쪽, 뒤쪽에서 과일을 제거해 탕후루에 꽂힌 과일을 두 종류 이하로 만들었을 때 가질 수 있는 과일 개수의 최대값을 구하는 문제이다. 접근같은 종류인 과일은 연속되어도 상관없으므로 입력받은 탕후루 내 과일 목록을 [종류, 개수] 형태로 정리해 리스트에 저장했다. 같은 종류 과일이 연달아 나올 경우 이렇게 바꾸어 계산하면 더 효율적일 것이라고 판단했다.ex) 5, 1, 1, 2, 1 -> [5, 1], [1, 2], [2, 1], [1, 1]이후, 집합을 활용해 현재 확인 중인 범위 내 과일을 두 종류 이하로 제한하며 과일 개수를 세고, 최대값을..

문제link: https://www.acmicpc.net/problem/18111문제에서 주어진 규칙에 따라 땅을 고르게 만드는 데 필요한 시간의 최솟값과 그때의 층수를 출력하는 문제이다. 접근처음에는 이분 탐색을 활용해 코드를 작성했으나 문제를 풀 수 없었다. 찾아야 하는 것은 시간의 최솟값인데 층수를 기준으로 이분 탐색을 진행하고 있었기 때문이다.브루트포스를 활용해 코드를 다시 작성했다. 층수 범위가 0층~256층이므로, Counter를 활용해 n층인 블록 개수를 따로 저장해 사용했다. 코드import sysfrom collections import Counterinput = sys.stdin.readlineN, M, B = map(int, input().split())grounds = []for _..