Leta Learns

문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 학기 중 알고리즘 수업 들을 때 그래프 과제에서 절망했던 경험이 있다.. ㅎ 그래프는 조금하면 익숙해진다고 하는데 난 아직 아니라서 천천히 많이 풀어보려고 한다. 이번 문제는 어렵진 않았는데 count 세는 부분을 dfs 함수 내부에 넣지 않는 게 중요한 것 같다. dfs 함수 내부에 넣었더니 지 멋대로 먼저 print돼서 애 좀 먹었다 :( import sys def dfs(v): visited..

문제 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 문제 알고리즘 분류에 '누적합'이라고 나와있는데 누적합으로 안 푼 바보가 여기 있다.. 최대로 끌 수 있는 객차 수를 하나하나 계산해서 단순합으로 넣으려고 하니까 코드도 복잡해지고 안 풀린 거였다. 2021.07.10 - [HUFS/HUFS 모각코 캠프] - [모각코] 210710 Today I Learned (단순합으로 시도한 코드) 단순합으로 하면 예제는 풀리긴 하는데 최대로 끌 수..

짜증나서 돌아버릴 것 같다. DP는 익숙하지 않아서 어렵다.. 테이블에 들어갈 요소 생각하고 점화식만 잘 세우면 되는데 그 두 개가 왜 이리 어려울까.. 다 풀고 나서 제출 돌려보니 런타임 에러가 났는데 최대로 끌 수 있는 객차의 수가 달라질 때를 고려하지 않아서 그런 것 같다. 단순합(dp[0]) 부분을 수정해줘야 하는데 어떤 방식으로 해야할 지 생각이 나지 않는다. #런타임 에러 코드 import sys n = int(sys.stdin.readline()) #기관차가 끌고 가던 객차의 수 people = [0] + list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline()) #소형기관차가 최대로 끌 수 있는 객차의 수 dp = ..

lambda : 익명함수 => 간결한 코드, 메모리 절약 def 함수이름(매개변수): return 결과 lambda 매개변수 : 결과 람다는 return 키워드 없이 자동으로 리턴. sort메소드와 함께 사용되는 경우 多 #특정 조건 정렬할 때 특정 조건 적용 가능 => lambda함수의 key인자 사용 cafe = [["카푸치노", 5000], ["아포가토", 6000], ["카페라떼", 4000], ["아메리카노", 3000]] cafe.sort(key = lambda x:x[1]) .sort(key = lambda x:x[1]) #x[1]의 값이 정렬의 기준 (key) => 가격을 기준으로 정렬 #다중 조건 cafe = [["카푸치노", 5000], ["아포가토", 5000], ["카페라떼", 40..

문제 https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 예제는 잘 돌아가는데 시간초과가 나서 며칠동안 고군분투했던 문제.. 그냥 문제가 귀여워서 재밌어 보이길래 시도한 건데 푼 사람도 많이 없어서 구글링해도 시간초과 해결하는 법을 찾을 수 없었다.. 같이 스터디하는 친구도 시간초과 났었는데 해결한 후 본인 알고리즘 설명해준 거 듣고 나도 비슷한 방식으로 접근해봤다. 우선, 당근 맛의 최댓값을 가지려면..

BFS (너비 우선 탐색) : 현재 정점과 인접한 정점들에 대해 우선적으로 탐색하는 방식 => 넓게(wide) 탐색. 큐(Queue)를 이용해서 구현. 방문한 정점에 대해 표시하지 않는 경우, 무한루프에 빠질 가능성 有 => 각 정점의 기 방문 여부 저장 (visited) 아래로 깊은 그래프에 대해 좋은 성능을 기대할 수 있다. ( -> 아래로 깊은 그래프에서 해가 중간에 있는 경우) BFS의 과정 BFS 시간 복잡도 (DFS와 동일) 시간 복잡도 (N: 노드 수, E: 에지 수) 인접 행렬로 표현된 그래프 => O(N^2) 인접 리스트로 표현된 그래프 => O(N+E) 희소 그래프 (Sparse Graph)의 경우, 인접리스트 사용이 유리 -> 그래프 내에 적은 숫자의 간선만을 가지는 그래프 DFS v..

문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 회의실 배정 문제를 제외하면 그리디는 처음 풀어본 것 같다. 정해진 틀이 있는 게 아니라 알고리즘 생각하고 구현하는 느낌이라서 풀면서 내가 지금 그리디로 잘 풀고 있는 게 맞나? 의문이 들었다. 가장 큰 동전부터 사용하기 위해서 입력받은 동전의 가치들을 역순으로 정렬한 후 for문을 사용하여 가능한 동전 수를 구하였다. 어쨌든 ..

내부에 필요한 input값들을 일일이 추가하여 사용자로부터 필요한 데이터들을 받아왔음. => 장고에서는 Form 기능 제공 (쉽고 빠르게 구현 가능) Form 장점 form 태그 내부에 input 태그들 자동 생성 is_valid() => 유효성 검사 fast forms.py (app 폴더 안에 생성하기) from django import forms from .models import Blog class BlogForm(forms.ModelForm): class Meta: model = Blog fields = ['title', 'writer', 'body', 'image'] => 블로그 모델(model = Blog)의 form 내부에 사용할 필드(컬럼)를 설정한 것. Meta 클래스 : 데이터에 대한 ..

static : 개발자가 준비하는 파일 media : 이용자들이 올리는 파일 settings.py (=> media 설정) MEDIA_ROOT = os.path.join(BASE_DIR, 'media') #이용자가 업로드한 파일을 모아두는 곳 MEDIA_URL = '/media/' urls.py (=> media 설정) from django.contrib import admin from django.urls import path, include # include 작업을 분리해서 앱의 urls.py로 넘겨준다 import blog.views #static, media 관련 내용 import from django.conf import settings from django.conf.urls.static imp..

그리디 알고리즘 공부 2021.06.29 - [HUFS/Algorithm] - Greedy Algorithm (그리디, 욕심쟁이 알고리즘) Greedy Algorithm (그리디, 욕심쟁이 알고리즘) 1. Greedy Algorithm : 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 Greedy 알고리즘은 최적해를 구하는 상황에서 사용하는 방법이다. 여러 경우 중 하나를 선택할 때 그 상황에서 가장 좋다고 letalearns.tistory.com 예제는 맞는데 시간 초과가 난다. 이중 for문을 사용해서 그런 것으로 추정되는데 이중 for문 안 쓰고 푸는 방법이 도무지 생각나지 않는다. 코드 길이라도 줄여보려고 다른 방식으로 코드를 하나 더 작성했으나 이것도 이중 for문을 사용해서인지 시간 초과..