유진'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(..