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..

# 백트래킹 해를 찾는 도중에 '막히면' (해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다. 결정 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'No'가 답하는 문제 미로 찾기, n-Queen 문제, 부분 집합의 합 등.. 정의를 보면 앞서 봤던 DFS-깊이 우선 탐색과 비슷한 것 같다. 미로 찾기 예를 통해서 어떤 차이가 있는지 알아보자. 미로 찾기 아래 그림과 같이 입구와 출구가 주어진 미로에서 입구부터 출구까지의 경로를 찾는 문제 이동할 수 있는 방향은 4가지로 제한된다. 내가 지나가는 경로를 스택에 저장해준 후 pop을 이용해 다시 경로를 되돌아 갈 수 있다. # 백트래킹과 깊이우선탐색의..

LIFO 구조의 Stack을 이용하여 계산기를 구현해보자. 여기서의 계산기는 중위 표기법(infix notation) (A+B)를 후위 표기법(postfix notation)(AB+)으로 변경하여 스택을 이용하여 계산한다. 중위 표기식의 후위 표기식 변환 방법 1 수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 다시 표현 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다. 괄호를 제거한다. 변환 알고리즘 2 (스택 이용) 입력받은 표기식에서 토큰을 읽는다. 토큰이 피연산자이면 토큰 출력 토큰이 괄호를 포함한 연산자일 때, 토큰이 스택의 TOP에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 PUSH 하고, 그렇지 않다면 스택 top의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지..

1ㄷ1 관계는 선형구조라고 불렀고 1ㄷN의 관계는 트리라고 불렀다. 그럼 N:N의 관계는 어떤 구조일까? 바로 그래프 구조라고 부른다. 비선형 구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요하다. 특히, 그래프와 비슷한 트리와의 큰 차이점은, 순환(Cycle) 할 수 있다는 것 이를 위한 탐색 방법 2가지가 있는데 오늘은 우선 DFS에 대해 알아볼 것이다. 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS) 두 방법의 차이 DFS는 탐색을 한 뒤 이전의 정점으로 돌아온다 이것은 백트래킹(Backtracking)이라고 부른다 # DFS - 깊이 우선 탐색 시작 정점의 한 방향으로 갈 수 있는 경로가 ..

앞에서 보았던 피보나치 수를 재귀 함수로 구하는 프로그램은 "엄청난 중복 호출" 이라는 큰 문제가 존재한다. 이를 해결하기 위해 동적 계획법의 핵심 기술인 memoization에 대해 먼저 알아보자 # memoization 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술 글자 그대로 해석하면 '메모리에 넣기 (to put in memorty)'라는 의미 앞서 구했던 fibo(n)의 값을 계산하자 마자 저장하면 O(2^n) 시간을 O(n)으로 줄일 수 있다. 이제 memoization을 활용한 Dynamic Programming에 대해서 알아보자 # DP(Dynamic Programming) 동적 계획 알고리즘은 그리..

문제 참고 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 키와 몸무게가 주어질 때 두 가지 모두 커야 덩치가 크다. 각각 리스트에 넣어준 후 for문을 이용해 모두 큰 경우에만 카운팅을 해주었다. 하지만 문제에서 원하는 결과는 '내가 몇번 째로 크냐'가 아닌 '나보다 큰 사람이 몇명인가' 였다. N = int(input()) height = [] # 키를 담을 리스트 weight = [] # 몸무게를 담을 리스트 cnt = N f..