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

👩🏻‍💻문제설명 [이코테 Ch6-4] 두 배열의 원소 교체 (정렬) 동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야한다. N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하라. 예를 들어 N = 5, K = 3이고, 배열 A와 B가 ..

👩🏻‍💻문제설명 [이코테 Ch5-4] 미로탈출 (BFS) N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 첫째 줄에 두 정수 N, M(4

👩🏻‍💻문제설명 [이코테 Ch4-1] 상하좌우 (구현) 여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다. L: 왼쪽으로 한 칸 이동 R: 오른쪽으로 한 칸 이동 U: 위로 한 칸 이동 D: 아래로 한 칸 이동 이때 여행가 A가 N × N 크기의 정사각형 공간..

👩🏻‍💻문제설명 [이코테 Ch3-4] 1이 될 때까지 (그리디) 어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. (N이 K로 나누어떨어질 때만 선택가능) 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이경우 전체과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오. 입력조건 첫째줄에 ..

👩🏻‍💻문제링크 [백준 10835] 카드게임 (Python) (맞왜틀) ✍️Idea Sketch 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다. 백준을 풀면서 "맞았습니다!"가 아니라 "**점" 점수를 매겨주는 문제는 이 문제가 처음이다. 문제를 풀면서 맞왜틀을 정말 많이 외쳤다. 다이나믹 프로그래밍 Top-down 방식으로 구현했다. 당신이 31점이라면 - 메모이제이션 없이 구현했을 것이고 당신이 64점이라면이라면 - sys.setrecursionlimi..

👩🏻‍💻문제링크 [백준 2798] 블랙잭 (Python) ✍️Idea Sketch 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. 처음에 삼중 for문을 쓰면 구현은 되겠군 했다가, 성능이 별로일 것 같은데.. 설마 삼중 for문을 쓸까? 하는 생각에 백트래킹(dfs)을 써서 풀었다. 다른 분들의 코드를 확인한 결과, 삼중 for문으로 구현한 코드가 매우 많았다. (채점 시간도 내 것보다 짧았다..) 백트래킹 연습문제인 N과 M (2) 문제를 응용하면 쉽다. 전체적인 흐름은 다음과 같다. dfs()에서 플레이어는 모든 카드를 순차적으로 확인하며 고를지 말지 결정한..

👩🏻‍💻문제링크 [백준 9093] 단어 뒤집기 (Python) ✍️Idea Sketch 문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다. 큰 흐름은 다음과 같다. sys.stdin.realine()으로 입력값을 받는다. 파이썬 슬라이스로 array[::-1] 단어를 뒤집어 출력한다. 보다 구체적으로 살펴보면 👩🏻‍💻 input() vs sys.stdin.readline() 차이점 1 input()은 파라미터로 prompt message를 받는다. prompt message는 사용자의 명령을 받아들을 준비가 되었음을 나타내는 메시지다. sys.stdin.readline()는 prompt message를 파..

👩🏻‍💻문제링크 [백준 15686] 치킨 배달 (Python) ✍️Idea Sketch 2021-08-10 1. 출력값 분석하기 치킨거리 : 집과 가장 가까운 치킨집 사이의 거리 집 (x1, y1), 치킨집 (x2, y2) 일 때, 치킨거리는 |x1-x2| + |y1-y2| 이다. 도시의 치킨거리 : 모든 치킨거리의 합 도시의 치킨거리의 최솟값은? 2. 입력값 분석하기 도시의 크기는 n*n 이다. 치킨집은 m개 빼고 다 폐업할 예정이다. 0은 빈칸이다. 1은 집이다. 2는 치킨집이다. 3. 로직 살펴보기 치킨집이 5개고, m이 2인 경우 치킨집 5개 중에 2개를 고르는 모든 조합을 combinations 로 구한다. city_length()에서 치킨거리 min_length 와 도시의 치킨거리 total을..

👩🏻‍💻문제링크 [백준 16234] 인구 이동 (Python) ✍️Idea Sketch 2021-08-09 1. 이번 문제는 80% 에서 시간 초과가 발생해 애를 먹은 문제다. Python3에는 약 1000회의 재귀 제한이 있다. PyPy3는 재귀 제한 횟수가 더 커서 통과할 수 있었다. import sys sys.setrecursionlimit(10**6) 2. BFS와 DFS DFS, BFS 둘 중 어느 것을 해도 상관없지만 BFS로 구현한 사례가 많다. 이번에 DFS로 구현해봤는데 재귀 제한으로 애를 많이 먹었다. 다시 이 문제를 본다면 BFS로 구현해볼 것. 3. 로직 이해하기 로직 이해에 많은 도움이 된 마이구미님 블로그 dfs(x, y) : 상하좌우 인접한 나라와 인구 차이를 확인한다. fla..

👩🏻‍💻문제링크 [백준 14891] 톱니바퀴 (Python) ✍️Idea Sketch 2021-08-09 1. 문제 이해하기 톱니바퀴는 한 칸 이동을 기준으로, K번 회전한다. 시계 or 반시계방향으로 회전한다. A가 회전하기 전 B와 극이 다른 경우, B는 A와 반대 방향으로 회전한다. B와 극이 같은 경우, B는 회전하지 않는다. 2. 입력값 살펴보기 12시부터 시계방향 0은 N극, 1은 S극 회전 횟수 K 회전할 톱니바퀴 번호(num) 및 회전방향 1은 시계방향 -1는 반시계방향 3. 재귀적 로직 예제1 참고) 톱니바퀴 3을 반시계방향으로 회전시켜보자. 톱니바퀴 3과 오른쪽으로 인접한 톱니바퀴 4를 살펴보자. recursion() graph[3][2]와 graph[4][6]의 두 극이 다른 경우, ..