본문 바로가기

알고리즘/문제 풀이

💔 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라는 아파트 단지.. 더보기
💜 2606 바이러스 JAVA 1. 개요 아주 기본적인 BFS로 풀 수 있는 간단한 문제이다. 이 문제가 잘 안 풀리는 사람은 BaaaaaaaaarkingDog님의 그래프 강의를 보고 오길 바란다. 실버 3도 식은 땀 흘리며 풀었다... 재활운동 시작! 내가 한번 틀렸었는데, 이유는 양방향 그래프임을 생각해주지 않고 풀어서 이다. 이론 정리 다시 해야겠다. 2. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { pu.. 더보기
💔 9663 N-Queen java 문제 설명 https://www.acmicpc.net/problem/9663 N*N 체스판이 주어진다. 체스판에 Queen을 서로가 서로를 죽이지 못하게 모든 행에 놓아라 이떄 놓을 수 있는 경우의 수는 어떻게 되는가? 푸는 원리 백트래킹을 사용해야 한다. 백트래킹이란 깊이 우선 탐색을 하되, 가능성이 없는 루트를 탐색한다고 판단될 경우 과감하게 그 루트를 포기하고 다음 경우의 수를 체크하러 떠나는 것이다. 해당 길이 답을 도출할 수 있는 유망한 길인지 아닌지 체크하는 것은 문제마다 다르다. 따라서 유망성 체크 조건을 알아차리는 감각은 많은 백트래킹 문제를 풀어보며 익혀야 하겠다. 본론으로 돌아와서 N-Queen 문제를 풀어보자. 체스에서 퀸은 비숍과 록을 합친 움직임을 할 수 있는 가장 쎈 장기말이다... 더보기
💔5525번 IOIOI 1. 문제 설명 https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net IOI 형태의 문자열 Pn이 주어질 때, 전체 문자열 S에서 Pn이 몇 번 등장하는지 등장 횟수를 출력해라 2. 푸는 원리 이것도 안 풀려서 답지를 봤다. 문자열 알고리즘을 공부 해야겠다. 나는 문자열을 투포인터로 한번 쭉 훑으려고 했는데 해당 문제는 숫자로 이루어진 것이 아니다 보니, 반복문의 i를 계속 star.. 더보기
💔전깃줄 1. 문제 설명 2565번: 전깃줄 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. www.acmicpc.net 두 개의 전봇대가 존재한다. 두 전봇대 사이엔 여러 전깃줄이 존재한다. 전봇대의 높이는 1~10으로 표현되는데, 전깃줄은 다음 그림과 같이 겹칠 수 있다. 최소한의 전깃줄을 제거해서 모든 전깃줄이 서로 교차하지 않도록 만들어라. 2. 푸는 원리 해당 문제를 LIS로 생각만 할 수 있다면 쉽게 풀리는 문제다. 하지만 그렇게 생각하기가 꽤나 어렵다. 따라서 필자는 먼저 전깃줄 문제를 어떻게 LIS 문제로 볼 수 있는지부터 설명하고자 한다. 위 사진의 .. 더보기
💔가장 긴 증가하는 부분 수열 4 1. 문제 설명 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. www.acmicpc.net 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하고, 해당 조건을 만족하는 부분 수열 중 하나를 출력하라. → 원래 최장 증가 부분 수열의 길이만 구하던 문제에서 이제 그 구성요소를 구하는 문제로 바뀌었다. 2. 푸는 원리 처음에 문제 푸는 데 정말 헤맸는데, 그 이유는 해당 문제도 다른 LIS처럼 이분탐색을 써서 풀려고 했기 때문이다. 하지만 이분탐색의 경우 큰 문제가 있는데, 바로 LIS의 구성요소를 구하기 힘들다는 점이다. 왜 그런지 한번 보자. 먼저 값을 구하기 위해 조작하는 배열을 A, 수열 전체를 담는 배.. 더보기

티스토리툴바