BFS 너비우선탐색 (파이썬)
2022. 9. 2. 21:49
알고리즘 개념
BFS (너비 우선 탐색) BFS란? BFS는 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 인접한 정점들에 대해 탐색을 한 후, 다시 BFS를 진행해야 하므로 Queue를 사용 DFS와는 달리, 최고 깊이 까지 간 후 돌아오는 것이 아니라, 인접한 모든 정점을 차례대로 방문하고 그 다음 높이의 노드에 반복 그래프, 트리, 미로 등에서 활용가능함 BFS 코드 def bfs(v): # bfs 반복 코드 Q.append(v) # 일단, 시작점을 Q에 넣어준다. D[v] = 0 # D는 시작점 부터의 거리 visited[v] = 1 # visited 방문 해주고 while Q: # Q가 빈 리스트가 될 때 까지 v = Q..
Stack 스택 (파이썬)
2022. 9. 1. 23:00
알고리즘 개념
stack stack의 특성 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 구조이다. 저장된 자료는 1대1의 선형관계를 갖는다. 마지막에 삽입한 자료를 가장 먼저 꺼낸다. (후입선출) python에서는 list에 stack을 만든다. stack에 마지막 삽입한 자료의 위치를 top이라 부른다. push와 pop을 이용하여 자료를 삽입, 삭제한다. 참고 코드 stack = [0]*10 top = -1 for i in range(10): top += 1 stack[top] = i print(stack) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 주의할 점 삽입할 때 에는 stack이 다 차있는지 확인해야 한다. 삭제할 때 에는 stack이 비어있는지 확인해야 한다. (비어있을 때 삭제하려하면,..
Django DB 저장, 조회, 수정, 삭제 crud (장고)
2022. 9. 1. 12:36
Django 개념
저장 방법 1 article.title = 'value' article.content = 'vlaue' article.save() 방법2 article = Article(title='value', content='value') article.save() 방법3 Articel.objects.create(title='value', content='value') 조회 모두 조회 Article.objects.all() 하나만 조회 Article.objects.get(id=1).... 여러 값이 있으면 에러 get대신 filter를 쓰면 여러 값도 가져올 수 있음. filter에 대한 문법은 구글링 추천 수정 수정하기전에 무조건 조회해야됨 조회 : article = Article.objects.get(pk=n) ..
백준 1181 단어 정렬 sorted, lambda (파이썬)
2022. 8. 29. 21:14
백준
아이디어 그냥 정렬할 때 lambda 써보라고 만든 문제같다. 정렬할 때, key를 lambda로 주고, 선순위, 후순위를 만들면 될 것 같다. 풀이 및 해설(주석) import sys N = int(sys.stdin.readline()) arr = set() for i in range(N): # 중복된 원소가 들어가면 안되니까 set으로 넣어준다. arr.add(sys.stdin.readline().rstrip()) list(arr) result = sorted(arr, key=lambda x:(len(x), x)) # 정렬에 lambda사용, 1순위는 길이, 2순위는 알파벳순... for r in range(len(result)): sys.stdout.write(result[r]) # 처음 sys.s..
백준 1094 막대기 (파이썬)
2022. 8. 29. 16:57
백준
아이디어 일단, 문제를 이해하기가 어렵다. 대충 막대기를 반으로 짜르고 가지고 있는 막대의 길이의 합이 원하는 숫자가 나올 때, 막대기는 몇개냐 라고 해석함. 비트 연산자를 이용해 경우의 수를 가지고 해봤더니, 맞았다. 풀이 및 해설(주석) N = int(input()) # 일단 64길이의 막대가 있으니, 잘라서 만들 수 있는 막대기의 길이를 다 넣어줬다. stick = [64, 32, 32, 16, 16, 8, 8, 4, 4, 2, 2, 1, 1] for i in range(1
백준 2559 수열 (실행 시간 줄이기) (파이썬)
2022. 8. 28. 22:03
백준
풀이 및 해석(주석) import sys N, K = map(int, sys.stdin.readline().split()) tmp = list(map(int, sys.stdin.readline().split())) lst = [] lst.append(sum(tmp[:K])) # 미리 첫 번째 요소 부터 K번 까지의 수를 더해준 값을 lst에 넣어준다. result = -0xfffffff for i in range(0, N-K): lst.append(lst[i] - tmp[i] + tmp[K+i]) # 이 과정에서 sum을 이용하지 않고 lst의 i값과 # tmp의 인덱스를 조절 해서 뺴주고, 더해준다. lst.sort() print(lst[-1]) 후기 문제 자체는 쉽지만, 최적화 문제였다. 풀이의 핵심..
백준 10163 색종이 (파이썬)
2022. 8. 28. 19:54
백준
풀이 및 해석(주석) N = int(input()) info = [list(map(int, input().split())) for _ in range(N)] max_r = max_c = 0 for n in info: # 1000행, 1000열을 미리 만들기 싫어서 최대 행값과 열값을 뽑아준다. if (n[2]+n[0]) > max_c: max_c = (n[2]+n[0]) if (n[3]+n[1]) > max_r: max_r = (n[3]+n[1]) arr = [[0]*(max_c+1) for _ in range(max_r+1)] for s in range(N): r, c, w, h = info[s][0], info[s][1], info[s][2], info[s][3], for i in range(c, c..
SWEA 1289 원재의 메모리 복구하기 (파이썬)
2022. 8. 28. 15:28
SWEA
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 및 해석(주석) for tc in range(int(input())): memory = list(map(int, input())) N = len(memory) now = [0] * N # 초기의 메모리 (현재 메모리) cnt = 0 # 출력 값 for i in range(N): if memory[i] != now[i]: # 만들어야 할 메모리와 현재 메모리를 비교 cnt += 1 # 다르다면 ..