본문 바로가기

분류 전체보기

(386)
[boj] 백준 21068 상어 초등학교 (Java) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net [풀이] 1. 자리를 배치하는 번호 순대로 앉을 수 있는 모든 자리를 넣는다. 정렬에 필요한 요소인 인접 칸에 앉은 좋아하는 학생 수, 인접 칸에 비어있는 자리수를 자리의 행, 열 번호와 함께 저장해주었다. 2. 조건에 맞게 정렬한 후 학생을 자리에 앉힌다. 3. 학생들이 모두 자리에 앉으면 만족도 합을 구한다. [코드] package 시뮬레이션; import java.util..
[boj] 백준 21609 상어 중학교 (Java) - 시뮬레이션, BFS [문제] https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net [풀이] 1. 블록 그룹을 구한다. 인접해있고, 같은 색의 일반 블록과 무지개 블록으로 구성되어있으며 검은 블록은 포함되면 안된다. BFS를 돌려서 구할 수 있다. 정렬에 필요한 데이터들을 저장해주었다. 중요한 점은 무지개 블록은 중복되어 포함될 수 있다!! 대놓고 써져있지 않아서 처음에 이 부분을 간과했는데 "무지개 블록은 얼마나 들어있든 상관없다." 는 부분을 주의해야 한다. 이를..
[boj] 백준 23288 주사위 굴리기 2 (Java) - 시뮬레이션, BFS [문제] https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net [풀이] 1. 주사위를 굴린다. 이 문제의 핵심 부분이다. 주사위를 어떻게 굴릴지 고민하다가 전개도를 가로, 세로 나눠서 두가지 배열로 저장했다. 동쪽으로 굴리면 가로배열이 한칸씩 오른쪽으로 이동하고, 서쪽으로 굴리면 가로배열이 한칸씩 왼쪽으로 이동한다. 남쪽으로 굴리면 세로배열이 한칸씩 오른쪽으로 이동하고, 북쪽으로 굴리면 세로배열이 한칸씩 왼쪽으로 이동한다. 이때 가..
[boj] 백준 21610 마법사 상어와 비바라기 (Java) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net [풀이] 마법사 상어와 파이어볼 문제와 상당히 유사하다. 1. 초기 구름은 (N, 1), (N, 2), (N-1, 1), (N-1, 2) 에 존재한다. 구름 리스트를 만들어 구름을 세팅한다. 2. d방향으로 s만큼 구름을 이동한다. 이때 주의해야 할 점은 1-N 열과 행이 연결되어 있기 때문에 인덱스 오류가 나지 않도록 설정해야 한다. 위 문제와 똑같은데, d[i]*s%n 만큼 이..
[sof] 소프티어 <인증평가 5차 기출> 업무 처리 - 이진 트리 [문제] https://softeer.ai/practice/info.do?idx=1&eid=1256&sw_prbl_sbms_sn=172419 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [풀이] 1. 높이가 h인 이진트리의 노드의 개수는 2^(h+1) - 1 이고, 리프 노드의 개수는 2^h 개이다. 각 업무는 올라온 순서대로 처리하므로 Queue[][] 배열을 이진트리 노드의 개수만큼 만든다. 이때, 리프노드를 제외한 노드들은 모두 홀수일에는 왼쪽 부하가 올린 일을, 짝수일에는 오른쪽 부하가 올린 일을 처리한다. 따라서 2차원 배열로 만들어서 왼, 오른쪽을 구분할 수 있도록 한다. 2. r일 동안 일을 처리한다. 이진트리에서 자신의 상사 노드의 인덱스는 (i+1)..
[sof] 소프티어 <인증평가 5차 기출> 성적 평가 (Java) - 시뮬레이션 [문제] https://softeer.ai/practice/info.do?idx=1&eid=1309&sw_prbl_sbms_sn=171753 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [풀이] 문제도 단순하고 풀이도 단순한데 너무 쓸데없이 복잡하게 푼 느낌... 먼저 각 대회마다 모든 참가자들의 점수를 저장해주고 이를 내림차순으로 정렬한다. 그 후 등수를 매기면 된다. 주의할 점은 점수가 같다면 같은 등수를 유지하도록 해야한다는 것. 라이브러리에서 가져다 쓴 sort가 시간초과가 나서 직접 정렬을 구현해야 했으면 피곤했을 것 같다. [코드] import java.util.*; import java.io.*; public class Main { static int ..
[sof] 소프티어 <21년 재직자 대회 본선> 거리 합 구하기 (Java) - DFS, 트리 [문제] https://softeer.ai/practice/info.do?idx=1&eid=635&sw_prbl_sbms_sn=171739 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [풀이] DFS를 이용해서 풀 수 있다. 상상도 못한 접근법이라 소프티어가 제공하는 풀이 동영상을 보고서야 풀 수 있었다..참고하면 좋을 듯. *풀이 동영상 Softeer 아직 태그 없음 --> [2021년 재직자 대회 본선] 거리 합 구하기 Softeer 관리자 1580 views · 2021-12-07 14:27 1 즐겨찾기 softeer.ai 먼저 subtree를 이용해야 한다. subtree의 개수는 자기자신을 포함한 자식노드의 개수가 된다. 즉 위 그림에서 2, 5, 6, 7..
[sof] 소프티어 <인증평가 4차 기출> 통근버스 출발 순서 검증하기 (Java) - 구간합 [문제] https://softeer.ai/practice/info.do?idx=1&eid=654&sw_prbl_sbms_sn=171624 Softeer 문제에서 주어진 조건을 만족하는 서로 다른 (i, j, k) 순서쌍의 개수를 출력한다. 첫 번째 위치에는 2번 버스, 두 번째 위치에는 3번 버스, 그리고 세 번째 위치에는 1번 버스가 기다 softeer.ai [풀이] i, j, k 3중 for문을 돌리거나 dfs로 3가지 순열을 찾아서 aiak를 만족하는지 확인하면 풀 수 있다. 그러나 당연히 시간초과가 발생하기에...효율적으로 푸는 방법을 생각해내야 하는데 아아무 생각도 나지 않았고, 소프티어에서 제공해준 모범답안을 확인했다. 1. 먼저 arr[x][j]는 j보다 오른쪽에 있는 배열 값들에 대해 x..