https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 프로그래밍을 하며 '재귀'를 접하게 되면 가장 먼저 만나게 되는 문제라고 볼 수 있다. 그만큼 유명하고 재귀를 가장 잘 표현하였다고 생각이 드는 것이 '하노이의 탑'이라고 볼 수 있다. # 조건 세 개의 장대가 있고 첫 번째 장대에는 서로 크기가 다른 N개의 원판이 쌓여있다. 한 번에 한 개의 원판만 이동 가능하며 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. # 접근..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ## 조건 - 캠프 때 쓸 N개의 랜선을 만들어야 한다. - 이미 자체적으로 가지고 있는 K개의 랜선을 이용하여 N개 이상의 랜선을 만든다. - 항상 센티미터 단위로 정수 길이만큼 자르며, 만들 수 없는 경우는 없다. - 최대 랜선 길이를 구하여라 ## 접근방법 - 처음에는 평균값을 구한 후, -1씩 해주면서 주어진 개수를 만족시키는 값을 구하려고 하였지만 시간초과! ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LsaaqDzYDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 접근 방법 우선 제일 처음 빵이 만들어지기 전에 손님이 방문한다면 "Impossible" 출력과 동시에 끝내주었다. 또한 빵을 받아가는 사람 수가 처음 만든 빵의 개수보다 적다면 위의 조건 이후에 elif 조건문을 이용하여 "Possible" 출력을 해주며 끝내주었다. 이제 나머지 조건에 맞추어서 답을 내주면 되는데, 방문하는 사람을 "시간 초"로 표현하였기에 "시간"에 관점을 두고 풀이를 하였..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18LoAqItcCFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 접근 방법 제일 큰 행렬 속 작은 행렬들을 찾는 문제였다. 작은 행렬들을 찾아 개수와, 넓이 순으로 행과 열의 좌표를 출력하면 된다. 작은 행렬의 시작점과 끝점의 인덱스를 기록해주며 2중 for문으로 구현해보려 하였지만 쉽지 않았다. 역시나 이런 행렬 관련 문제는 델타 탐색과 4중 for문으로 먼저 접근하는 것이 빠르다는 것을 느낄 수 있었다. 또한, swea 등 제출 시 제출형식을 잘 맞춰야 ..

https://school.programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 접근 방법 주어진 조건에 맞게 함수를 완성시켜야한다. 같은 인형이 바구니에 들어온다면 터트려 주고 총 터진 인형의 수를 반환 해주는 문제이다. 2중 리스트이므로 전치행렬을 이용하여 구할수도 있지만, 나는 반복문 내에서 행과 열의 인덱스 번호를 반대로 적어주며 풀었다. 스택을 이용하여 LIFO 구조로 제일 위에 인형만 비교해주고 출고 시켜주었다. # 0은 빈칸 # 1~100은 각기 다른 인형 #..

https://school.programmers.co.kr/learn/courses/30/lessons/42840 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 접근 방법 1. 각 수포자의 정답 반복문을 리스트로 만든 후 answers 배열을 for문 통해 순회 2. 각 수포자의 길이의 나머지로 반환하게 되면 12345 12345와 같이 반복할 수 있다. 3. 답안지와 숫자가 일치하는 경우만 1씩 카운트 해주며 각자 맞춘 개수 기록 4. 제일 많이 맞춘 사람 도출 !! def solution(answers): answer = [] person = [0..

https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net # 조건 N개의 막대 기둥, 폭은 1m 높이는 다를 수 있음 지붕은 모두 연결되어야하고, 수평부분은 반드시 기둥의 윗면과 닿아야함 수직은 기둥의 옆면과 닿아야함 가장자리는 땅에 닿아야하고 지붕의 어떤 부분도 오목하게 들어가지 않는다. # 접근방법 1. 지붕의 어떤 부분도 오목하게 들어가지 않으므로 지금 높이의 지붕보다 낮은 기둥이 온다면 무시해도 된다. 2. 따라서 각 높이에 대한..

그래프를 탐색하는 방법에는 크게 두 가지가 있다. 깊이 우선 탐색(Depth First Search, DFS) 저번에 봤듯이 Stack 또는 재귀의 단계를 활용하여 구현 너비 우선 탐색(Breadth First Search, BFS) 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후, 방문헀던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐를 활용 순서 def BFS(G, v): # 그래프 G, 탐색 시작점 v visited = [0]*(n+1)# n: 정점의 개수 queue = [] # 큐 생성 queue.append(v) # 시작점 v를 큐에 삽입 while que..

분할 정복이란 말 그대로 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다. 정복(Conquer) : 나눈 작은 문제를 각각 해결한다. 통합(Combine): (필요하다면) 해결된 해답을 모은다. 거듭제곱을 통한 예제를 통하여 분할 정복을 알아보자. 기존의 함수를 구현한다면 O(n)의 시간 복잡도가 걸린다. def Power(Base, Exponent): if Base == 0: return 1 result = 1 # Base^0는 1이므로 for i in range(Exponent): result *= Base return result 분할 정복 기반 알고리즘을 통한다면 O(log 2 n)의 시간 복잡도가 걸리는데 어떻게 이렇게 될 수 있을까? 어떤 정수 C^8 = C x C x C..