유진's 공부로그

문제 설명 https://programmers.co.kr/learn/courses/30/lessons/12946 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr n개의 원판을 i번째 기둥에서 j번째 기둥까지 옮기는 방법을 구하는 문제이다. 위의 프로그래머스 문제에서는 n개의 원판을 첫번째 기둥에서 세번째 기둥으로 옮기는 방법을 구하는 문제로 출제되었음. 하노이의 탑은 재귀로 풀이 가능한 전형적인 문제. 문제 접근 처음에 패턴을 파악해서 재귀로 연관지을 수 있는지가 포인트. 또한, 어디로..

문제 설명 여섯 가지 괄호 '(', ')', '{', '}', '[', ']'로 이루어진 문자열이 바르게 닫힌 문자열인지 체크. 바르게 닫힌 문자열이란 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로, '[' 문자로 열렸으면 ']' 문자로, '{' 문자로 열렸으면 '}' 문자로 닫히는 문자열을 의미함. - 제대로 닫히지 않은 문자열 예시: ((]], ([)] - 제대로 닫힌 문자열 예시: [[(())]]{} 문자열 s가 주어졌을 때, 문자열 s가 바르게 닫힌 문자열일 경우 True를 그렇지 않으면 False를 리턴하는 코드를 작성할 것. 단, 문자열 s의 길이는 1 이상 40이하이며 문자열 s는 위의 6개 괄호 문자로만 이루어짐. 문제 접근 전형적인 스택 풀이 문제이다. 문자열 s를 처음부터 훑으면..

문제 https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 문제 요구 조건 가로 길이가 n으로 주어지고, 세로 길이는 2로 고정되어 있다. 세로를 2로 고정하기 때문에 고려할 사항은 가로 길이뿐이다. 따라서 가로 n을 어떻게 채울 것인가에 대해 생각하면 된다. 그렇게 되면 두 가지 선택지가 있다. 직사각형 모양 타일을 세로로 쌓거나 혹은 가로로 쌓거나이다. 즉, 1과 2를 사용해서 n을 잘 채우면 된다..

문제 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제 요구 조건 그래프의 연결성분 찾기 문제 요건 분석 그래프의 경우 무향 그래프임. 입력으로 주어지는 그래프가 인접행렬로 구현되어 있기 때문에, 인접리스트로 구현할 시 (defaultdict에 넣어주는 형태로) 무향 그래프임에도 불구하고 노드를 뒤바꿔 추가해주는 작업을 하지 않아도 됨. 그래프 탐색이기 때문에 dfs를 통해 구현함. 연결성분의 개수를..

문제 설명 N*N 숫자 입력과 지운 숫자가 들어가있는 nums 배열이 있다고 했을 때 총 몇 개의 빙고가 발생(?)하는지를 리턴하는 문제 나의 풀이 시간 초과 발생. def solution(board, nums): answer = 0 n = len(board) for row in range(n): for col in range(n): if board[row][col] in nums: board[row][col] = 0 # 오른쪽으로 이동 (horizontal 빙고) for i in range(n): for j in range(n-1): if board[i][j] != board[i][j+1]: break else: answer += 1 # 아래로 이동 (vertical 빙고) for i in range(..

문제 설명 m x n 크기인 사무실이 있습니다. 사무실에는 전염병에 걸린 직원이 있는데, 이 직원은 매일 상하좌우로 병을 퍼트려 다른 직원을 감염시킵니다. 단, 백신을 접종한 직원은 면역력이 있어 감염되지 않습니다. 예를 들어 2x4 크기 사무실에서, 병에 걸린 직원의 위치가 (1,4), (2,2)이고 백신을 맞은 직원의 위치가 (1,2)입니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기 까지는 이틀이 소요됩니다. 사무실의 크기 m, n과 병에 걸린 직원의 위치 infests, 백신을 맞은 직원의 위치 vaccinateds가 매개변수로 주어집니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기까지 며칠이 걸리는지 return 하는 solution 함수를 완성해주세요. 제한 사..

https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문제 풀이 입력 문자열의 길이가 최대 1000이었으므로 완전 탐색이 가능할 것으로 생각함. 따라서 망설임 없이 loop를 두 번 타는 걸 생각했다. → O(n^2) 풀이 압축률이 가장 높은 단위에서의 압축된 문자열의 길이를 반환해야 하기 때문에, 단위를 1부터 전체 문자열 길이까지 설정하고 각 단위에서 단위 문자열의 중복 개수를 찾아야 한다. 로직은 간단..

문제 설명 각 캐릭터는 보스몹을 잡기 위해 아이템을 사용해서 공격력을 높일 수 있음. 아이템을 사용하면 공격력이 올라가는 대신 체력이 감소함. 캐릭터는 아이템을 사용해서 공격력을 증가시키되 최소 체력은 100 이상을 유지해야 함. 이 상황에서 팀 내 공격력을 최대화하기 위해 사용 가능한 아이템 수를 구하여라. 입력 입력으로는 1) 각 캐릭터의 잔여 체력, 2) 아이템을 사용하며 증가하는 공격력 & 소모되는 체력 이 주어짐. e.g.) healths = [100,200,300] // items = [[30, 20], [100, 50]] 제한 사항 healths의 길이는 1 이상 10,000 이하 healths의 원소는 1이상 1,000,000 이하인 자연수 items의 길이는 1 이상 5,000 이하 아이..

FloodFill과 그래프 탐색 floodfill 같은 경우엔 주어진 시작점으로부터 연결된 영역의 크기를 구하는 문제이다. (하나의 알고리즘으로 분류되는 듯하다) 프로그래머스 스터디에 참가하면서 floodfill 이라는 문제를 오래 붙잡고 있었는데, 이런 문제는 쉽게 접근하자면 모든 점마다 bfs, dfs를 수행하면서 영역 별로 "조져주는" 것이 해결책임을 알아냈다! 한 번의 탐색만으로는 수행이 불가능하다. (모든 정점을 한 번씩만 방문하는 걸로는 해결이 안된다는 의미) 처음에는 dfs 풀이만을 생각해냈는데, 한 번의 dfs만으로 풀이하려 했기에 해당 풀이도 오류가 떴다 (당시엔 몰랐음 ㅎㅎ... 컴퓨터는 죄가 없다. 코드를 짜는 나에게 있다 죄는 ^^). bfs로는 도저히 어떻게 푸는 건지 감이 안와서..

https://school.programmers.co.kr/tryouts/32181/challenges 문제의 핵심은 주어진 skill이 skill_trees 내 skill_tree에 올바른 순서로 들어가있는가이다. skill의 subsequence만 들어가도 무방하다. 문제에서 주어진 배열의 길이를 보았을 때 시간 복잡도를 고려할 만한 문제는 아님을 판단할 수 있어야 한다. 그리고 문제 요구 사항을 보고 어떤 자료구조를 사용할 것인지에 대한 감이 빨리 와야 할 것 같다. 나의 첫 풀이 def solution(skill, skill_trees): """ skill_trees 탐색하되...skill의 순서가 어떻게 되는지 체크 """ answer = 0 for sk in skill_trees: sk = "..