빠르고 꾸준하게

자료구조 & 알고리즘/백준(Baekjoon)

[백준]11404(파이썬) - 플로이드

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이 문제는 제목을 읽으면 바로 떠오르는 풀이법이 하나 있죠. 바로 플로이드 워셜입니다. 플로이드 워셜은 다익스트라 알고리즘과 함께 최단거리를 계산하는 문제의 풀이법으로 유명한데요, 혹시 처음 들어보신분들은 아래 게시물을 한 번 읽고오시면 도움이 될 것 같습니다. 다익스트라 알고리즘(Dijkstra Algorithm)(feat.힙(heap)) 다익스트라 알고리즘 최단경로 알고리즘으로 특정 노드에서 ..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 15685(파이썬) - 드래곤 커브

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 이 문제는 뭔가 엄청 어려운 거 같았는데 엄청 어려웠던... 문제입니다. 하지만 그림을 그려보면서 문제를 읽다보니까 '규칙을 무조건 찾아야겠다'라는 생각이 들었습니다. 0,1,2,3의 방향을 가지고 규칙을 찾다보니 방향이 앞에 이전 세대의 정보를 뒤집어 거기에 1을 더해주면 됩니다. 4면 다시 처음인 0으로 돌려주면 됩니다. 이 구현은 4로 나눈 나머지로 계산해주면 됩니..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 16235(파이썬) - 나무 제테크

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 하라는 대로 하면 되는 삼성 기출문제 유형의 문제였지만, 시간 초과가 있어 상당히 까다로웠습니다. 처음에 푼 방식에서 테스트 케이스를 모두 통과했지만 시간 초과가 발생했고, 로직은 유지하면서 시간 초과를 어떻게 줄일 수 있을지 고민했습니다. 시간이 정말 오래걸렸는데요, 문제를 맞았을 때 쾌감이 어마어마했던 문제입니다. 먼저 하라는대로 하면 되는 구현 문제는 문제를 잘 읽어야 합니다..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 22116(파이썬) - 창영이와 퇴근

https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 이 문제를 보고 처음 든 생각은 '이분 탐색을 사용해야 하고, 그래프를 사용해야겠다'였습니다. 이분 탐색을 어떻게 구현해야 할지 생각하다가 일단 mid, 기준값을 문제에서 요구하는 최대 경사의 최솟값으로 정하고 문제를 풀었습니다. 처음에 DFS라고 생각하고 풀다가 오히려 시간이 더 오래걸릴 것 같아서 BFS로 풀었고, BFS개념에 이분탐색을 실행하면서 구하는 기준값, mid를 적용시켜주기만 하면 됩니다. *수정 : dfs로 구현을 성공했으나 제출했을 때 1000 * 1000 메모리 초과가 발생합니다. 친구의 설명을..