유진'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을 잘 채우면 된다..

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

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 (깊이 우선 탐색) 일단 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 ..

https://leetcode.com/problems/daily-temperatures/ 문제 설명 매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨가 될 때까지 며칠을 더 기다려야 하는지 리스트로 리턴하라. 문제 접근 및 풀이 [1st Try] - 투 포인터 1) 현재를 가리키는 포인터를 left, 미래를 가리키는 포인터를 right으로 설정. 2) 미래의 기온이 현재의 기온보다 높지 않다면 right 포인터를 한 칸 옮긴다. 3) 미래의 온도가 현재의 온도보다 높다면 결과가 되는 리스트에 right과 left의 차이를 append하고, left 포인터를 한 칸 이동, right 포인터를 left의 바로 다음 칸으로 이동시킨다. 4) left가 마지막에서 두번째 원소를 가리킬 때까지 반복한다...

https://leetcode.com/problems/remove-duplicate-letters/ 문제 설명 주어진 문자열에서 중복된 문자를 제외한 후 사전식 순서가 가장 작은 문자열을 리턴하라. (즉, 원래 문자열에서의 문자 순서를 완벽히 무시할 수는 없다는 뜻. 중복조합처럼 자리를 정해주는 식으로 생각하면 좀 더 수월할 듯하다) 문제 접근 및 풀이 [1st try] 1) 중복을 제거한다는 것은, 각 글자가 있을 자리를 정해준다는 것 → 원래 있던 자리를 무시하는 게 아님 2) 사전식 순서로 가장 작은 것을 리턴해야하는 것 → 쉽게 생각하면 가장 작은 글자 앞으로, 가장 큰 글자 뒤로 → 그러나 문제가 되는 점은 원래 문자열에서의 각 글자의 자리는 보존되어야 한다는 점 → 뚜렷한 자료구조는 생각나지 ..

https://leetcode.com/problems/valid-parentheses 문제 설명 괄호로 된 입력값이 올바른지 판별 (기본기 점검으로 좋은 문제) 문제 풀이 접근 1) 각 여는 괄호는 짝이 맞는 닫는 괄호가 있다 2) 닫는 괄호의 순서는 여는 괄호의 순서와 반대로 이루어져야 한다. 가장 마지막에 오는 여는 괄호는 가장 처음에 오는 닫는 괄호와 만나게 되고, 이런 패턴이 계속 반복된다. → 스택으로 접근 (LIFO) → 여는 괄호는 스택에 넣고, 닫는 괄호를 만나면 pop해서 짝이 맞는지 대조하는 방식 → 짝이 맞는지 대조하는 데에 편리한 자료구조는 딕셔너리 문제 풀이 class Solution: def isValid(self, s: str) -> bool: parentheses = { "(..