본문 바로가기

알고리즘 풀이/백준43

[BOJ] 14725. 개미굴 - JAVA 문제 링크 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 풀이 문제 유형 : 트라이 * 트라이의 기본 코드에 대한 설명 : https://github.com/J00HUI/Algorithm-Codes/blob/master/trie.md 이 문제에서 기본 트라이 문제와 다르게 신경써야 할 점은 1. Map 내에 알파벳 순으로 정렬 2. 트라이 내의 원소들을 원하는 형태로 출력 이다. 먼저 1번은 HashMap 대신 TreeMap 을.. 2022. 6. 20.
[BOJ] 2631번. 줄 세우기 - JAVA 🌱 문제 링크 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 📝 풀이 과정 풀이 문제 유형 : DP 이 문제는 어린이들을 정렬해야 하는 문제이다. 중요한 건 이미 순서를 지키고 있는 어린이들은 옮길 필요가 없다. 예를 들어, 12435 순서대로 서있다면 1245 인 어린이들은 위치를 바꿀 필요가 없고 3 어린이만 위치를 바꾸면 된다. 이를 풀기 위해 필요한 개념이 LIS(Longest Increasing SubSequence) 알고리즘이다. 가장 긴.. 2022. 5. 5.
[BOJ] 17143번. 낚시왕 - JAVA 문제 링크 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 📝 풀이 과정 문제 유형 : 시뮬레이션 느낀 점 처음에 혼자 풀고 난 뒤 채점 현황을 보니 내것보다 메모리는 10000KB 적고 시간은 거의 5배가 적게 걸리게 푸신 분을 보고 어떻게 다른가 코드를 보고 난 뒤 다시 풀어봤다. 그리고 나서 다시 제출하니 거의 다가 비슷한 코드였는데 메모리와 소요 시간이 줄긴 했지만 실행시간은 여전히 3배 차이가 났다. 다시 한번 다른.. 2022. 4. 9.
[BOJ] 13460번. 구슬 탈출 2 🌱 문제 링크 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 📝 풀이 과정 문제 유형 : BFS 블로그의 힘을 빌려 어찌어찌 풀긴 했는데.. BFS로 접근할 생각을 못했다. (참조: https://sdesigner.tistory.com/105) 내가 했던 접근 방법은 경우의 수가 나눠지니 완탐으로 재귀를 사용해 턴 수를 매개변수로 주고 4방을 탐색해서 구슬이 갈 수 있다면 가고 다음 턴으로 넘.. 2022. 4. 8.
[BOJ] 15961번. 회전초밥 - JAVA 🌱 문제 링크 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 📝 풀이 과정 문제 유형 : 슬라이딩 윈도우 처음에는 K개씩 끊어서 일일이 갯수를 셌는데 역시나 시간초과가 났다. 그러다 슬라이딩 윈도우 방식으로 풀어야 시간초과가 나지 않는다는 것을 알게 되었다. 슬라이딩 윈도우 예를 들어 ABCDEF 가 있고 K가 3이라면, S1 = A+B+C, S2 = B+C+D, .... 이런식으로 구하지 않고, .. 2022. 4. 7.
[BOJ] 1194번. 달이 차오른다, 가자. -JAVA 🧷 문제 링크 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 📄 풀이 과정 블로그에서 BFS 의 활용 방법과 이 문제에 대해 정리된 것을 보았다. 가장 기초적인 방문체크는 해당 좌표에 이전에 방문한 적이 있는지 확인한다. 다음으로 많이 사용되는 것은 특정 시간에 해당 좌표를 방문한 적 있는가 이 문제에서는 특정 상태에 해당 좌표를 방문한 적 있는가 어떤 열쇠를 가지고 있는 상태에서 이 지점을 방문했는지 체크하는 .. 2022. 4. 6.

티스토리툴바