분류 전체보기354

• 

  [프로그래머스] 퍼즐 조각 채우기 - 파이썬(python) 문제 설명 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다. 조각은 한 번에 하나씩 채워 넣습니다. 조각을 회전시킬 수 있습니다. 조각을 뒤집을 수는 없습니다. 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다. 다음은 퍼즐 조각을 채우는 예시입니다. 위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 .. 알고리즘/DFS, BFS 2022. 9. 23.

• 

  [프로그래머스] 아이템 줍기 - 파이썬(python) 문제 설명 다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다. 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다. 만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다. 단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다. 즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다. 다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다. 한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다. 지형을 나타내는 직사각형이 담긴 2차원 배.. 알고리즘/DFS, BFS 2022. 9. 22.

• [프로그래머스] 여행경로 - 파이썬(python) 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. [["ICN", "JFK"], ["HND", "IA.. 알고리즘/DFS, BFS 2022. 9. 22.

• 

  [프로그래머스] 단어 변환 - 파이썬(python) 나의 풀이 step = [] def dfs(begin, target, words, cnt): if begin == target : step.append(cnt) return for i in range(len(words)) : tmp = 0 for j in range(len(words[i])) : if begin[j] == words[i][j] : tmp += 1 if tmp == len(begin)-1 : lst = words[:] lst.remove(words[i]) dfs(words[i], target, lst, cnt+1) def solution(begin, target, words): dfs(begin, target, words, 0) if step == [] : return 0 else : st.. 알고리즘/DFS, BFS 2022. 9. 21.

• 

  [프로그래머스] 네트워크 - 파이썬(python) 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j].. 알고리즘/DFS, BFS 2022. 9. 20.

• 

  [프로그래머스] 게임 맵 최단거리 - 파이썬(python) 문제 설명 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째 방법은 11.. 알고리즘/DFS, BFS 2022. 9. 20.

• 

  [프로그래머스] 타겟 넘버 - 파이썬(python) 나의 풀이 a = 0 def dfs(i, result, numbers, target) : global a if i == len(numbers) : if result == target : a+=1 return else : dfs(i+1, result+numbers[i], numbers, target) dfs(i+1, result-numbers[i], numbers, target) def solution(numbers, target): result = 0 dfs(0, result, numbers, target) return a 위 그림처럼 i번째 숫자에 대해 +부호 or -부호를 붙여 계산하는 모든 경우의 수를 따져보면 된다. 즉, DFS 로 모든 경우에 대해 깊이 우선 탐색을 한다. 그리고, i가 마지막원.. 알고리즘/DFS, BFS 2022. 9. 20.

• 

  [프로그래머스] 사칙연산 - 파이썬(python) 나의 풀이 import math def solution(arr): N = math.ceil(len(arr) / 2) # dp[] 는 피연산자만 담아둔다 # 즉, dp[i][j] 는 i번째숫자~j번째숫자까지의 최대/최솟값이다 max_dp = [[float('-inf') for _ in range(N)] for _ in range(N)] min_dp = [[float('inf') for _ in range(N)] for _ in range(N)] for step in range(N) : # i~j 까지의 간격 for i in range(N-step) : j = i + step if step == 0 : # 간격이 0 일때는 자기자신이 최대/최소 max_dp[i][i] = int(arr[i*2]) min_dp.. 알고리즘/동적프로그래밍(DP) 2022. 9. 20.

• 

  인간실격 - 다자이 오사무 항상 문학 베스트셀러이길래 궁금증을 못참고 읽게되었다 책을 읽는 중간에는 작가가 어떤 삶을 살아왔길래 이렇게도 기괴(?)한 삶과 요조의 내면을 솔직하게 묘사하지 싶었다 그 솔직함에 나도 모르게 요조의 내면에 따라 감정이 동조되는 기분이 들 정도였으니깐... 그리고 당황스럽지만 그런 파격적이고 혐오스런 내용이 꽤나 마음에 들었다는 것이다 나도 요조에게 공감되는 것들이 꽤 많아서 그런 것일까? 뭔가 아직 충족되지 않은 기분에 유튜브와 구글링을 통해 다자이 오사무에 대해 찾아보았다 다자이 오사무의 대표작 《인간 실격》은 나쓰메 소세키의 《마음》과 더불어 일본 근대문학의 양대 소설로 평가받으며 현재까지 천만 부 이상 판매되었다. 수차례의 자살 시도 끝에 39세의 젊은 나이에 스스로 생을 마감한 다자이 오사무. .. 독서 2022. 9. 20.

• 

  [프로그래머스] 도둑질 - 파이썬(python) 나의 풀이 def solution(money): # 방법1. 맨 뒷 집을 제외한 경우 dp1 = [0]*len(money) dp1[0] = money[0] dp1[1] = max(money[0], money[1]) # 0,1번 집 중 더 돈이 많은 집 하나만 털 수 있음 for i in range(2,len(money)) : if i != len(money) - 1 : dp1[i] = max(dp1[i-2]+money[i], dp1[i-1]) else : dp1[i] = max(dp1[i-2]+0, dp1[i-1]) # 마지막집이 없다고 가정했으므로 dp[i] 는 i-2, i-1 중 더 큰 값이 된다. # 방법2. 맨 앞 집을 제외한 경우 dp2 = [0]*len(money) dp2[0] = 0 # 맨 .. 알고리즘/동적프로그래밍(DP) 2022. 9. 19.

• 

  [프로그래머스] 등굣길 - 파이썬(python) 나의 풀이 def solution(m, n, puddles): dp = [[0]*(m+1) for _ in range(n+1)] print(dp) for i in range(1, n+1) : for j in range(1, m+1) : if i == 1 and j == 1 : dp[i][j] = 1 elif [j,i] in puddles : dp[i][j] = 0 else : dp[i][j] = dp[i-1][j] + dp[i][j-1] # print("dp[{}][{}] = {}".format(i,j,dp[i][j])) return dp[n][m] % 1000000007 (1,1) 을 집으로, (n,m) 을 학교 좌표로 만들기 위해, 이차원 배열을 [n+1][m+1] 의 크기로 초기화한다. 이번 문제는.. 알고리즘/동적프로그래밍(DP) 2022. 9. 19.

• 

  [프로그래머스] 정수 삼각형 - 파이썬(python) 나의 풀이 def solution(triangle): d = triangle[:] for i in range(1, len(d)) : for j in range(0,i+1) : if j == 0 : d[i][j] += d[i-1][j] elif j == i : d[i][j] += d[i-1][i-1] else : d[i][j] += max(d[i-1][j-1], d[i-1][j]) return max(d[len(d)-1]) 전형적인 bottom up 동적프로그래밍 문제이다. dp[] 에는항상 dp[i][j] 까지의 최댓값 경로가 저장되어 있다. 따라서 dp[i][j] 를 구하려면, dp[i-1][j-1] 와 dp[i-1][j] 둘 중 더 큰값을 나의 값에 더해주면 된다. 만약 한 줄에서 첫번째 값(j=0).. 알고리즘/동적프로그래밍(DP) 2022. 9. 17.