👩🏻‍💻 은진의 로그파일 ✍️

👩🏻‍💻문제설명 [백준 18405] 경쟁적 전염 (Python) 문제요약 NxN 크기의 시험관이 있다. 모든 바이러스는 1번부터 K번까지 중 하나다. 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식한다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 빈칸으로만 증식할 수 있다. S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하시오. 단, S초 후 바이러스가 존재하지 않는다면, 0을 출력한다. 입력 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으..

👩🏻‍💻문제설명 [백준 3190] 뱀 (Python) 문제요약 (0, 0) 지점에서 시작하고, 머리는 오른쪽을 바라보고 있다. 머리 : 항상 이동할 다음 칸을 바라보고 있다. 이동한 칸에 사과가 있는 경우 : 꼬리는 움직이지 않음 이동한 칸에 사과가 없는 경우 : 꼬리칸 비우기 종료 조건 : 자기 자신 또는 벽과 닿았을 때 종료한다. 게임이 몇 초 뒤에 끝나는가? 입력 첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100) 다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다. 다음 줄에는 뱀의 방향 변환..

👩🏻‍💻문제설명 [백준 1052] 물병 (Python) ✍️Idea Sketch 문제요약 물병이 N개 있는데 1리터씩 들어있다. 물이 든 물병을 K개 이하로 만들어보자. 단, 재분배 규칙은 아래와 같다. 먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 물이 든 물병이 K개 이하가 되면 종료한다. 더이상 물병 두 개를 고를 수 없으면, 상점에서 물병을 살 수 있다. 물은 1리터 들어있다. 목표 : 상점에서 사야하는 물병의 최솟값을 출력하자. 예시 N=3이고, K=1인 경우를 예로 들어보자. 한 병을 또다른 병에 부으면, 2리터 물병 하나와, 1리터 물병 하나가 남는다. 만약 상점에서 1리터 물병 하나를 사면, 2리터 물병 두 개를 만들..

👩🏻‍💻문제설명 [이코테 Ch18-47] 청소년 상어 ✍️Idea Sketch 문제요약 그래프 공간 4×4크기의 공간이 있다. 한 칸에는 물고기가 한 마리 있다. 모든 물고기는 번호와 방향을 가지고 있다. 번호는 1~16의 자연수이며, 중복은 없다. 방향은 상하좌우, 대각선까지 포함하여 총 8가지이다. 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다. (반시계 방향) 이동 패턴 상어가 물고기를 잡아먹는다. 맨 처음에, 상어는 (0, 0)에 있는 물고기를 먹는다. 번호가 작은 물고기부터 이동한다. 상어가 이동한다. 물고기의 이동 번호가 작은 물고기부터 1칸만 이동한다. 물고기가 있는 경우, 두 물고기의 위치를 교환한다. 상어가 있는 칸이거나 벽인 경우, 방향을 반시계 방향으로 45도씩..

👩🏻‍💻문제설명 [이코테 Ch18-45] 최종 순위 (그래프) ✍️Idea Sketch 문제요약 팀은 1번부터 n번까지 번호가 매겨져 있다. 작년에는 최종 순위를 발표했다. 하지만 올해에는 작년과 비교하여 상대적인 순위가 바뀐 팀의 목록만 발표했다. 올해 목록을 바탕으로 올해 최종 순위를 만들어 출력해보자. "?"를 출력 : 확실한 순위를 찾을 수 없는 경우 "IMPOSSIBLE"을 출력 : 데이터에 일관성이 없어서 순위를 정할 수 없는 경우 알고리즘 : 위상 정렬 위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 작년의 최종 순위는 방향성을 가지고 있다. 이를 인접 리스트로 표현한 후, 올해의 목록에 따라 일부 간선의 방향을 바꾼다. 인접 ..

👩🏻‍💻문제설명 [이코테 Ch17-40] 숨바꼭질 ✍️Idea Sketch 문제요약 최단경로 중 가장 큰 값을 찾는 문제이다. 문제에서 "여기서 거리라 함은 지나야 하는 길의 최소 개수이다. " 라고 명시했다. 따라서 최단경로를 구하면 된다. 출발 헛간은 1번이다. 1번 헛간에서 x번 헛간까지의 최단경로를 모두 구하고, 그 중 가장 큰 값을 찾아야 한다. 가중치가 없고 모든 헛간을 탐색해야 한다. 시간복잡도 O(V + E) BFS의 그래프를 인접리스트로 구현하면 총 O(V + E)의 시간복잡도를 가진다. BFS는 모든 정점을 방문하므로 O(V)의 시간복잡도를 가진다. 이 때 한 정점을 방문할 때마다 간선을 통해 인접한 정점을 방문한다. 모든 간선도 방문하므로 O(E)의 시간복잡도를 가진다. 따라서 BFS..

👩🏻‍💻문제설명 [이코테 Ch16-35] 못생긴 수 못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 하며, 이를 수열로 늘어놓으면 다음과 같다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12… 편의상 1을 못생긴 수에 포함한다. 정수 n이 주어졌을 때, n번째 못생긴 수를 출력하는 프로그램을 작성하라. ✍️Idea Sketch 시간복잡도 O(nlogn) heap 라이브러리의 배열 원소 추가/삭제 시간복잡도는 O(logn)이다. 이를 고려하면 총 시간복잡도는 O(nlogn)이다. 알고리즘 : 다이나믹 프로그래밍 ✍️내 소스코드 전체 코드 import sys import heapq si = sys.stdin.readline n = int(si()) queue ..

👩🏻‍💻문제설명 [이코테 Ch16-34] 병사 배치하기 ✍️Idea Sketch 문제요약 병사들을 전투력 기준으로 내림차순 배치하고 싶다. 단, 전투력 중복은 허용되지 않으며, 병사를 열외시켜 내림차순 배치한다. 이 때 예외되지 않고 남아 있는 병사의 수가 최대가 되도록 하라. 시간복잡도 O(n^2) 이중 for문으로 이중탐색을 하기 때문에 O(n^2) 이다. 알고리즘 : 다이나믹 프로그래밍, LIS 가장 긴 증가하는 부분 수열 LIS의 전형적인 문제이다. 부분 수열의 최대 길이를 매 차례마다 계산하여 dp 배열에 저장하면 된다. ✍️내 소스코드 dp 배열 : i번째 병사가 마지막인 부분 수열의 최대 길이를 저장한다. 두번째 for문에서 i-1번째부터 역순으로 병사를 탐색한다. 전투력이 i번째 병사보다 ..

👩🏻‍💻문제설명 [이코테 Ch16-33] 퇴사 ✍️Idea Sketch 문제요약 남은 N일 동안 최대한 많은 상담을 하려고 한다. 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. 퇴사 전에 할 수 있는 상담의 최대 이익을 구하라. 시간복잡도 O(2^n) 각 날짜마다 상담을 하는 경우, 그렇지 않은 경우 총 2가지를 고려한다. 2 * 2 * 2 * … 총 n번 곱하므로 2^n이다. 알고리즘 : 브루트포스 알고리즘, 다이나믹 프로그래밍 브루트포스 알고리즘으로 구현했다. DFS로 상담을 하는 경우와 그렇지 않는 경우 둘 다 함수 호출했다. 그리고 정확히 퇴사날짜에 도달한 경우, 최대 이익을 계산한다. ✍️내 소스코드 종료조건 : 정확히 퇴사날짜 n에 도달한 경우..

👩🏻‍💻문제설명 [이코테 Ch16-32] 정수 삼각형 (DP) ✍️Idea Sketch 문제요약 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 시간복잡도 O(n) 위에서부터 아래까지 모든 수를 한 번씩 탐색하므로 O(n)이다. 여기서 n은 순차탐색을 의미하며, 문제의 삼각형의 크기 n과는 다르다. 알고리즘 : 다이나믹 프로그래밍 ✍️내 소스코드 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 따라서 dp[i-1][j..