본문 바로가기
728x90

분류 전체보기651

다이나믹 프로그래밍 이미 계산된 결과(작은 문제)는 별도의 메모리 공간에 저장해 둠으로써 중복 연산을 줄여 수행시간을 줄일 수 있다 다이나믹 프로그래밍을 사용할 수 있는 조건 1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다 2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결해야 함 다이나믹 프로그래밍 방식으로는 1. 탑다운(메모이제이션) 2. 보텀업 두가지가 있다. 탑다운 방식은 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이고, 보텀업 방식은 단순히 반복문을 이용하여 작은 문제부터 차근차근 답을 도출하는 방식이다. 탑다운 방식은 보통 재귀함수를 이용하는데, 재귀함수 깊이 제한 때문에 문제가 생길 수 있으므로 보텀업 방식을 권장한다. 고한다... 2022. 7. 19.
허브딜 꽃대가 올라옴 오늘 화분보는데 허브딜 꼭대기에 뭔 노란 덩어리가 생겼음 자세히보니까 꽃 필려고 하는거같음 허브딜 3월부터 키웠으니까 지금까지 한 4개월 넘음 잘자라다가 또 흐물흐물해졌다가 쪼그라들다가 어떤건 먹고 어떤건 갖다버리고 했는데 마지막남은 한마리가 꽃을 피게 생김 씨앗 심고 한달됐을때 사진인듯 이건 두달쯤 자란 사진이다. 이땐 아주 팔팔하게 잘 자람. 대나무같음. 근데 좀 휘청휘청함 잘자라는건 대나무처럼 잘자라는데 못자라는건 바닥을 기어감 그래서 몇개는 해먹고 몇개는 뽑고 하나는 물에다가 수경재배 하기로 했다 근데 뭔가 뿌리에 문제가 있었나봄 수경재배 시작한 애는 갑자기 팔팔해지고 흙에 계속 키우던애들은 다 말라서 죽음 그렇게 수경재배 한마리 빼고 허브딜 다 죽음 근데 어느날 공부하고 집 들어왔는데 잘자라던 .. 2022. 7. 18.
이진 탐색: 떡볶이 떡 만들기 떡을 자르기 위해 칼날의 높이를 설정해야 한다. 길이가 일정하지 않은 여러개의 떡이 있는데, 떡이 칼날 높이보다 높으면 잘린 만큼 떡을 가져갈 것이고 떡이 칼날 높이보다 낮으면 잘리지 않는다. 떡의개수n,필요한 떡의 총 길이m을 첫 줄에 입력받고 두번째 줄에서 떡의 개별 높이를 한 줄에 입력받는다. m만큼의 떡을 얻기 위해 최대한으로 높일 수 있는 칼날의 높이를 구하라. n,m=map(int,input().split()) #떡의개수n, 용청한 떡의길이m h=list(map(int,input().split())) #개별떡의길이 k=max(h)-1 #절단기 높이 초기값 for kal in range(k,0,-1): sum=0 for teok in h: if teok>kal: sum+=teok-kal if s.. 2022. 7. 18.
백준 2468번: 안전 영역 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정.. 2022. 7. 18.
백준 11724번: 연결요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤.. 2022. 7. 18.
백준 2583번: 영역 구하기 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 .. 2022. 7. 18.
백준 4963번: 섬의 개수 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테.. 2022. 7. 18.
백준 1987번: 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 .. 2022. 7. 17.
정렬 알고리즘: 이진 탐색 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법. (시작점, 끝점, 중간점 이용함) n, target = list(map(int,input().split())) #데이터개수와 찾을 값 array = list(map(int,input().split())) def binary_search(array, target, start, end): if start> end: return None mid = (start + end) // 2 #중간점 인덱스 if array[mid] == target: #타깃을 찾은 경우 return mid elif array[mid] > target:.. 2022. 7. 17.
백준 1946번: 신입사원 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지.. 2022. 7. 16.
정렬 알고리즘: 삽입 정렬 시간복잡도는 O(N^2) 정도.. 처리되지 않은 데이터를 하나씩 집어서.. 왼쪽으로 한 칸씩 이동하며 알맞은 위치에 삽입시키는거라고 보면 될듯. array = [7,5,9,0,3,1,6,2,4,8] for i in range(1,len(array)): for j in range(i,0,-1): if array[j] 2022. 7. 15.
정렬 알고리즘: 계수정렬 계수정렬.. 조건만 잘 맞으면 퀵정렬보다 빠른.. 그런 정렬.. 시간복잡도가 O(N+K)라고한다. N은 숫자개수 K는 최대숫자 근데 이게.. 숫자들이 일단 정수여야함 그리고 배열을 하나 더 만들기 때문에 공간복잡도가 높음. 어떻게하냐면.. 배열을 쭉 돌면서 어떤 숫자가 몇번 나왔는지를 다 카운트함 그러고나서 그냥 0부터 시작해서~최대값까지 각 숫자를 카운트만큼 출력해주면됨 array = [7,5,9,0,3,1,6,2,9,1,4,8,0,6,2] count=[0]*(max(array)+1) for i in range(len(array)): count[array[i]]+=1 #각 숫자가 나오는 횟수를 셈.. for i in range(len(count)): for j in range(count[i]): pri.. 2022. 7. 15.
정렬 알고리즘: 퀵 정렬 배열이 있을 때.. 1. 배열의 맨 앞에 있는 수를 pivot으로 설정한다 (피벗은 다른 수로 선택할 수도 있다는데 일단 난 맨 앞에걸로 하겠음) 2. 배열의 두 번째 수부터 오른쪽으로 진행하면서 pivot보다 큰 수를 찾는다 => 여기서 찾은 수의 인덱스를 left라고 하겠음 3. 배열의 끝부터 왼쪽으로 진행하면서 pivot보다 작은 수를 찾는다. => 여기서 찾은 수의 인덱스를 right라고 하겠음 4. 찾은 left와 right인덱스의 값을 서로 바꿈.. 근데~ 만약에 left가 right보다 오른쪽에있다?? 그러면 작은수랑 피벗이랑 바꿈.. 5. 이렇게되면 피벗을 기준으로 왼쪽엔 피벗보다 작은값, 오른쪽엔 피벗보다 큰값으로 대충 정리가 됨.. 그니까 피벗 기준으로 앞부분, 뒷부분을 또 퀵소트를 돌.. 2022. 7. 15.
정렬 알고리즘: 선택정렬 가장 작은 수를 찾아서 맨 앞이랑 바꾸고.. 그다음 또 작은수를 찾아서 맨앞으로 바꾸고... ' array=[7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_idx=i for j in range(i+1,len(array)): if array[min_idx]>array[j]: min_idx=j array[i],array[min_idx]=array[min_idx],array[i] print(array) i번째 값과 i+1 ~ 끝까지의 범위 중 가장작은 값을 골라 i번째 값과 가장작은 값을 스왑 함 2022. 7. 15.
백준 10026번: 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은.. 2022. 7. 15.
백준 1753번: 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작.. 2022. 7. 15.
레몬 키우기 시작함. 얼마전에 레몬 뭐 해먹고 씨앗 묻어뒀는데 새싹 자람. 허브들은 다 힘없이 흐물흐물한데 레몬은 새싹부터 아주 강하게생김. 빳빳함. 다이소에서 천원에 세개짜리 화분 사갖고와서 분갈이함. 근데 생각보다 레몬 잘자람. 천혜향은 진짜 느리게 자라는중인데 이건 맨날 볼때마다 더 커져있음 아침에보고 점심에보면 또 달라짐 저녁에보면 또 또달라짐 이거 키우는 맛이 쏠쏠할듯. 2022. 7. 14.
백준 1697번: 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의.. 2022. 7. 14.
백준 2667번: 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고.. 2022. 7. 14.
백준 7569번: 토마토 (3차원배열) https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 .. 2022. 7. 14.
728x90

티스토리툴바