오뚝이개발자

문제설명 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요. 제한사항 스킬..

문제설명 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧..

문제 https://www.acmicpc.net/problem/9376 9376번: 탈옥 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 � www.acmicpc.net 생각의 흐름 사실 혼자 힘으로 풀지 못해 블로그를 많이 참고해서 구현하였다. 참고한 블로그는 https://rebas.kr/770이다. 위 블로그에 드러나지 않은 부분을 설명하겠다. bfs함수의 for문 안에서 '.'인 경우 appendleft를 해주고 '#'인 경우 그냥 append를 해주는데 이유는 '.'인 경우를 우선적으로 처리하도록 하기 위함이다. 왜냐하면 '.'와 연결된 경우는 문을 부수지 ..

문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 생각의 흐름 수빈이가 X에 있을 때 이동가능한 경우의 수는 X-1, X+1, 2X의 세가지이다. 가능한 경우는 이 세가지이므로 수빈이의 위치를 q에 넣고 이들을 pop하면서 BFS로 탐색을 해주면 된다. 이 때, pop을 했을 때 원소가 K와 같은 값이면 탐색을 종료한다. 방문을 체크하기 위해서는 visit이라는 1차원 리스트를 사용하였다. 리스트에는 ..

문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 생각의 흐름 메모리 제한이 심한 문제이다. 따라서 2차원 리스트 그대로를 이용해 문제를 풀기에는 무리가 있다. 메모리 제한을 해결하기 위해선 저장하는 방식을 바꾸어야 하는데 주어진 예시에서 0을 9로 바꿔주고 이를 int형으로 저장한다. 예를 들어 예제1의 경우 193425786이 된다. 위와 같이 저장하면 특정한 "상태"를 나타낼 수 있는데 이 상태에 대한 value 값으로 이동 횟수를 매칭시켜 저장해야 한다. 이를 위해 dictionary 구조를 사용한다. 즉, k..

문제 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. www.acmicpc.net 생각의 흐름 편의상 물통을 각각 x,y,z라고 하자. 물이 담겨 있는 것을 "특정한 상태"라고 바라보자. 그러면 이 특정상태는 x,y에 ..

문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 생각의 흐름 사실 이 문제는 브루트 포스 알고리즘이라기보단 백트래킹 알고리즘을 사용한다고 보는 것이 맞다. zero리스트에는 0의 위..

문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다. www.acmicpc.net 생각의 흐름 알파벳마다 중요도를 계산한다. 이 때, 중요도는 해당 알파벳이 등장하는 자릿값을 더해주는 것이다. 예를 들어, ABCDE가 주어졌다면 A의 중요도는 10000이 되는 것이다. 모든 알파벳의 중요도를 계산한 후 중요도가 큰 순서대로 9부터 순차적으로 할당해주면 된다. 깨달은 점 파이썬에서 아..