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

👩🏻‍💻문제설명 [이코테 Ch13-22] 블록 이동하기 (BFS) ✍️Idea Sketch 시간복잡도 O(NM) board를 탐색하는 BFS의 시간복잡도는 O(NM)이다. board의 가로 길이 * 세로 길이이다. 이 문제에서 board의 한 변의 길이는 100 이하이므로, 시간복잡도는 100 * 100 이하이다. 알고리즘 : BFS (1, 1)에 존재하는 로봇을 (N, N)으로 옮기는 최단 거리를 계산하는 문제이다. 문제요약 출발지 (1, 1)에 존재하는 로봇을 목적지 (N, N)으로 옮기는 최단 거리를 계산하라. 일반적인 BFS 문제와는 다르게, 출발지에서 로봇이 차지하고 있는 위치가 두 칸이다. 상하좌우 이동은 물론, 특정 조건에서 회전도 할 수 있다. 회전조건 1. 가로로 놓인 로봇이 아래로 회전..

👩🏻‍💻문제설명 [이코테 Ch14-25] 실패율 (정렬) ✍️Idea Sketch 문제요약 실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하라. 시간복잡도 스테이지의 개수 N은 500 이하이고, stages의 길이는 200,000 이하이다. 500 x 200,000는 1억이기 때문에 시간초과가 날 것이라 예상했다. 하지만 시간초과가 나지 않았다. 스테이지에 도달한 플레이어의 수가 0명인 경우, count()를 하지 않는다. 이 점 때문에 통과했다고 생각한다. a.count(x) 리스트 a에서 x가 몇개 있는지 count한다. count하기 위해 리스트 a를 전체 탐..

👩🏻‍💻문제설명 [이코테 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번 ..