[문제 요약] 선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 skill트리 개수를 return하는 solution 함수를 작성해주세요. 스킬은 알파벳 대문자로 표기 스킬 순서와 스킬트리는 문자열로 표기 skill의 길이는 1-26, 중복된 스킬 없음 skill_trees는 길이 1-20의 배열이며, 그 원소는 길이가 2 이상 26 이하인 중복 없는 문자열 [내 풀이] def available(skill, tree): arr = [-1] * len(skill) for i, s in enumerate(skill): for j, t in enumerate(tree): if t==s: if i==0 or -1
알고리즘
문제 개요 사람들 t번 사람은 t분에 자신이 가고싶은 편의점과 최단거리에 있는 베이스캠프에 들어감 가장 가까운 베캠이 여러개이면 행이 작은 곳으로 , 행이 같으면 열이 작은 곳으로 들어감 베이스캠프에 들어가는 데에는 시간이 소유되지 않음 베이스캠프에 사람이 들어가면 그 이후로 다른 사람들은 해당 베이스캠프를 지나갈 수 없음 격자에 있는 사람들이 모두 이동하고 해당 칸을 지날 수 없음 가고 싶은 편의점 방향을 향해서 1칸 움직임 최단거리로 움직임 상, 좌, 우, 하 순으로 움직임 편의점 도착 해당 편의점에서 멈춤 다른 사람들은 해당 편의점을 지나갈 수 없음 격자에 있는 사람들이 모두 이동하고 해당 칸을 지나갈 수 없게 됨 문제를 위와 같이 정리할 수 있다. 풀이과정, 방향 함수는 들어갈 베이스캠프 결정/사..
문제 개요 공격자 가장 약한 포탑 가장 낮은 공격력 가장 최근에 공격 행과 열의 합이 큰 포탑 열 값이 큰 포탑 순으로 선정 공격력이 전체 행+전체 열만큼 늘어남 타겟 포탑 가장 강한 포탑 가장 높은 공격력 가장 예전에 공격 행과 열의 합이 작은 포탑 열 값이 작은 포탑 공격자 선정 기준의 반대 공격 레이저 공격 상하좌우 4개 방향 포탑이 있는 경로로만 이동 가장자리에서 반대쪽으로 나옴 우 하 좌 상 순서로 경로 결정 경로에 있는 포탑은 공격력//2 만큼 감소, 타겟은 공격력 만큼 감소 포탄 공격 공격 대상은 공격력만큼 감소, 그 주변 8방향 내의 포탑은 공격력//2만큼 감소 가장자리에 포탄이 떨어지면 반대편 격자에 영향을 미침 포탑 부서짐 공격력 0 이하이면 포탑이 부서짐 포탑 정비 공격 이후, 부서지..
문제 개요 미로 M*M 격자 미로 종류 빈칸(참가자 이동 가능) 벽(1-9의 내구도, 회전 시 내구도가 1씩 깎이고 0이 되면 빈칸이 됨) 출구(참가자 도달 시 탈출) 회전 참가자 이동 후 회전 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형 크기가 같다면 좌상단 r좌표가 작은 것, 그 후엔 c좌표가 작은 것이 우선 선택된 정사각형은 시계방향으로 90도 회전, 회전된 벽은 내구도가 1씩 깎임 참가자(M명) 상하좌우, 벽이 없는 곳으로 이동 움직인 칸은 현재 칸보다 출구에 가까워야 함 움직일 수 없으면 움직이지 않음 한 칸에 여러 참가자 있을 수 있음 모든 참가자가 동시에 움직임 종료조건 모든 참가자가 탈출에 성공했을 때 K초가 지났을 때 모든 참가자들의 이동 거리 합과 출구 좌표를 출력하기 문제..
재귀는 스스로의 함수 또는 매소드를 호출하는 방식이다. DFS는 그래프 형태 자료구조에서 모든 정점을 탐색할 수 있는 알고리즘 중 하나이다. 깊이를 우선적으로 탐색하기 때문에 재귀 또는 스택을 이용한다. 백트래킹은 재귀를 통해 알고리즘을 푸는 기법 중 하나로 가지치기를 통해 탐색을 하다가 유망하지 않으면 추가 탐색을 하지 않고 다른 해를 찾는 방법이다. DFS와 백트래킹 모두 재귀를 이용하는 하나의 방식으로 이해하면 되며, DFS는 기본적으로 모든 노드를 탐색하는 것이 목적이고, 백트래킹은 불필요한 탐색이라고 판단되면 탐색을 중지하고 다른 노드에 대해 탐색하는 것이다. 상황에 따라서 DFS와 백트래킹 기법을 혼용할 수 있다. 🔹 즉, DFS와 백트래킹은 유사한 부분이 있으며 기본적으로 사용 목적이 다르지..
공통점: 주어진 문제를 작게 쪼개서 하위문제로 해결하고 연계적으로 큰 문제를 해결함 차이점 분할정복 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 사용 Top-Down만 가능 동적 프로그래밍 분할된 하위 문제가 동일하게 중복이 일어날 때 사용 Top Down, Bottom up 모두 가능
