본문 바로가기

알고리즘 풀이56

[BOJ] 1241. 머리 톡톡 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1241 1241번: 머리 톡톡 엄지 생일 기념으로 학생들은 파티를 하고 있다. 엄지는 N(1≤N≤100,000)명의 학생에게 1부터 N번까지 차례대로 번호를 부여하였고 그들을 순서대로 빙 둘러앉아 원을 만들게 하였다. (즉 i번째 학 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 수학, 소수 판정 잘못된 방법) 완전 탐색으로 풀 경우 N개의 숫자가 차례로 N-1 (자신을 뺀 나머지) 개의 숫자를 탐색하면서 자신이 배수인지 확인한다면 시간 복잡도 O(N^2) N의 최댓값은 10만이므로 N^2 라면 100억, 1억당 1초가 걸린다면 소요 시간 10초 -> 제한 시간 2초를 초과 해결 방법) * 약수의 갯수만큼 머리 톡톡 하므로.. 2022. 12. 15.
[BOJ] 13460. 구슬탈출2 - JAVA 🔗 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : BFS, 구현, 시뮬레이션 문제를 보고 완전탐색 방법만 떠올랐다. 저번에 풀었던 문제였는데 그때도 똑같이 BFS 는 떠올리지 못했었던 것 같은데.. 관건은 최단경로탐색문제이니 BFS 떠올리기 여러 조건을 정확히 파악하고 로직을 짜기 기울인 횟수가 10 초과면 -1 출력 빨간 공, 파란 공 동시에 움직여야 됨.. 2022. 12. 14.
[BOJ] 2234. 성곽 - JAVA 🔗 문제 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 비트마스킹, BFS/DFS, 구현 방의 갯수와 최대 방의 넓이를 구하는 문제는 쉽게 구할 수 있었는데, 한 개의 벽을 부쉈을 때 최대 방의 넓이를 구하는 문제에서 많이 헤맸다.(몇 일을...) 이 문제를 통해 - 비트마스킹 복습 - 벽을 부수는 문제는 3차원 배열을 사용하는 경우만 봤었는데 인접한 두 개의 방을 합치면서 최대 값을 구하는 풀이 방식 을.. 2022. 12. 5.
[BOJ] 1593. 문자 해독 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1593 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net 🧩 풀이 및 코드 문제 요약 : 문자열 W, S 가 주어질 때, W의 순열이 S에 몇 번 포함되는지 갯수를 세 출력하는 문제 문제 유형 : 슬라이딩 윈도우 처음에 문제를 보고 생각난 풀이 방법은 완탐으로 W의 순열을 모두 구해서 순열 하나씩 S 에 포함되는지 슬라이딩 윈도우 기법을 사용해서 체크하는 것이었다. 그러다 순열을 모두 구할 필요 없이 W에 포함된 .. 2022. 7. 3.
[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.

티스토리툴바