Leta Learns

#DFS 탐색 - 그래프 탐색 https://www.codetree.ai/missions/2/concepts/4/problems/graph-traversal/description 코드트리 삼성 SW역량테스트, 코드트리와 함께 www.codetree.ai import sys input = sys.stdin.readline def dfs(v): visited[v] = 1 for i in range(len(adjList[v])): w = adjList[v][i] if not visited[w]: dfs(w) n, m = map(int, input().split()) adjList = [[] for i in range(n+1)] visited = [0 for i in range(n+1)] for i in ran..

오일러 경로 (Eulerian Trail) : 그래프에 존재하는 모든 엣지를 1번씩만 방문하는 연속된 경로 if 시작점 == 도착점 : 오일러 회로 (Circuit) 별 모양 그래프 : 대표적인 오일러 회로 시작점이 어디든 모두 출발점으로 되돌아 온다. 모든 정점의 차수 : 2 (짝수) => 들어오는 간선이 있으면, 나가는 간선도 있어야 하므로 (시작점, 끝점 제외) => 항상 차수가 2의 배수 꼴로 붙는다. 무향그래프인 경우 차수(Degree)가 홀수인 정점이 2개 -> 오일러 경로 0개 -> 오일러 회로 오일러 회로가 존재한다면, 어떤 정점을 시작점으로 선택하든 오일러 경로를 만들 수 있다. 오일러 회로 구하기 현재 가장 널리 알려져있고, 가장 효율적인 알고리즘 : Hierholzer’s Algori..

첫 날에 백 작업을 거의 완료해두고 둘째 날에는 CSS 작업 위주로 진행했다. 1일 차 포스트에서 얘기했던 것처럼 CSS 할 여유 시간과 체력이 있어서 더 즐겁게 진행할 수 있었다. 1. NavBar, Footer 만들기 어쩌다보니 이 부분은 내가 도맡아서 했다. NavBar는 멋사 노션에 제공된 것을 사용하였다. download login logout 등 필요 없는 부분은 제외하고 로고와 서치 기능만 넣어주었다. Footer는 빌보드 홈페이지에 있는 검정 배경의 footer가 너무 맘에 들어서 그것과 비슷하게 했다. 플렉스를 넣고 Sharing, GitHub, Link 세 구역으로 나눈 다음 그 밑에 해당하는 링크들을 넣는 과정에서 어려움이 있었다. home.html에서는 링크들이 세로줄로 제대로 배열..

미니 해커톤 후 팀원 한 명과 토이 프로젝트를 하기로 했다. 개강 전에 미니 해커톤을 한 번 더 진행할 계획이 있다고 들어서 그 전에 조금이라도 더 실력을 키워놓고 싶었다. 주제 : billboard HOT 100 🔥 미니 해커톤때는 사실 CSS에 손도 안 댔어서 이번에는 CSS 열심히 하는 게 제1 목표였다. 두 번째 목표는 git 좀 더 능숙하게 사용해보기. 1. API 통신 장고 기본 세팅을 마치고 API 받아오는 작업을 했다. 미니 해커톤 때는 API 받아오는 작업을 팀원이 해서 이번 프로젝트에서는 이 작업을 내가 해보기로 했다. (팀원의 도움 하에.. ㅋㅋ) 우선, 모델을 먼저 정의해주었다. models.py from django.db import models # Create your model..

코드트리에서 구현 한 문제 풀었다. 사실 두 문제 시도했는데 하나는 못 풀었다. ㅎㅎ 구현 왤케 어렵지..? 정해진 알고리즘이 있는 게 아니라 그냥 내 생각을 코드로 짜는 거라서 더 어려운 것 같다. 연습 많이 하면 이것도 늘겠지..? 늘어야 할텐데.. 문제 #최고의 33위치 https://www.codetree.ai/missions/2/concepts/2/problems/best-place-of-33/description 코드트리 삼성 SW역량테스트, 코드트리와 함께 www.codetree.ai 근데 나 사실 완전 어거지로 풀었다 ;; 이렇게 풀어도 되는 건가ㅋㅋㅋ 하도 안 풀려서 그냥 패스라도 받자.. 코드 더러운 건 신경쓰지 말자.. 했더니 이 사태가 났다. three에 하나하나 다 넣어준 것 봐 ..

Segment Tree : 사용자가 요청한 쿼리에 대해서 더 빠르게 응답하기 위해 만들어진 자료구조. 특정 기준으로 트리를 전처리하여 연산 속도를 높이게 된다. 이진 트리 구조. 구간 트리라고도 불림. 배열로 구현 가능. 세그먼트 트리를 이루는 각 노드의 왼쪽 자식과 오른쪽 자식이 각각 해당 구간의 왼쪽 반과 오른쪽 반을 표현. => 이진 트리 구조 Segment Tree를 사용하는 이유 배열 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 있는 경우. arr[4] + arr[5] + arr[6] 의 부분합을 구하는 쿼리와 arr[4]의 값을 바꾸는 쿼리가 있다고 하면 보통의 방식에서 부분합을 구하는 쿼리는 O(N), 값을 바꾸는 쿼리는 O(1)의 시간복잡도를 요구한다. 이처럼 수..

문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 타임머신 문제와 비슷한 유형이다. 다른 점이라면 bf 함수에서 세번째 for문 안에 있는 if문을 돌릴 때, 타임머신에서는 아래의 if문을 사용하여 시작점과 연결된 경로가 있는지 확인해야 했고, if dist[a] != float('inf') and dist[next] > dist[a] + time: 웜홀 문제에서는 시작점이 주어지지 않으므로 이에 대한 확인 없이 negative..

문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만포드 코드에 문제가 있는데 모르겠어서 친구랑 스터디할 때 상의했다. for문을 세 번 돌려야 하는데 난 두 번만 돌려서 문제가 생겼다. for i in range(1, n+1) : 간선 탐색을 위한 for문 (아래 for문을 n번 반복) for a in range(1, n+1) : 노드 탐색을 위한 for문 (모든 엣지에 대해서..

ㅎ............ 벨만포드....... 모르겠어요......... 오늘 낮에 벨만포드 다른 문제 풀다가 안 풀려서 넘기고 이거 푼 건데 그 문제를 못 풀어서 그런가 이것도 못 풀겠다. 내 벨만포드 코드에 문제가 있나보다.. 뭐가 문제일까... 근데 이 문제는 테스트 케이스 여러 개 받아와야 해서 for문 안에서 모든 것을 처리해야 하는데 그걸 이해하는데 오래 걸렸다. 문제가 너무 길어서 읽기 싫게 생겼거든요.. 내일 다시 풀거나 다음 모각코 때 다시 풀어야지.... ㅠ import sys input = sys.stdin.readline def bf(start): dist[start] = 0 for i in range(1, n+1): for next, time in road[i]: if dist[i..

문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 어제 푼 다익스트라 코드 이용해서 조금만 손 봤더니 그냥 풀렸다.. 다익스트라 코드 외우면 이 문제 저 문제 풀기 수월하겠네. 외워야겠다. 시작점, 도착점만 입력 받아서 다익스트라 이용해서 dist 배열 구하고 변수(cost) 에 저장한 다음, 해당 배열의 도착점 인덱스 값을 출력해주면 된다. (cost[end]) import sys import heapq ..