본문 바로가기

분류 전체보기132

최단 경로 개념 코딩 테스트에는 주로 '다익스트라'와 '플로이드 워셜'이 출제 된다. 둘다 방향이 있는 그래프이다. 주로 최단 경로 전체를 출력하는 문제보다는 단순히 최단 거리만을 출력하는 문제가 많다. 아래 설명에서 시간복잡도의 N는 노드의 개수, E는 간선의 개수를 나타낸다. 다익스트라 - 특정 노드에서 모든 노드까지의 최단 거리들을 구함 - 최단 거리 저장 자료 구조 : 특정 노드에 대한 리스트 사용 (1차원 벡터) - 시간 복잡도 : 리스트를 순회하는 알고리즘 = O(N^2) / 힙을 이용한 알고리즘 = O(ElogN) - 음의 간선이 없을 때 사용 가능 플로이드 워셜 - 모든 노드에서 모든 노드까지의 최단 거리들을 구함 - 최단 거리 저장 자료 구조 : 모든 노드에 대한 리스트 사용 (2차원 벡터) - 시간 복.. 2021. 1. 24.
백준 2178번 : 미로 탐색 문제 링크 : www.acmicpc.net/problem/2178 풀이에 참고한 링크 : www.acmicpc.net/board/view/12343 내 풀이(2021.1.24) : #include #include #include using namespace std; int map[101][101]; int N, M; int dy[4] = { -1,0,1,0 }; int dx[4] = { 0,-1,0,1 }; void show() { for (int i = 1; i 2021. 1. 24.
배민커넥트 자전거 배달 세부 후기 [본 글은 2020년 7월~12월 동안의 경험을 바탕으로, 2021년 1월에 처음 작성됐고 2022년 2월에 일부 바뀐 규정들을 반영하여 수정하였습니다.] 길거리에 하늘색 커다란 가방을 메고 자전거를 타는 20대 남성 분들을 종종 보게 되었다. 하늘색이라서 유난히 튀고 호기심이 들었는데 나중에 찾아보니, '배민커넥트'로 배달을 하는 사람들이었다. 유튜브로 배민커넥트 후기 영상들을 살펴보고 나도 할지말지 고민을 해보았고 재밌는 경험 하나 늘린다는 마인드로 하기로 결심을 했다. 전자계약서를 작성하고 배달 가방을 구입하였다. 배달 가방과 헬멧 등을 돈을 내고 빌릴 수도 있었지만 나는 헬멧이 이미 있기도 하고, 그냥 배달 가방만 구입을 했다. 업무에 익숙해지면 최저시급 정도 벌 수 있는데 돈도 벌고, 운동도 하.. 2021. 1. 24.
백준 17626번 : Four Squares 문제 링크 : www.acmicpc.net/problem/17626 내 풀이1(2021.1.22.) : #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; bool stop = false; int a, b, c, d; for (a = 0; a < 224; a++) { for (b = a; b < 224; b++) { for (c = b; c < 224; c++) { for (d = c; d < 224; d++) { if (a * a + b * b + c * c + d * d == n) { stop = true; break; } } if.. 2021. 1. 22.

티스토리툴바