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

👩🏻‍💻문제설명 [이코테 Ch13-15] 특정 거리의 도시 찾기 (BFS) ✍️Idea Sketch 시간복잡도 그래프를 인접리스트로 구현한 경우 O(V + E)이다. BFS에서 모든 정점을 방문한다. 한 번 방문한 정점은 다시 방문하지 않는다. (V = vertex = 정점) BFS에서 한 정점을 방문할 때마다 간선으로 인접한 정점을 방문한다. 한 번 지나간 간선은 다시 지나가지 않는다. (E = edge = 간선) 따라서 그래프를 인접리스트로 구현한 경우, 시간복잡도는 O(V + E) 이다. 알고리즘 : BFS 도시의 최단 거리를 구해야 하는 문제이므로 BFS 알고리즘을 구현하면 된다. ✍️내 소스코드 graph 인접리스트를 만들고 bfs 함수를 실행한다. 배열 visited는 도시의 최단 거리를 저장..

👩🏻‍💻문제설명 [이코테 Ch13-18] 괄호 변환 (재귀) ✍️Idea Sketch 문제 요약 균형잡힌 괄호 문자열 : '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같은 경우 올바른 괄호 문자열 : 균형잡힌 괄호 문자열에서 '('와 ')'의 괄호의 짝도 모두 맞는 경우 목표 : 균형잡힌 괄호 문자열을 올바른 괄호 문자열로 변환하기 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 3-1. 수행한 결과..

👩🏻‍💻문제설명 [이코테 Ch12-14] 외벽 점검 (구현) ✍️Idea Sketch 문제 요약 외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요. weak : 반드시 방문해야하는 지점 dist : 한번에 이동할 수 있는 거리 제한사항 n은 1 이상 200 이하인 자연수 weak의 길이는 1 이상 15 이하 weak의 원소는 0 이상 n - 1 이하인 정수 dist의 길이는 1 이상 8 이하 dist의 원소는 1 이상 100 이하인 자연수 weak를 모두 방문할 수 없는 경우, return -..

👩🏻‍💻문제설명 [이코테 Ch12-13] 치킨 배달 (구현) ✍️Idea Sketch 문제 요약 치킨거리 : 집과 가장 가까운 치킨집과의 거리 도시의 치킨거리 : 치킨거리의 합 치킨집 m개만 남겨야 함 만들 수 있는 가장 작은 '도시의 치킨거리'는? 시간복잡도 참고사이트 이 문제는 n * n의 모든 그래프 영역을 탐색 할 필요가 없다. 집과 치킨집만 탐색하면 된다. 집은 2N개, 즉 최대 100개이며, 치킨집 M은 최대 13이다. 이는 시간 초과를 암시하는 연산횟수 1억과는 거리가 멀다. 따라서 브루트포스 알고리즘(완전 탐색)을 시도해봄직 하다. 그리고 치킨집 최대 13개 중에서 M개를 고르는 조합의 최대 경우의 수는 100,000에 가깝다. (M이 중간값 6, 7일 경우 100,000에 가깝다. ) 알..

👩🏻‍💻문제설명 [이코테 Ch12-10] 자물쇠와 열쇠 (구현) ✍️Idea Sketch 문제 요약 자물쇠와 회전, 이동이 가능한 열쇠가 있다. 목표 : 자물쇠의 모든 영역을 1로 채우기 = 자물쇠의 모든 홈을 채우기 열쇠 움직임 종류 회전 : 시계방향 90도 (90도 함수 하나 만으로 180도, 270도 동작 가능) 이동 : 상하좌우 1칸 중요 아이디어 : 자물쇠 배열 확장 시간복잡도 O(n^4), O(n^2 * m^2) 자물쇠와 열쇠의 최대 크기는 20 * 20으로, 시간 초과를 암시하는 연산횟수 1억과는 거리가 멀다. 따라서 브루트포스 알고리즘(완전 탐색)을 시도해봄직 하다. 이 문제는 자물쇠 배열을 3n * 3n으로 확장한 후, 가능한 모든 영역에 대해 열쇠 m * m 을 대조해봐야 한다. 따라서..

👩🏻‍💻문제설명 [이코테 Ch11-4] 만들 수 없는 금액 (그리디) 동네 편의점의 주인인 동빈이는 N개의 동전을 갖고 있다. 이 때 N개의 동전을 이용해 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성해라. 예를 들면, N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리 동전이라고 가정하자. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다. 또 다른 예시로, N = 3이고 각 동전이 각각 3원, 5원, 7원이면, 만들 수 없는 양의 정수 금액 중 최솟값은 1원이다. 입력조건 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다. (1

👩🏻‍💻문제설명 [이코테 Ch11-3] 문자열 뒤집기 (그리디) 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다. 다솜이 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다. 예를 들어 S = 0001100일 때는 다음과 같습니다. 전체를 뒤집으면 1110011이 된다. 4번째 문자무터 5번째 문자까지 뒤집으면 1111111이 되어서 두번만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4, 5번째 문자를 뒤집었으면 한번에 0000000이 되어서 1번만에 모두 같은 숫자로 만들 수 있습니다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오. 입력조건 첫째 줄에 ..

👩🏻‍💻문제설명 [이코테 Ch10-4] 커리큘럼 (Graph) 동빈이는 온라인으로 컴퓨터 공학 강의를 듣고 있다. 이 때 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 동빈이는 총 N개의 강의를 듣고자 한다. 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 예를 들어, N = 3일 때, 3번 강의의 선수 강의로 1번과 2번 강의가 이씨고, 1번과 2번 강의는 선수 강의가 없다고 하자. 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 하자. 1번 강의: 30시간 2번 강의: 20시간 3번 강의: 40시간 이 경우, 1번 강의를 수강하기까지의 최소 시간은 30시간, 2번 ..

👩🏻‍💻문제설명 [이코테 Ch8-5] 효율적인 화폐 구성 (DP) N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 회폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. 입력 조건 첫째 줄에 N, M이 주어진다. (1

👩🏻‍💻문제설명 [이코테 Ch7-2] 부품 찾기 (이진 탐색) 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N=5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M=3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력..