본문 바로가기

알고리즘/문제 풀이

💜 백준 2085 사탕게임 JAVA 1. 문제 설명 (사탕게임 링크)[https://www.acmicpc.net/problem/3085] 캔디 크러쉬 처럼, 서로 다른 종류의 캔디가 보이면 자리를 바꾼다. 그 후, 한 행, 혹은 한 열에서 같은 종류의 캔디끼리 나열되어 있으면 그건 터져서 사라짐. 주어진 2차원 배열에서 한 번 자리를 바꿨을 때 터질 수 있는 최대한의 캔디의 개수를 구하시오 2. 푸는 원리 서로 다른 종류의 캔디를 만나면 자리를 바꾼다. 모든 행을 검사하며, 일련의 연속성을 가진 캔디의 개수를 센다. -> 최고 길이 갱신 모든 열을 검사하며, 일련의 연속성을 가진 캔디의 개수를 센다. -> 최고 길이 갱신 최고 길이를 출력한다. 3. 코드 분석 import java.io.BufferedReader; import java.i.. 더보기
💜 백준 1038 감소하는 수 1. 문제 분석 감소하는 수 문제 링크 321, 952 등 제일 큰 자릿수부터 작은 자릿수로 올수록, 자릿수의 값이 작아지는 경우, 감소하는 수라고 한다. 반면 322, 235 등은 위의 정의에서 벗어나기에 감소하는 수가 아니다. 0을 0번째 감소하는 수, 1을 1번째 감소하는 수, 9를 9번째 감소하는 수 라고 했을 때, 주어진 N에 관하여, N번째 감소하는 수의 값을 구하여라 2. 푸는 원리 조합이다. 하지만 원래의 조합처럼 오름차순으로는 풀 수 없다. (1) 첫번째 자릿수를 고정하고, 그 자릿수를 limit으로 정한다. (2) 조합을 돌며, 두 번째 자릿수는 limit보다 작은 수 중에서 하나를 택한다. (3) 재귀를 돈다. (4) 세 번째 자릿수를 고를 때는 두 번째 자릿수가 넘어설 수 없는 li.. 더보기
💔 백준 14500 테트로미노 1. 문제 분석 백준 테트로미노 링크 2차원 배열에서 면 대 면으로 붙는 원소끼리 총 4개를 이었을 때, 원소간의 합이 최대값이 되는 경우를 구하여라. 2. 푸는 원리 테트로미노로 나올 수 있는 값들이 미리 나와 있다. 왼쪽 상단부터 1번이라고 하자. 그리고 왼쪽 -> 오른쪽으로 번호를 붙이겠다. 1번부터 4번에 해당하는 블럭은 DFS로 값을 구할 수 있다. 예를 들어보면, 다음과 같다. 하지만 5번의 경우 단순 dfs로 안 풀린다 왜냐하면 두번째 depth 부터 갈 수 있는 길이 2 갈래로 갈라지기 때문이다. 따라서 DFS로는 풀지 못하고, 중앙에서 시작하여 4방 탐색 중 3방을 고르는 조합으로 문제를 풀었다. 3. 코드 분석 import java.io.BufferedReader; import java.. 더보기
💔 백준 2503 숫자야구 JAVA 1. 문제 설명 2503번 숫자야구 주소 영수가 숫자 3개를 머릿속으로 생각, 민혁이는 그 숫자를 맞추기 위해 3개의 수를 말하여 N번 추측을 한다. 민혁이가 말한 숫자 중 하나가 영수가 생각한 숫자와 위치도 같고, 숫자도 같으면 1 Strike, 민혁이가 말한 숫자 중 하나가 영수가 생각한 숫자와 위치는 다르지만, 숫자는 같으면 1ball, 이 행위를 N번 반복할 때, 영수가 생각한 숫자 3개가 될 수 있는 후보 수의 개수를 구하여라 2. 문제 푸는 원리 민혁이가 추측한 숫자가 영수의 머릿속 숫자와 얼마나 같은지는, 해당 숫자가 받은 ball_count를 보면 된다. 예시에서, 영수가 생각한 숫자가 324이고, 민혁이가 추측한 수가 429이면 1S 1B이다. 따라서 민혁이가 말한 숫자 N 개의 Ball.. 더보기
💚 5430 AC JAVA 목차 1. 문제 설명 2. 원리 설명 3. 코드 분석 1. 문제 설명 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 2. 원리 설명 해당 문제는 deque라는 양방향에서 add, poll이 가능한 자료구조를 이용하여 문제를 풀었다. 아직 deque가 낯선 분들은 여기로 가서 봐주세요 https://velog.io/@sdk1926/deque%EB%8A%94-%EC%99%9C-%EC%93%B8%EA%B9%8C toggle(boolean) 값을 두었다. 그래서 R이라는 명령어가 들어오면 true, fal.. 더보기
💔 14889. 스타트와 링크 목차 1. 문제 설명 2. 푼 원리 설명 3. 코드 1. 문제 설명 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 2. 푼 원리 설명 일단 나는 이거 답지 봤다. (1) 팀을 조합으로 반으로 나눈다. -> (2) 각 팀 멤버간의 시너지 계산 -> (3) 차 구해서 그 차가 지금까지의 값 중 최소일 경우 갱신 요거까지는 생각을 했는데, (2)도 조합으로 스타트팀 내에서 2명씩 짝을 잡아서 값을 계산 해야 한다고 생각했다. 그러면 경우의 수가 기하급수적으로 늘어난다... 더보기
💜 2589 보물섬 목차 1. 문제 설명 2. 내가 푼 방법 3. 코드 분석 1. 문제 설명 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 육지하고 바다가 있는데, 해적은 육지로만 갈 수 있다. 육지는 인접할 수 있고, 해적은 대각선을 제외한 사방으로만 움직일 수 있다. 보물은 해적이 걸어서 갈 수 있는 육지 안에 가장 거리가 긴 육지노드에 각각 존재하는데, 이때, 보물 2개를 찾는 최단 거리를 구하시오. 2. 문제 푼 원리 설명 2차원 배열을 돌면서 육지를 만나면.. 더보기
💜 2667번 단지 번호 붙이기 JAVA 1. 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2. 풀이에 대한 설명 2차원 배열을 순회하면서, (1) 1을 만난다면! 거기서 부터 해당 1의 상하좌우 중 붙어있는 1이 있는지 확인한다. (아파트 단지 내의 아파트 수 체크) (2) 내가 금방 방문해서 확인한 1은 -1로 값을 바꾸어서 방문 처리한다. (3) 1 search가 끝나면 해당 아파트 단지의 아파트 수를 다 센 것이다. (4) 이때 아파트 수를 aptList라는 아파트 단지.. 더보기

티스토리툴바