알고리즘 공부 및 문제 풀이/소프티어(SOF) (7) 썸네일형 리스트형 [sof] 소프티어 <인증평가(6차) 기출> 출퇴근길 - DFS [문제] https://softeer.ai/practice/result.do?eventIdx=1&submissionSn=SW_PRBL_SBMS_174270&psProblemId=1529 https://softeer.ai/practice/result.do?eventIdx=1&psProblemId=1529&submissionSn=SW_PRBL_SBMS_174270 softeer.ai [풀이] 이 문제의 핵심은 역방향 간선 그래프를 이용하는 것이다. 출근길과 퇴근길에 모두 포함될 수 있는 정점을 구해야 한다. 이를 위해 집 s를 시작점으로 dfs를 한 번 돌리면 s와 연결되어있는 모든 정점을 구할 수 있다. 주의할 점은 출근길 경로에 회사 t는 한번만 등장한다. 즉 t에 도달하면 dfs를 멈춘다. 이제 s와 .. [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.. [sof] 소프티어 <인증평가 4차 기출> 슈퍼컴퓨터 클러스터 (Java) - 이분탐색 [문제] https://softeer.ai/practice/info.do?idx=1&eid=1204&sw_prbl_sbms_sn=171598 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [풀이] 이분 탐색으로 풀 수 있다. low값을 컴퓨터의 최저 성능인 capacity[0]로, high값은 컴퓨터의 최고 성능이 될 수 있는 현재의 최고 성능 값 + 최대로 업그레이드 가능한 점수 값으로 해준다. 최대 비용 B는 10^18 이고, d점을 올리는데 d^2 비용이 사용되므로 최대로 올릴 수 있는 점수는 Math.sqrt(B)이다. mid보다 낮은 컴퓨터 성능들을 B 비용 이내로 모두 mid 성능으로 올릴 수 있다면 low를 mid+1로 하여 mid 값을 높인다. 반대로 .. [sof] 소프티어 <인증평가(3차) 기출> 플레이페어 암호 (Java) - 시뮬레이션 [문제] https://softeer.ai/practice/info.do?idx=1&eid=804&sw_prbl_sbms_sn=171521 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [풀이] 1. 5x5 암호표를 채운다. 25가지의 문자에 대해서 idx를 증가시켜가며 암호표를 채워준다. 행은 idx/5, 열은 idx%5로 나타낼 수 있고, 문자는 한번 씩 등장해야하므로 boolean 배열을 이용해 나왔는지 여부를 체크해준다. 2. 키를 두 자씩 쪼개서 저장한다. 같은 문자가 연속될 경우 X가 아니면 X를, X면 Q를 이어 붙여줘야 한다. 한문자씩 빼와 그 다음 문자와 비교하기 위해 Queue를 사용한다. 마지막 문자의 경우 예외적으로 XX도 허용함에 주의한다! 3.. 이전 1 다음
