일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- dp
- LCS
- 종만북
- Cloud Pub/Sub
- r
- 삼성SW역량테스트
- 우선순위 큐
- CI/CD
- REACT
- 시뮬레이션
- jpa
- 백준 1753번
- BFS
- JavaScript
- 접미사 배열
- 수학
- ICPC
- Air Table
- 삼성 SW 역량테스트
- 데이터 분석
- 이분탐색
- 다익스트라
- 생활코딩
- 그리디
- Bit
- Cloud Run
- 펜윅 트리
- 고속 푸리에 변환
- 다이나믹 프로그래밍
- 컴퓨터 구조
- Today
- Total
목록알고리즘/BOJ 문제 풀이 (51)
코딩스토리
www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 다음 주 알고리즘 학회의 주제가 그래프여서 한번 풀어보았다. 솔직한 마음으로는 가볍게 풀어보고 괜찮은 문제다 싶으면 미팅 때 내야겠다고 생각했는데.. 푸는데 2시간 걸렸다... 삼성 A형 문제라는데 아직 A형 따긴 멀었네.. 문제 자체가 어렵다기 보단 어떻게 구현해야 할지 생각하다 더 좋은 구현 방법이 자꾸 떠올라 계속해서 바꾸다 보니 오래 걸렸다. 문제의 퀄리티는 굉장히 좋은 것 같다. (다양한 알고리즘들이 사용됨!) ..
www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 다익스트라 알고리즘을 사용하여 해결할 수 있는 문제이다. 문제 분석 1. "목적지의 후보"들이 주어진다. 2. 목적지까지 반드시 "최단거리"로만 갈 것이다. 3. 반드시 "g와 h사이의 교차로"를 지나간다. 따라서 이 문제를 한 줄로 요약하면 다음과 같다. "목적지의 후보들 중 g와 h 사이의 간선을 반드시 지나가는 경로가 최단 경로인 정점들을 모두 찾아라!" 해결 방법 사실 문제를 보자마자 해결법이 떠올..
www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 알고리즘을 활용한 문제이다. 문제에서 확인해야 하는 조건들 1. 방향성이 없는 그래프 -> 무방향 그래프, 즉 양방향 그래프가 된다. (입력받을 때 처리) 2. 임의로 주어진 두 정점은 반드시 통과해야 한다. -> 두 정점을 거쳐서 가야함 3. 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동 가능 -> 각각의 중간 정점에 가서 새롭게 다익스트라..
www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라 알고리즘 관련 문제이다. 처음 봤을 때 어떻게 해야 할지 감은 잡혔으나 그걸 코드로 옮기는 게 너무 어려웠다.. 먼저 떠올렸던 해법은 1. 다익스트라를 통해 시작점부터 도착점까지 최단 거리를 구한다. 2. 최단 경로에 포함된 간선들을 모두 제거한다. 3. 다익스트라를 통해 거의 최단 경로를 구한다. 문제는 2번이였다. 최단 경로가 여러 개가 나올 수 있고, 그렇다면 그 ..
www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라를 활용한 문제이다. 문제 분석 기본적인 다익스트라 문제이다. 버스 비용이 다르다 -> 가중치가 다르다, 즉 다익스트라! 도시를 노드로, 버스 비용을 간선으로 바꾸어 그래프 문제로 모델링하면 된다. 이 문제의 특이한 점은 출력 조건이였다. 1. 출발 도시에서 도착 도시까지 가는데 드는 최소 비용 출력 2. 경로에 포함되어있는 도시의 개수 3. 도시 순서대로 출력 최소 비..