python

문제https://www.acmicpc.net/problem/21939백준 문제집 - 0x16강 - 이진 검색 트리 알고리즘: 이진 탐색 트리, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵, 우선순위 큐풀이명령어 recommend x에서 값을 선택하는 기준은 1) 난이도, 2) 문제번호 순이다.x의 값에 따라 최대/최소값을 선택해야 하므로 최대힙/최소힙을 각각 만들어준다.최대힙에는 (-난이도, -문제번호), 최소힙에는 (난이도, 문제번호)를 집어넣어 내림차순/오름차순 형태로 관리한다. 단, 힙에서 꺼낸 값이 이미 solved 된 문제일수도 있으므로 딕셔너리로 따로 체크해야한다.딕셔너리는 문제 번호: 난이도 형태로 구성, solved 된 문제일경우 딕셔너리에서 제거한다. 명령어별로 실행과정을 정리하..

문제https://www.acmicpc.net/problem/7662백준 문제집 - 0x16강 - 이진 검색 트리 알고리즘: 우선순위 큐풀이 단순하게 최대힙, 최소힙으로만 관리했다가 틀렸던 문제다.최대힙에서 추출했던 숫자가 최소힙에서는 아직 존재할수도 있으므로, 각 숫자의 상태(갯수)를 따로 저장해둬야한다. 입력이 I로 주어질경우 해당 숫자의 갯수를 +1 카운트.D일경우 명령어에 맞춰 최대/최소힙에서 숫자를 추출.만약 추출한 숫자의 갯수가 0인 상태라면 이미 전체 힙에서 제거된 상태이므로, 갯수가 0이 아닌 숫자를 찾을때까지 계속 추출한다.찾으면 1 감소시킨 후 해당 숫자를 출력하면 된다. 모든 과정이 끝나고나서 힙의 길이가 0이라면 "EMPTY"를, 남아있다면 최댓값, 최솟값을 추출한다.이때는 숫자의 ..

문제https://www.acmicpc.net/problem/1351백준 문제집 - 0x15강 - 해시 알고리즘: 해시를 사용한 집합과 맵, 다이나믹 프로그래밍풀이 피보나치와 비슷한 문제라고 생각하면 되겠다.A[0] = 1이니 임의의 값 A[N]을 N = 0이 될 때까지 식에 맞춰 쪼개면 된다. 💡참고로 ⌊ ⌋ 기호는 바닥함수(floor function)를 나타낸다.⌊x⌋ = x보다 작거나 같은 가장 큰 정수 를 의미한다.즉, ⌊i/P⌋ = i // P인 셈이다. 따라서 딕셔너리에 A[0] = 1을 미리 저장해주고, N이 0이 될때까지 아래의 과정을 반복한다.A[N]의 값이 딕셔너리에 존재한다면 그 값을 반환없다면 재귀를 통해 A[N] = A[N//P] + A[N//Q]의 값을 구하고 딕셔너리에 저장 ..

문제https://www.acmicpc.net/problem/20166백준 문제집 - 0x15강 - 해시 알고리즘: 해시를 사용한 집합과 맵, 깊이 우선 탐색(DFS), 그래프 탐색, 다이나믹 프로그래밍풀이 주의깊게 봐야 할 조건은 다음과 같다.방문했던 곳에 다시 방문 가능환형 구조로 이루어진 좌표조합이 아닌 순열 (순서가 다르면 다른것으로 계산)대각선 이동 가능또한 단어는 중복으로 주어질 수 있으므로, 딕셔너리에 이미 계산된 값이 있다면 탐색할 필요 없이 그 값을 출력해주면 된다.없다면 아래의 탐색 과정을 진행한다.단어의 첫 문자와 일치하는 좌표들을 리스트에 저장한다.만약 단어의 길이가 1이라면 리스트의 길이를 딕셔너리에 저장 후 출력.아니라면, 저장한 좌표를 하나씩 꺼내며 DFS를 진행한다. (단어,..

문제https://www.acmicpc.net/problem/19583백준 문제집 - 0x15강 - 해시 알고리즘: 문자열, 해시를 사용한 집합과 맵, 구현풀이 우선 입력 데이터가 정확히 몇 줄인지 주어지지 않으므로 받아올 때 주의해야한다. 사실 이 문제는 왜 굳이 해시로 분류되었는가...? 의문이 드는 문제다.어쨌든 파이썬을 사용한다면 set() 만으로도 충분하다. 먼저 입장용 set, 퇴장용 set을 각각 생성한다.그리고 채팅이 올라온 시간 time, 이름 name을 입력받는다.참고로 str 정렬과 int 정렬은 차이가 꽤 있다. 때문에 숫자 + (비교 or 정렬) 이 필요하다면 보통은 정수형으로 변환 후 사용하는것이 좋다.하지만 이 문제는 시간이 HH:MM 형태로 주어지므로 문자열 그대로 정렬해도 ..

문제https://www.acmicpc.net/problem/2461백준 문제집 - 0x14강 - 투 포인터 알고리즘: 투 포인터, 우선순위 큐, 정렬풀이투포인터만 사용하면 시간초과가 나는 문제다.Python3로 통과하기 위해선 우선순위 큐, 힙heapq을 사용해야한다. 우선 각 반의 능력치를 모두 오름차순 정렬한다.그리고 힙 리스트 heap에 각 반의 최솟값들을 (값, 반, 인덱스) 형태로 삽입한다.이 중 가장 큰 값은 따로 저장해둬야 한다.heap에서 최솟값을 꺼냄 => (값, 반, 인덱스)기존 결과값과 (최댓값 - 최솟값) 중 더 작은 값을 새로운 결과값으로 업데이트.인덱스를 1 증가시킴.해당 반에서 몇번째 값을 가리키는지 나타내는 포인터 역할즉, 현재까지의 가장 최솟값의 포인터를 뜻함.+1 처리 ..