본문 바로가기

알고리즘 풀이56

[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.
[SWEA] 1868번. 파핑파핑 지뢰찾기 - JAVA 🧷 문제 링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📄 풀이 과정 문제 유형 : 구현, BFS 문제를 정말 꼼꼼히 읽어야 안헷갈릴 수 있는 문제였다. 처음에 어떻게 구현할지 흐릿흐릿하긴 했지만, 0이 아닌 칸들도 클릭하면 8방이 클릭된 것으로 처리되는 것으로 생각해서 더 머리속이 복잡했다. 항상 천천히 꼼꼼히 문제를 읽고 계획을 세운 뒤 코드를 짜자고 다짐을 하지만 항상 마음이 급해지기 일쑤인 것 같다..ㅜ 입력이 끝나면 배열을 돌면서.. 2022. 4. 7.
[SWEA] 1767번. 프로세서 연결하기 - JAVA 🧷 문제 링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📄 풀이 과정 문제 유형 : 완탐, 백트랙킹 가장 자리를 뺀 나머지 코어들을 list에 담아 연결할 코어의 리스트를 만든다. 순차적으로 코어를 하나씩 4방을 연결했을 때와 연결하지 않았을 때의 경우로 나눠 계산한다. 4방을 연결할 때는 그 방향으로 다른 전선이나(mat[r][c]=2) 다른 코어(mat[r][c]=1) 가 없는지 판단한 후, 없다고 판단이 된다면 연결한 후, 연결한 갯.. 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.

티스토리툴바