본문 바로가기

알고리즘 풀이/백준43

[BOJ] 2448. 별 찍기 - 11 - JAVA 🔗 문제 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 재귀 재귀 연습 많이 해야 겠다... k = 0 ( 즉, N = 3) 일 떄는 기본 블록 * * * ***** 규칙을 찾으면 크게 2줄로 구분된다. 첫 번째 줄은 중앙에 한 개의 블록, 두 번째 줄은 빈칸을 사이에 둔 두 개의 블록 * * * ***** * * * * * * ***** ***** 두 번째 줄은 블록을 한 개 삽입하고, 빈칸 삽입하고, 블록 한 개 삽입 첫 번쨰 줄은 블록을 중앙에 놓기 위해 블.. 2022. 12. 16.
[BOJ] 1976. 여행 가자 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합 내가 푼 방법은 Floyd 를 사용한 것이었는데, 출발지와 도착지가 같다면 여행할 수 있다는 것을 생각해내지 못해서 틀렸다. 검색을 하다가 Floyd는 시간 복잡도가 O(N^3) 이고 대부분 Union-Find 를 사용해서 푼 것 같아 2가지 방법으로 풀었다. Floyd (메모리, 시간, 코드 길이 순서).. 2022. 12. 15.
[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.

티스토리툴바