합니다, 개발공부📝 합니다, 개발공부📝

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 서로 겹치지 않도록 전깃줄을 위치하기 위해서 제거해야하는 전깃줄의 갯수를 구하는 문제이다. 처음에는 순서와 상관없이 서로 교차하는 전깃줄의 교차여부를 2차원 배열에 담고, 교차하는 부분이 있는 전깃줄을 모두 제거해버리는 코드를 작성했었다. 그런데 이 코드는 중복해서 교차하는 전깃줄을 제거했을 때의 반영을 전혀하지 못하기 때문에 당연히 실패하였다😭 n = int(input()) rope = [] dp..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 최단경로를 구하는 다익스트라 알고리즘의 기본 문제 이다. 첫번째로 우선순위 큐를 이용해서 문제를 해결했다. 여기서 주의할 점은 파이썬의 경우 sys를 이용한 입력이 아닌 경우에 시간초과가 발생했다. from queue import PriorityQueue import sys inf = 100000000 v, e = map(int, sys.stdin.readli..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이전에 푼 토마토 문제에서 방향만 z방향으로 더 추가된 문제이다. https://dodop-blog.tistory.com/364 백준 7576) 토마토 (골드.5) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제의 조건을 확인하면 다음과 같다. 썩은 토마토부터 시작해서 전체를 다 탐색할 때까지 걸리는 시간을 구하는 BFS문제다. 1) 썩은 토마토는 1, 썩지 않은 토마토는 0, 토마토가 없는 곳은 -1로 주어진다. 3) 썩은 토마토는 하루가 지나면 인접해있는 앞뒤왼오의 네 방향의 토마토도 썩게 만든다. 2) 토마토가 모두 썩을 수 없으면 -1을 반환 3) 토마토가 모두 썩을 때까지 걸..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제의 조건은 다음과 같으며 백트래킹을 이용하여 퀸을 놓을 수 있는 모든 경우의 수를 찾는 것이다. 1) 같은 열에 퀸이 없을 것 2) 같은 행에 퀸이 없을 것 3) 퀸의 대각선(오른쪽, 왼쪽)으로는 다른 퀸을 위치하지 않을 것 이 문제는 python3로 풀때 계속해서 시간초과가 났기 때문에 해결방법을 찾지 못했다 😭 두번 모두 pypy로는 성공하였다 😭 내가 처음에 푼 코드는 다음과 같다. 이것이 다음에 확인한..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 먼저 문제의 조건을 확인해보자. 1) 직업이 상담사인 사람이 n+1일 째에 퇴사를 한다. 2) 각각의 상담에는 개별의 시간이 걸리기 때문에 다음 상담은 이전 상담이 끝나고 나서 진행할 수 있다. 3) 퇴사날 까지 일을 수행할 때 상담사가 벌 수 있는 최대 이익을 구한다. 먼저 제일 먼저 생각했던 방법은 dfs를 이용해서 상담이 가능한 모든 경우의 수를 구하고 최대 이익을 구하는 방법이었다. 만약 첫번째 상담을 하기로 했으면 그 다음 상담이 가능한 경우는 첫번째 상담일 수가 지난 후일 것이기 때문에 범위는 range(idx, n)으로 ..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제의 조건은 다음과 같다. 1) 총 사람수는 짝수로 이루어져 있다. 2) 팀원수는 각각 n/2명이 된다 3) 팀원 각각의 쌍의 능력치를 더한 값이 팀이 능력치가 된다 4) 팀별로 능력치가 가장 작을 때의 차이 출력 가장 먼저 생각한 것은 팀원의 조합을 이용하여 모든 팀이 생성되는 경우의 수를 구하고 각각의 팀점수를 구해서 차이의 최솟값을 찾는 해법을 생각했다. from itertools import combinati..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 시뮬레이션 문제로 조건에 따라 이동시키는 문제이다. 조건을 확인하면 다음과 같다. 1) 뱀은 0, 0 위치에서 시작하여 처음엔 오른쪽으로 이동한다. 2) 방향조건이 D일 경우 오른쪽, L일 경우 왼쪽으로 이동한다. 3) 시간조건은 처음 이동을 시작할 때부터 방향을 바꿀때 까지의 시간을 나타낸다. 4) 이동할 칸에 사과가 있으면 뱀의 꼬리는 줄어들지 않는다. 5) 이동할 칸에 사과가 없으면 뱀의 꼬리는 한..