구현15 [백준 9328] 열쇠 / 자바 / bfs + 구현 #문제 레벨: G1알고리즘: bfs + 구현풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/9328#문제 풀이 이 문제에서 중요한 건 bfs가 아니다. 구현에 초점에 맞춰진 문제이다. 그냥 bfs로 탐색하면 지금은 못가더라도 나중에 키(소문자)를 획득하고 나서 갈 수 있는 곳은 어떻게 갈 것인가? 어떻게 구현할 것인가를 묻고 있다. 아이디어는 간단하다. 지금 열 수 없는 문은 나중에 열 수도 있으니 저장해둔다. 그리고 해당 키를 얻었을 때 열 수 있는 문을 다 열고 마저 탐색한다.나머지는 주석참고 바란다.#풀이 코드 import java.io.BufferedReader;import java.io.IOException;imp.. 2024. 9. 10. [백준 2261] 가장 가까운 두 점 / 자바 / 분할정복 or 라인스위핑 #문제 레벨: P2알고리즘: 분할정복, 라인스위핑풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2261#문제 풀이 이 문제는 디게 어렵다. 이분의 블로그를 보고 풀이를 이해했다. 이 분의 글을 보기 전에 이것만 기억해라. 아이디어는 간단하다(라인 스위핑 풀이에 관한). 직사각형을 생각하자. 우린 그 직사각형을 오른쪽으로 밀며 직사각형 안에 있는 점들끼리 비교할 것이다. 그러나 더 좋은 효율을 내기 위해 그 직사각형을 가로 혹은 세로를 점점 줄이면서 탐색하는 것이다. https://st-lab.tistory.com/256 [백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]https://www.acmicpc.net/pr.. 2024. 8. 29. [백준 16988] Baaaaaaaaaduk2 (Easy) / 자바 / 구현 + bfs #문제 레벨: G3알고리즘; bfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/16988#문제 풀이 문제를 보는 순간 규칙이 없고 완전탐색(브루트 포스)로 해결해야겠다고 생각이 들었다. 시간복잡도를 구해보자면 2개의 바둑돌을 놓는 경우의 수(400 C 2) X 상대 바둑돌을 잡아먹는 수 구하기(400) = 400 x 399 % 2 X 400 = 대략삼천 이백만 정도 되므로 가능한 경우의 수이다. 이제 구현할 차례이다. dfs를 돌며 바둑 돌을 놓는 구현은 0인 자리에만 놓고 dfs 재귀 깊이가 2인 함수를 구현하면 된다. 여기서 막혔다. 어떻게 함수를 구현해야 겹치치 않고 400 C 2를 구현할 수 있을까? 정답은 이중 for문을 돌며 .. 2024. 8. 18. [백준 14890] 경사로 / 자바 / 구현 #문제 레벨: G3알고리즘: 구현풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14890 #문제 풀이 문제를 보면 알겠지만 우리가 해야할 일은 명확하다. 모든 행을 검사하고 모든 열을 검사하면 된다. 그러나 조건이 많이 붙어있어 구현하는데 까다로울 수 있다. 해야 할 일이 명확하고 구현이 까다로운 경우는 밀고나가야한다. 이것은 구현문제이기 때문이다. dfs 혹은 bfs 혹은 dp 문제 같은 경우 해야 할 일이 명확하지는 않은데 구현이 지엽적인 것 같다고 느낄 때는 아이디어를 돌아볼 필요성이 있다.#풀이 코드 import java.util.*;import java.io.*;public class Main { static i.. 2024. 8. 6. [백준 15684] 사다리 조작 / 자바 / 브루트포스 + 약간의 구현 #문제 레벨: G3알고리즘: 브루트포스 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/15684#문제 풀이 난 문제를 볼 때 이것은 규칙이 있나 없나부터 가볍게 생각한다. 딱 떠오르지 않는다면 입출력 제한을 보고 완전탐색인지 확인한다. 이 문제 같은 경우 최대 (10x30)^3 사다리 구현은 어려울 수 있지만, 굳이 이 문제에서 한가지만 뽑아서 배울 수 있다면, 브루트 포스 문제 풀이 흐름이다.다리를 놓을 조합을 뽑아놓고(dfs로 구현) 조건에 맞는대로 결과가 나오는지 시뮬레이션 돌린다. #풀이 코드 import java.util.*;import java.io.*;public class Main { static in.. 2024. 8. 4. [백준 2504] 괄호의 값 / 자바 / 구현(괄호) #문제 레벨: G5알고리즘: 구현(괄호)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2504#문제 풀이 괄호문제가 보면 스택문제임을 깨달아야 한다. 근데 평상시 만났던 괄호가 올바른지 검사하는 문제가 아니라 괄호의 값을 계산하는 문제이다. 바로 문제 설명하겠다.( () () ) 가장 안쪽에 있느 ()는 원래 2이다. 그런데 우린 () 앞에 (가 있었으므로 4라고 칠 거다. 그 옆에 있는 ()도 4라고 치자. 그럼 답이 8이 나오지 않은가?이게 어떻게 이렇게 될 수 있을까? 분배법칙 때문에 그렇다. ( () () ) 는 (()) (()) 와 같다. 즉, 2x(2+2) 이나 (2x2 + 2x2)는 같다. 그러니 우리.. 2024. 8. 2. [백준 17144] 미세먼지 안녕! / 자바 / 구현 #문제 레벨: G4알고리즘: 구현풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/17144#문제 풀이 제목이 상쾌하여 문제에 대한 호감도가 올라갔다. 풀면서 구현 문제에 적합한 것 같아 호감도가 더 올라갔다.이문제에서 우리가 구현할 것은1. 미세먼지 확산2. 공기청정기 바람 부는 것 3 . 토탈 먼지 수 구하기이 두가지이다. 1 ~ 2번을 T초 동안 반복 후 최종적으로 3번을 통해 답을 구하면 된다. 미세먼지 확산은 기존배열을 참조하여 temp(임시)배열에 값을 추가하거나 빼주면 된다................(1)기존 배열을 수정하면 다른 미세먼지 확산을 계산할 때 영향을 미치기 때문에 일단은 temp배열에 다 계산해주고 기존 배.. 2024. 8. 2. [백준 14891] 톱니바퀴 / 자바 / 구현 + 자료구조 #문제 레벨: G5알고리즘: 구현 + 자료구조풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14891#문제 풀이 위 문제는 간단한 구현 문제이다. 회전을 하기 전 그 상태가 모든 톱니바퀴의 회전 여부를 결정하기 때문이다. 만약 처음 그상태가 아니라 톱니바퀴 하나를 돌리고 나서 다른 톱니바퀴의 회전 여부를 결정해야 했다면 이것보다는 조금 더 구현이 복잡해졌을 수 있다. 1. 해당 톱니바퀴를 기준으로 연속적으로 왼쪽 톱니바퀴들이 회전하는지 체크하고 같은 방식으로 오른쪽 톱니바퀴들이 회전하는지 체크한다.2. 회전 시켜준다. 3. 스코어를 구한다. 난 이 문제를 통해 구현연습을 한 것도 있지만 자료구조를 더 집중적으로 공부해봤다. 톱니바퀴의.. 2024. 8. 1. [백준 20058] 마법사 상어와 파이어스톰 / 자바 / 구현 + bfs 조금 *** #문제 레벨: G3알고리즘: 구현 + bfs 조금풀이시간: 2시간힌트 참조 유무: 유 https://www.acmicpc.net/problem/20058#문제 풀이 이 문제는 bfs문제로 분류되어있지만, 사실상 구현문제라 생각한다. 이 문제에 핵심은 격자회전시키는 식을 잘 세울 수 있는지이다. 그 방법을 바로 말하겠다. 오른쪽으로 90도 회전한다고 하면 map[i][j]가 map [j][n-1-i]가 된다. 즉, i와 j를 바꿔주고 열은 n-1에다가 바꾼 i를 빼준다. (왼쪽으로 90도 회전한다고 하면 거꾸로 돼서 map[i][j]가 map[n-1-j][i]가 된다.) 우리는 덩어리 째 회전을 시켜야 하므로 이중 for문에서 i+=L 씩 증가시켜줘야 한다. 위 방식을 이해하고 .. 2024. 7. 29. 이전 1 2 다음
