본문 바로가기
728x90
반응형

전체 글648

코로나 걸림 코로나 생긴지가 벌써 2년반정도 됐는데 이제와서 처음 걸렸다;; 사람을 잘 안만나서 그런가 암튼 걸림 첫날엔 두통이랑 몸살만 있었다 그냥 감기몸살인거 아닌가 싶을정도.. 둘쨋날부터는 목이 아프기 시작했다 목에 물엿같은게 껴있는느낌 이 물엿같은거 때문에 목소리도 이상하게 갈라지고 너무 아픔.. 침 삼킬때도 지옥을 맛보게됨 그리고 잘 때마다 너무 추워서 달달달달 떨면서 이불 뒤집어쓰고 잤다 근데 신기한게;;너무 추운데 온몸에 땀이 남;; 너무 찝찝하다~ 아프니까 죽 시켜먹었다 본죽에서 특새우죽,전복내장죽,전복죽,김치낙지죽 시켜먹었다ㅋㅋ 평소엔 죽 배달시켜먹으면 뭔가 돈 아까운 느낌이라 안시켜먹었는데 이번 기회에 먹고싶은거 다 시켜먹었다 이참에 게임도함 폴가이즈 우승 한번 하려고 하루죙일 하고 자면서도 폴가이.. 2022. 8. 24.
허브딜 꽃 키우기;; 오늘 낮에 베란다에 햇빛이 너무 잘 들길래 한번 찍어봤다 바질도 잘 자라고있고 아보카도가 말도안되게 잘 자라고있는게 보인다 허브딜 꽃은 어떻게됐을까? 생생하던 허브딜 (1개월 전) 어느날 허브딜 물 갈아주려고 꺼내봤는데 뿌리가.. 마늘쫑조림처럼.. 뭔가 요리 한것 처럼 이상하게 변해있었다 그래서 줄기를 또 잘라서 물에 담가놨다. 허브딜 결국엔 드라이플라워가 됐다 2022. 8. 18.
알고리즘 기출문제: 그리디2 볼링공 고르기 볼링공 개수n, 볼링공의 최대무게m이 주어지고 다음 줄에 각 볼링공의 무게가 주어진다 두 사람이 서로 다른 무게의 볼링공을 고르고자 할 때, 고를 수 있는 조합의 개수는? n,m=map(int,input().split()) balls=list(map(int,input().split())) result=0 for i in range(n-1): for j in range(i,n): if balls[i]!=balls[j]: result+=1 print(result) 2022. 8. 17.
알고리즘 기출문제: 그리디 1. 모험가 길드 n명의 모험가가 있다 각각의 모험가는 공포도가 있는데, 공포도가 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야 모험을 떠날 수 있다 최대 몇개의 모험가 그룹을 만들 수 있을까? n=int(input()) data=list(map(int,input().split())) data.sort() result=0 count=0 for i in data: count+=1 if count >= i: result+=1 count=0 print(result) 모험가를 한 명씩 데려와서 count를 세고 현재 모험가의 공포도보다 count가 크거나 같다면 result+=1, count는 초기화 한다 2. 곱하기 혹은 더하기 각 자리가 숫자로만 이루어진 문자열 S가 주어진다. 왼쪽부터 .. 2022. 8. 16.
백준 1806번: 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며.. 2022. 8. 15.
기타 알고리즘: 투 포인터 알고리즘, 구간 합 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다 투 포인터 알고리즘을 잘 활용할 수 있는 문제로는 '특정한 합을 가지는 부분 연속 수열 찾기' 가 있다 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 2. 현재 부분 합이 M과 같다면, 카운트한다. 3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다. 4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다. 5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. n=5 #데이터의 개수 5개 m=5 #찾고자 하는 부분합 m=5 data=[1,2,3,2,5] #전체 수열 count=0 interval_sum=0.. 2022. 8. 15.
엄청 큰 나무 오랜만에 달리기를 하려고 공원에 왔다 평소에도 자주 오던 공원인데 유독 오늘따라 나무가 커보인다 이 나무는 너무 커서 조금만 가까이 가도 새까만 나무의 형상이 하늘을 가리는데 그게 압도감이 느껴질 정도다 밑에서 올려다 보면 높은 만큼 많은 가지가 있고 이파리가 층층이 나있어서 꼭대기를 볼 수가 없다 웬만한 빌라 정도는 될 것 같은 키다 지금도 자라는 중인가 궁금하다 2022. 8. 15.
9. 기타 알고리즘: 소수 판별, 에라토스테네스의 체 알고리즘 소수: 1보다 큰 자연수 중에서 1과 자신을 제외한 자연수로는 나누어 떨어지지 않는 수 이걸 코드로 그대로 옮기면 def is_prime_number(x): for i in range(2,x): if x%i==0: return False return True 이렇게 간단하게 쓸 수 있다 숫자가 X일 때 시간복잡도는 O(X)가 된다 여기서 약수의 성질을 이용하면 시간복잡도를 줄일 수 있다 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다 예를 들어 16의 약수는 1, 2, 4, 8, 16인데, 1*16=16, 2*8=16으로, 4를 기준으로 대칭이다 따라서 특정한 자연수의 모든 약수를 찾을 때, 가운데 약수(제곱근)까지만 확인하면 된다 이것을 소수판별 알고리즘에 적용시키면 import m.. 2022. 8. 14.
백준 13023번: ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다. 둘째.. 2022. 8. 13.
이웃사람들 길바닥에서 꽃 발견함 주워서 사진찍음 요즘 너무 더워서 나갈 때 얼음물 챙겨 가야 함 안 챙기고 가다가 더워서 죽음 도서관에서 너무 화가 나는 일이 있었다. 도서관 중앙에 테이블이 하나 있는데 거기 고등학생 커플이 마주앉아 있었고 자꾸 둘이 장난치고 떠들었어;; 시끄럽게 속닥속닥 하다가 실실 쪼개는거임;;.. 갑자기 폰 꺼내서 지들끼리 서로 쳐 찍고 난리 치더니만 또 속닥속닥 쳐 얘기하고 있는 꼬락서니를 보고있으니 진짜 내 속 안에 있는 악마가 꺠어날 뻔;;~ 2022. 8. 11.
백준 1922번: 네트워크 연결 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용.. 2022. 8. 11.
백준 1520번: 내리막 길 (dp, dfs) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 입력 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다. 출력 첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다... 2022. 8. 10.
2623번: 음악프로그램 (위상정렬) https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다. 그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD.. 2022. 8. 10.
백준 14567번: 선수과목 (위상정렬) https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 문제 올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 .. 2022. 8. 9.
8. 기타 그래프 알고리즘 예제 3문제 (팀 결성, 도시 분할 계획, 커리큘럼) 팀 결성(union - find) n명의 학생이 있다 두 학생의 팀을 합치는 연산과 두 학생의 같은 팀 여부를 확인하는 연산이 있다 입력받아서 연산하고~ 같은팀 여부 확인 연산은 같은팀일 시 Yes, 아닐 시 No 출력 import sys input=sys.stdin.readline def find_parent(parent,x): if parent[x]!=x: parent[x]=find_parent(parent,parent[x]) else: return parent[x] def union_parent(parent,a,b): a=find_parent(parent,a) b=find_parent(parent,b) if a 2022. 8. 9.
개미와의 조우 저번에 바질에 에프킬라 뿌린 이후 이제 바질이 어느정도 잘 자라고 있어서 상했던 이파리를 다 떼주기로 했다 상한 부분이 투명하게 변했다 뒤에 손 갖다대면 손이 보일정도로 진짜 투명해짐... 근데 앞에 뭔가 검정색이 왔다갔다 하는게 느껴짐 개미가 바질이파리에서 피서 즐기는중 더듬이 이래저래 흔들면서 잘 다닌다 보고있으면 개미도 좀 귀여운듯? 더듬이 움직이는게 귀엽다 이건 딴얘기긴한데 토끼 귀도 약간 더듬이같이생겨서 귀여운거같다 토끼를 위에서보면 달팽이를 보는거같아서 위에서 보는거 좋아함 아 근데 개미는 진딧물이랑 친구다 그래서 개미는 집에 들이는게 아닌데.. 귀여운 개미 근데 개미가 원래 날개가 있었나? 2022. 8. 9.
오늘은 휴관 평화로운 월요일 오전 헬스장 가서 깔짝 하고 도서관 가는길 길에 사람도 없다 다 어디갔나? 직장인들은 출근했다 치고 방학한 초중고대딩들은 어디로? 아스팔트 바닥에 뜬금없이 구멍이 나있다 물빠지라고 뚫어놓은건가 저기로 가면 왠지 위험할것같아서 빙 둘러갔다 땀 뻘~뻘 흘리면서 20분 걸어서 도서관 도착 ........... 눈물이 앞을 가린다 사실 눈물은 아니고 땀이 앞을 가린다 이마에서 흐른 땀이 머리카락을 타고 내려와서 눈에 떨어짐 진짜로 근데 이까지 노트북 둘러메고 땀 뻘~뻘 흘리면서 왔는데 집 가긴 좀 그래서... 가까운 스타벅스로.. 출발 가는길에 뭐가 만개했길래 찍었다 뭔진 모르겠는데 폭죽같이 생겨서 신기하다 멀리서 보면 꽃인지도 잘 안보이고 눈에 안 띄는데 가까이서 보니까 예쁘다 가는길에 미리 .. 2022. 8. 8.
이끼 키우기 어제까지만 해도 평화롭던 식물존 오늘 갑자기 무슨일이?? 아뿔싸 귀찮아서 물도 잘 안갈아주고 물에 빛 들어오는것도 막아야하는데 귀찮아서 그냥 뒀더니만 물에서 무언가가 자라고있다 식물과 대화가 필요할 것 같다 ..... 다 씻어내고 은박지로 싸줌 2022. 8. 8.
8. 기타 그래프 이론: 위상 정렬 위상정렬은 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는'것임 사이클이 없는 방향그래프(DAG:Direct Acycle Graph) 에서 위상정렬 하는 방법 설명. 1. 진입차수가 0인 노드를 큐에 넣는다 2. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 이것을 큐가 빌 때까지 반복한다 만약 그래프에 사이클이 존재한다면.. 사이클에 포함되는 노드는 진입차수가 모두 1이상이 되므로 큐에 들어가지 못하고 정렬이 끝날것이다 from collections import deque v,e=map(int,input().split()) indegree=[0]*(v+1) graph=[[]for i in range(v+1)] for i in range(e): a,b=ma.. 2022. 8. 8.
8. 기타 그래프 이론: 크루스칼 알고리즘 크루스칼 알고리즘 최소 신장 트리를 찾는 알고리즘 최소 신장 트리는 사이클이 존재하지 않고 모든 노드가 연결되어 있어야 함 모든 도시가 연결되어야 하고 도로 건설 비용을 최소화 해야할 때 크루스칼 알고리즘을 사용하면.. 도로를 짓는 데 필요한 최소 비용을 계산할 수 있다 먼저 간선의 정보를 입력받는다(노드1,노드2,비용) 비용에 대하여 오름차순으로 정렬한다 비용이 적게 드는 순으로 노드1,노드2가 사이클이 아니라면(부모 노드가 같지 않다면) 노드 1,2를 union연산을 수행하고, 노드1,2의 부모노드가 같다면 무시한다 동그라미 안 숫자는 각 간선의 비용에 대하여 오름차순으로 번호를 매긴 것이고, 그래프에서 빨간 선은 연결된 것, 파란 선은 연결하지 않고 무시한 것이다 def find_parent(par.. 2022. 8. 8.
728x90
반응형

티스토리툴바