유진's 공부로그

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

소수를 대량으로 빠르게 찾는 알고리즘이다. 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수이다. 자연수 n이 소수인지 아닌지를 판별하기 위해서는 단순히 2부터 n-1까지 반복하면서 나누어 떨어지는지 확인하면 된다. 하나라도 나누어 떨어지는 수가 존재한다면 1과 자기자신을 제외한 수 중 약수를 갖게 되는 것이므로 n은 소수가 아니다. 위의 과정을 Python 코드로 표현하면, def is_prime_number(n): for i in range(2,n): # 2부터 n-1까지 if n % i == 0: # 하나라도 나누어 떨어지는 수가 있다면 return False # 소수가 아니다. return True 위의 방법은 직관적이지만 비효율적이라는 단점이 있다. 2부터 n-1까지 반복해야 하기..

문제 설명 여섯 가지 괄호 '(', ')', '{', '}', '[', ']'로 이루어진 문자열이 바르게 닫힌 문자열인지 체크. 바르게 닫힌 문자열이란 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로, '[' 문자로 열렸으면 ']' 문자로, '{' 문자로 열렸으면 '}' 문자로 닫히는 문자열을 의미함. - 제대로 닫히지 않은 문자열 예시: ((]], ([)] - 제대로 닫힌 문자열 예시: [[(())]]{} 문자열 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 함수를 완성해주세요. 제한 사..

문제 설명 각 캐릭터는 보스몹을 잡기 위해 아이템을 사용해서 공격력을 높일 수 있음. 아이템을 사용하면 공격력이 올라가는 대신 체력이 감소함. 캐릭터는 아이템을 사용해서 공격력을 증가시키되 최소 체력은 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로는 도저히 어떻게 푸는 건지 감이 안와서..

DFS(Depth-First Search; 깊이우선탐색)와 BFS(Breadth-First Search; 너비우선탐색)는 그래프의 정점을 방문하는 그래프 탐색(Graph Search or Graph traversal; 그래프 운행) 방법의 큰 갈래이다. 코딩 테스트 시에는 DFS를 좀 더 많이 활용하는 듯하다. DFS는 스택이나 재귀로, BFS는 큐로 구현한다. python에서 그래프는 아래와 같이 보통 딕셔너리를 활용해서 인접 리스트로 구현하는 경우가 많다. graph = { 1: [2,3,4], 2: [5], 3: [5], 4: [], ... } DFS (깊이 우선 탐색) 일단 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 ..