일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 스택
- 백트래킹
- 백준
- dfs
- 그리디
- 프로그래머스
- 위상정렬
- CS
- 문자열
- 수학
- mst
- 시뮬레이션
- 에라토스테네스의 체
- BFS
- Kotlin
- JUnit 5
- Effective Java
- java
- 이분탐색
- Network
- 후니의 쉽게 쓴 시스코 네트워킹
- 구현
- 완전탐색
- 알고리즘
- 세그먼트 트리
- 투 포인터
- swea
- 동적계획법
- 플로이드-와샬
- 유니온 파인드
목록알고리즘 문제 풀이 (239)
반갑습니다!
2959번: 거북이 boj.kr 풀이 이 문제에서 4개의 정수로 직사각형을 만들어야한다. 예시로 들어온 1, 2, 3, 4를 생각해보면 거북이는 가로로 3과 4만큼 이동하고 세로로는 1과 2만큼 이동한다. 따라서 1 x 3의 직사각형이 된다. 즉, 작은 정수 2개, 큰 정수 2개가 각각 가로 / 세로가 된다. 따라서 정렬을 해준 뒤, 가로에서 작은 수 x 세로에서 작은 수를 구하면 된다. 코드 C++
12096번: boj.kr 풀이 이 문제는 알고리즘 문제는 아니다. 문제를 보면 전혀 감이 오질 않는다. 혹시나하는 마음에 페이시 소스를 살펴보면 몇 가지 힌트를 얻을 수 있다. 페이지 소스에는 총 4가지의 주석이 숨겨져 있다. 66y47KCc7J2YIOygleuLteydgA 7JWM66Ck7KSEIOyImCDsl4bri6Q 7ZWY7KeA66eMIO2ejO2KuOuKlCDsnojri6Q 7Z6M7Yq464qUIGh0dHBzOi8vc3RhcnRsaW5rLmlvLyDsl5Ag7J6I64qUIOOFiOOFjuOFguOFjg 각각의 주석을 Base64로 디코딩하게 되면 아래와 같은 힌트를 얻게 된다. 문제의 정답은 알려줄 수 없다 하지만 힌트는 있다 힌트는 https://startlink.io/ 에 있는 ㅈㅎ..
15663번: N과 M (9) boj.kr 풀이 엄청 많은 시리즈가 있는 문제이다. N개의 자연수 중에서 M개를 고르는 것은 백트래킹을 사용해서 어렵지 않게 구현할 수 있다. 하지만 이 문제에는 중복이 발생하기 때문에 중복을 제거해야한다. 아래의 코드에서는 set을 사용해서 중복을 제거했는데, 수열을 string으로 변환해서 set에 넣어주는 방식으로 구현했다. 또한 수열은 사전 순으로 출력해야하므로 맨 처음 입력받은 N개의 자연수를 정렬한 뒤 백트래킹했다. 코드 C++
5557번: 1학년 boj.kr 풀이 동적계획법으로 해결해야하는 문제이다. 문제를 읽고 단순하게 생각하면 DFS를 사용해서 해결할 수 있을 것 같지만, DFS를 사용하면 최대 O(2^100)의 복잡도를 가지기 때문에 시간초과가 발생한다. 따라서 다른 방법을 고민해봐야하는데, 문제에 중간에 나오는 수 모두 0 이상 20 이하라는 말이 나온다. 이 점을 이용해서 dp[숫자 인덱스][중간의 나오는 수]는 숫자 인덱스까지 수를 더했을 때 중간의 나오는 수가 될 수 있는 가지수를 구할 수 있다. 코드 C++