본문 바로가기

분류 전체보기

 (328)
[백준] 3109번 : 빵집 안녕하세요. 오늘은 그래프 탐색 알고리즘 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 해당 문제는 깊이 우선탐색 + 그리디로 답을 도출 해낼 수 있습니다. 깊이우선탐색 : 한 위치에서 빵집까지를 갈 수 있는 경로를 탐색합니다. 1) 열이 위에서 아래 순서로 탐색해보는 조건 - 위에서 아래 순서로 탐색할때에는 우선순위를 오른쪽 대각선위 , 오른쪽, 오른쪽 대각선 아래 순서로 두어야 한다. R, C = map(int, input(..
[백준] 1700번 : 멀티탭 스케줄링 안녕하세요. 매일공부하는 개발자 빅광스입니다. 저번주는 다이나믹 프로그래밍 문제를 풀어보았는데요, 이번주는 그리디 알고리즘 문제를 풀어보려고 합니다. https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 오늘의 문제는 멀티탭 스케줄링 문제입니다. 문제의 내용은 위의 사이트에서 참고하시고 오세요. 저는 이 문제를 풀때 여러가지 테스트 케이스를 생각하면서 공책에 써가면서 최적해를 구하는 과정을 생각해보았습니다. 1) 현재 콘센트에 현재 넣으려는 아이템의..
파이썬 공간복잡도 안녕하세요. 오늘은 알고리즘 문제를 풀때 파이썬 공간복잡도를 어떻게 감을 잡아야 할지 알려드리겠습니다. 보통 코딩테스트의 경우 메모리 제한을 128MB ~ 512 MB로 제한을 둡니다. 코딩테스트 문제를 풀때에 대부분 리스트 자료구조를 사용하게 됩니다. int형의 리스트 자료구조는 리스트의 길이가 약 100만 일경우 4MB정도 차지합니다. 아래의 다음과 같이 내용을 정리 할 수 있겠습니다. 128MB일때 3200만개 256MB일때 6400만개 512MB일때 1억2800만개
파이썬 시간복잡도 안녕하세요. 알고리즘 문제를 풀때에 파이썬 시간복잡도 시간을 확인하는 방법을 알려드리겠습니다. 파이썬은 1초에 2000만 = 20,000,000 번 연산이 가능하다고 생각해두면 좋습니다. 따라서 시간제한이 1초, n = 100,000 (10만) 이라고 할 때 O(N^2) 으로 알고리즘을 짜게 되면 10,000,000,000 = 100억 번의 연산이 필요하므로, 시간초과가 나게 된다. 이 경우엔 O(NlogN) 으로 알고리즘을 짜야 1,600,000 번의 연산으로 문제를 해결해야합니다.
[백준] 2579번 : 계단오르기 안녕하세요. 매일 공부하는 개발자 빅광스입니다. 제가 아직 다이나믹프로그래밍이 익숙치 않아서 오늘도 또한 다이나믹 프로그래밍 문제를 풀도록 하겠습니다. https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단오르기 문제인데요, 자세한 내용은 링크를 타고 들어가서 문제를 확인 해보시기 바랍니다. 우리는 이 문제를 해결하기위하여 Sub Problem을 정의하고 메모리제이션 기법을 활용하여 이전에 올라왔던 계단위치의 합을 활용하여 시간 복잡도를 줄일 것 입니다. 우..
[백준] 1149번 : RGB거리 안녕하세요. 매일공부하는 개발자 빅광스입니다. 오늘은 다이나믹 프로그래밍 문제를 풀어보겠습니다. https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 먼저 저는 다이나믹 사고 능력이 아직 부족하여 모든 경우의 수를 다 따져보는 계산을 해보았습니다. dfs 탐색을 통하여 모든 경우를 다 방문하고 방문한 값을 저장하고 그 저장한 값들중 min 값을 구하여 정답을 도출하였습니다. char = ['R', 'G', 'B'] r = [] ..
[백준] 11726번 : 2xn 타일링 안녕하세요. 매일공부하는 개발자 빅광스입니다. 오늘은 다이나믹 프로그래밍의 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나..
[백준] 1339번 : 단어수학 안녕하세요. 개발자 빅광스 입니다. 오늘은 그리디 알고리즘 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개..

티스토리툴바