본문 바로가기

알고리즘 공부 및 문제 풀이

 (317)
[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..
[boj] 백준 20058 마법사 상어와 파이어스톰 (Java) - 시뮬레이션(배열 회전), BFS [문제] https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net [풀이] 1. 2^L x 2^L 의 부분격자를 시계방향으로 90도 회전시킨다. 2. 3면 이상 얼음에 닿아있지 않으면 얼음의 양이 1 줄어든다. 3. 남아있는 얼음의 양의 합과 가장 큰 덩어리의 칸의 개수를 출력한다. 2^L x 2^L 의 부분격자에 대해 2차원 배열 회전을 시켜줘야 한다. 2차원 배열 회전은 직접 그림을 그려서 어떻게 회전이 되는지 확인했다. 1 2 ..
[pro] 프로그래머스 level2 12902 3*n 타일링 (Java) - dp [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12902 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] n이 홀수이면 딱 맞는 타일링이 불가능하므로 0을 반환한다. n이 2인 경우 가능한 경우의 수는 모두 3가지이다. n이 4인 경우 n이 2인 경우를 각각 합쳐서 4를 만들 수 있으므로 f(2)*3이 된다. 또한 여기에 합치지 않고 만들 수 있는 모양이 2개가 추가로 있다. 즉 f(2)*3 + 2가 된다. n이 6인 경우, n이 4인 경우에 n이 2인 경우를 각각 합쳐서 만들 수 ..
[boj] 백준 20056 마법사 상어와 파이어볼 (Java) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net [풀이] 1. 파이어볼이 d 방향으로 s만큼 이동한다. 2. 같은 칸에 2개 이상의 파이어볼이 있다면 합쳐진 후 4개로 나눠진다. 3. 이렇게 k번 이동한다. 처음에는 파이어볼을 이동시키기 위해서 board[][] 배열에 파이어볼을 저장한 후 add와 remove를 사용했으나 이 경우 remove 때문에 인덱스가 변경되어 배열 접근 시 오류가 쉽게 ..
[boj] 백준 골드4 7662 이중 우선순위 큐 (Java) - TreeMap [문제] https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net [풀이] 이전 프로그래머스 풀이대로 minHeap과 maxHeap 두개를 이용해 구현하면 시간초과가 발생한다. 시간초과가 발생하는 이유는 다른 우선순위큐의 원소를 제거하기 위해 remove()를 사용할 경우 O(N)이 소요되기 때문이다. 따라서 우선순위큐가 아닌 TreeMap을 이용해서 원하는 원소를 바로 찾아 제거할 수 있도록 하였다. [코드] package heap_stack_de..
[boj] 백준 골드4 14500 테트로미노 (Java) - DFS [문제] https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net [풀이] 이전에 풀었던 코드. 이전에는 ㅏ, ㅓ, ㅜ, ㅗ 모양에 대해 하드코딩을 했었다. 그러나 하드코딩을 하지 않아도 2칸이 선택되었을 때, 3번째 칸에 대해서는 방문 표시만 해두고 다시 원래의 좌표인 r, c에서 dfs 탐색을 진행하면 위의 4가지 모양에 대해서도 테트로미노의 합을 구할 수 있다. [코드] package bfs_dfs; import java.util.*; import..
[boj] 백준 2636 치즈 (Java) - BFS [문제] https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net [풀이] 1. 가장자리의 치즈만 녹아 없어지고 내부에 공간이 있는 경우 영향을 주지 않는다. 따라서 치즈가 없다고 명시된 (0,0)부터 탐색을 진행하면 가장자리의 치즈만 녹일 수 있다. 2. 치즈가 없으면 큐에 넣고 계속 탐색을 진행하고, 치즈가 있으면 치즈를 녹인 후 탐색을 멈춘다. 한번 BFS가 호출될때마다 가장자리의 치즈가 모두 녹을 것이므로 t를 증가시킨다. 3. 탐색이 끝나고 남은 치즈의..

티스토리툴바