비트마스킹 연습하기1(백준 25166,12833)

1. 문제 25166번: 배고픈 아리의 샌드위치 구매하기 (acmicpc.net) 25166번: 배고픈 아리의 샌드위치 구매하기 "두리"라는 나라가 있다. 이 나라에서 사용되는 동전은 1원, 2원, 4원, 8원, 16원, 32원, 64원, 128원, 256원, 512원짜리 이렇게 총 10가지이다. 이 나라의 국민인 아리는 10가지의 동전을 각각 1개씩 총 10 www.acmicpc.net 1,2,4,8,16,32,64,128,256,512원짜리 동전만 사용가능할때, 이들을 하나씩 가지고 있는데, 친구에게 돈을 빌려서라도 샌드위치 가격만큼 내줄 수 있는지 아닌지 알아보는 문제 2. 풀이 브론즈1인데.. 어렵다.. 비트마스킹 이론 공부 했는데 뭔가 응용하기가 어렵다고 해야하나..? 연습좀 많이 해봐야겠지 이..

• format_list_bulleted 비트마스킹
• · 2022. 10. 30.
• textsms

재귀함수 연습하기1(백준 17478 1769)

1. 문제 17478번: 재귀함수가 뭔가요? (acmicpc.net) 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 출력 예시를 보고, 재귀함수로 똑같이 출력하는 문제 2. 풀이 from sys import stdin def chatbot(n,s1,s2,s3,s4,s5,s6): if n == 0: print(s1) print(s6) print(s5) else: print(s1) print(s2) print(s3) print(s4) chatbot(n-1,'____'+s1,'____'+s2,'____'+s3,'..

• format_list_bulleted 재귀 연습장
• · 2022. 10. 30.
• textsms

다이나믹 프로그래밍 - 2차원 배열 목적지까지 이동하는 방법의 수를 구하는 방법(파이프 옮기기)

1. 문제 17070번: 파이프 옮기기 1 (acmicpc.net) 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 17069번: 파이프 옮기기 2 (acmicpc.net) 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net n*n에서 조건에 맞게 (0,0)에서 시작해서 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 10. 27.
• textsms

회의실 배정 문제 응용하기 -모든 수업을 가능하게 하는 회의실의 수는-

1. 문제 11000번: 강의실 배정 (acmicpc.net) 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si = 현재 종료시간"이면 하나의 회의실에서 가능하다는 알고리즘으로 해결했다 근데 이 문제는 모든 수업을 가능하게 하는 최소의 회의실 수를 구해야한다 어떻게 하냐면 시작시간이 빠른 순서대로 오름차순 정렬한다 먼저 가..

• format_list_bulleted 그리디 알고리즘
• · 2022. 10. 18.
• textsms

우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median

1. 개요 수열이 계속 변화할때, 이 수열의 중앙값을 어떻게 빠르게 구할 수 있을까 매번 정렬해서 중간의 값을 찾아야하는가? 최대 힙과 최소 힙을 이용하면 중앙값을 아주 쉽게 찾을 수 있다 결론부터 말하자면, (크기와는 무관하게) 항의 순서대로 수열이 주어질때 최대힙에 들어간 원소의 수와 최소힙에 들어간 원소의 수가 서로 같을 때는 최대힙에 수를 넣어주고 최대힙의 원소의 수가 최소힙의 원소의 수보다 1개 더 많을때는 최소힙에 수를 넣어준다 즉 항상 최대힙 > 최소힙 > 최대힙 > 최소힙 >.. 으로 번갈아가면서 수를 넣어준다. 힙은 완벽하게 정렬해주지는 않지만, 루트에는 최소힙이면 힙에 들어간 원소들 중 최솟값이, 최대힙이면 힙에 들어간 원소들 중 최댓값이 온다는건 확실하다 최대힙에 원소를 넣으면 최대힙..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2022. 10. 18.
• textsms

다익스트라 알고리즘에서 실제 최단 경로 구하기

1. 실제 최단 경로 역추적 지금까지 다익스트라 알고리즘에선 최단 경로로 가는데 걸리는 가중치의 합을 구해왔는데, 실제 최단 경로가 궁금할 수도 있다 어떻게 하면 구할 수 있을까? 결론부터 말하자면 경로를 역추적해서 구한다 어떤 정점 A에서 목적지 B로 가는데, "A,C,D,E,F,G,B로 가는게 최단 경로다" 이렇게 순방향으로 구하지 않고, 다익스트라 알고리즘에서 테이블에서 최단 거리를 가진 정점 u를 선택할때, u와 인접한 정점 b를 선택하는데, b의 거리가 테이블에서 갱신될때 "b와 가장 가까운 정점이 u이다"라고 테이블에 저장을 해놓는다 모든 과정이 종료되면 목적지 B와 가장 가까운 정점이 G이고, G와 가장 가까운 정점이 F이고 F와 가장 가까운 정점이 E이고, ... C와 가장 가까운 정점이 ..

• format_list_bulleted 최단거리 알고리즘
• · 2022. 10. 10.
• textsms