일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- db
- Javascript
- QuerySetAPI
- Python
- 머신러닝종류
- react
- VITE
- PWA
- vitepwa
- 알고리즘
- SSAFY
- 리액트
- 데코레이터
- git
- 싸피10기
- Django
- queryset
- 셀프넘버
- TypeScript
- 싸피
- js
- sqld
- SSAFYcial
- unionfind
- 싸피셜
- 백준
- SQL
- 14658
- 플로이드워셜
- pwa적용하기
- Today
- Total
목록알고리즘 (7)
Meme's IT
백준 14658번 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 브루트포스, 라고는 나와있는데 구글링 했을 때랑 다르게 풀었음 K의 갯수가 100개 이하이므로 K기준으로 진행 12 10 4 7 2 4 7 3 3 1 5 6 4 7 12 10 8 6 해당 예제에서 별의 위치를 받고, 얘네를 우선 x기준으로 정렬을 해준다. [(2, 4), (3, 1), (4, 7), (5, 6), (7, 3), (8, 6), (12, 10)] 이런식으로 ..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 이름이 젤다길래 풀어봤는데 젤다는 안나오고 뭔 강도가... 문제 젤다가 (0, 0)의 위치에서 (N - 1, N - 1) 위치로 이동하는데 맵에는 강도가 있어서 강도가 있는 위치로 지나가면 일정 금액을 뜯긴다.... 그래서 최대한 덜 뜯기고 갔을 때, 잃은 돈을 출력해주기 풀이 다익스트라의 정석같은 문제였음.. 맵과 같은 크기의 리스트를 만든 후, 엄청 큰 값(inf)을 넣어둠 ..
# BFS https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 문제 개구리가 징검다리를 건너는데, 다리에는 각각 숫자가 써져있음 그 숫자의 배수만큼은 그냥 갈 수 있다. 출발지와 목적지가 주어졌을 때, 목적지까지 가는데 얼마나 걸리는지 구하기 ▶ 내가 지금 밟은 칸이 1이 되면 다 갈 수 있음 → 시간 무조건 1 ▶ 배수 만큼은 갈 수 있다고 했으니까 뒤로도 가능함 BFS방식으로 풀었다 풀이 from collections import ..
알고리즘이란? 문제 해결을 위한 절차나 방법 좋은 알고리즘이란 무엇인가 정확성: 얼마나 정확한지 작업량: 얼마나 적은 연산으로 결과를 내는지 메모리 사용량: 얼마나 적은 메모리를 사용하는지 단순성: 얼마나 단순한지 최적성: 개선할 여지가 없는지 시간 복잡도 실제 걸리는 시간을 측정, 실행되는 명령문의 개수를 계산해서 얻어낼 수 있음 빅 - 오 표기법 시간 복잡도 함수 중에서 가장 큰 영향을 주는 n에 대한 항만을 표시한 것 계수는 생략함 예: O(n) = O(3n)
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/AJACH/btsw6ZI5ZIr/kvS3xb2TTKj4Yt3reGNaJ0/img.png)
스택(Stack)이란? 영어 그대로 쌓아놓은 것이라고 생각하면 편함 스택의 핵심은 후입선출, 즉 가장 최근에 들어온 데이터가 가장 먼저 나감 스택의 연산 push: 삽입, 저장소에 자료를 저장 pop: 삭제, 저장소에서 자료를 꺼냄, 순서는 최근에 삽입한 자료 부터 isEmpty: 공백인지 아닌지를 확인 peek: 스택의 top에 있는 원소를 반환 스택의 구현 1. push def pop(): global top if top == -1: print('underflow') return 0 else: top = -1 return stack[top + 1] print(pop()) if top > -1: top -= 1 print(stack[top + 1]) 2. pop def pop(): global top ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bxzx3B/btsvatzfoqx/gF5zriUIV6ZD1go353vIP0/img.png)
# Union-Find #DFS 문제 창용 마을에는 N명의 사람이 살고 있다. 사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다. 두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수도 있다. 두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면, 모두 묶어서 하나의 무리라고 한다. 창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라. 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는 두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다. 이후 M개의 줄에 걸쳐서 서로를 알고 있는 두..