문제https://swexpertacademy.com/main/code/problem/problemDetail.do문제 설명 회사 좌표 S에서 N명의 고객의 좌표를 모두 방문한 후, 집 좌표 E로 이동하려고 한다.두 위치 (x1,y1), (x2,y2)의 거리는 |x1-x2| + |y1-y2|으로 계산된다.각 좌표는 모두 다르다.S에서 출발해서 N명의 고객을 모두 방문한 후 E로 이동하는 경로중 최단 경로를 구해야 한다. 풀이이 문제의 N은 10이다. 따라서 모든 경우의 수를 탐색해보면, 10 * 9 * 8 * 7 * 6 ... * 2 * 1 = 3,628,800개이다. 즉, 완전탐색으로 모든 경우의 수를 탐색해도 문제를 풀이할 수 있다. 시작 좌표부터 하나씩 좌표를 선택하고, 방문 처리하며 백트래킹하는..

문제https://swexpertacademy.com/main/code/problem/problemDetail.do문제 설명N개의 문제가 주어진다.각 문제마다 배점이 다르며, 틀리면 0점 맞으면 배점만큼의 점수를 받을 수 있다.학생들이 받을 수 있는 점수의 경우의 수를 모두 구한다. 풀이단순 true, false인 것을 보고 먼저 떠오른 것은 비트마스킹이었다. 하지만 문제의 조건에서 $N = 100$이기 때문에 $2^{100} = 10^{30}$만큼의 연산이 필요하게 되어 시간 초과가 발생하게 된다. 따라서 경우의 수를 압축할 수 있는 방법을 떠올렸고, Set을 사용해서 문제를 풀었다. Set배열에 가능한 점수를 매번 넣어가며 완전탐색을 진행하면 중복값을 제외하고 검사가 가능하다. N개의 원소를 순회하면..

문제https://swexpertacademy.com/main/code/problem/problemDetail.do문제 설명출발지 S에서 도착지 G까지 이동하며 도로 복구 작업을 진행하려고 한다.S: (0,0)G: (N-1,N-1)도로는 파여진 깊이에 비례해서 복구 시간이 증가한다.깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다.출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구시간을 구한다. 풀이결국에는 S에서 G로 이동할 때 최소 비용을 구하는 것이 이 문제의 핵심이다. 다익스트라를 통해 최소 비용을 구하면 풀리는 문제였다.이 문제는 2차원 배열이 주어졌기 때문에 다익스트라 알고리즘이 아닌 BFS를 통해 최단 거리를 매번 갱신하면서 도착지점으로 이동하도록 코드를 구..

문제https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AZz7FPpqAUnHBIRj문제 설명N개의 정점은 가진 방향성 없는 그래프가 주어진다.서로 다른 정점 쌍이 정확히 1개의 간선으로 이어져 있다.총 $N(N-1)/2$ 개의 서로 다른 간선이 있는 완전 그래프다.각 간선은 양의 정수 가정치를 가진다.해당 그래프에서 최소 스패닝 트리를 계산해야 한다.어떤 간선에 어떤 가중치가 있는지 모르며, 가중치만 리스트로 주어진다.모든 가중치를 간선에 배치했을 때, MST의 최소 비용과 최대 비용을 구한다. 풀이문제를 이해하는데 많은 시간을 사용했다. MST는 N개의 노드가 존재할 때 N-1개의 간선을 사이클이 존재하지 않도록 이..

문제https://www.acmicpc.net/problem/31778문제 설명문자열 S는 길이가 N이며 알파벳 대문자 C와 P만으로 이루어져 있는 문자열이다.대회 전 문자열 S에 다음과 같은 연산을 최대 K번 시행할 수 있다. 1 ≤ i ≤ j ≤ N인 두 정수 $i, j$를 골라 $S_i$ 와 $S_j$를 바꾼다.완성된 문자열 S에 PPC 부분문자열이 가장 많도록 하고 싶다.PPC 부분 문자열이란, 1 ≤ i ≤ j ≤k ≤N 이고 $S_i = S_j = P, S_k = C$인 $(i,j,k)$를 의미한다.만들 수 있는 PPC 부분문자열의 개수의 최댓값을 구한다. 풀이먼저 K번 시행할 수 있는 연산을 통해 최대한 많은 PPC를 만들 수 있는 문자열을 만들어야 한다. 결국 부분문자열은 연속적인 세 ..

문제https://www.acmicpc.net/problem/5625문제 설명삼각 패스트리 N개의 각 x1,y1, x2,y2, x3,y3 좌표가 주어진다.총 M번의 칼질을 진행할 때, 총 몇 개의 페스츄리가 잘리는지 구해야 한다.칼질은 수평, 수직 방향으로만 가능하다.칼질은 음이 아닌 정수의 좌표에서만 가능하다.모든 칼질은 독립적이기 때문에 한번 칼질을 하면 페스츄리는 다시 원래 모양으로 돌아온다. 풀이매번 칼질을 할 때마다 각 페스츄리가 잘리는 범위인지 판단하는 문제이다. 최초의 접근은 각각의 칼질을 할 때 모든 페스츄리 범위에 대해 검사하여 몇 개가 잘리는지 확인하는 방식이었다. 칼질을 총 M회 진행되며 각 칼질마다 N개의 좌표를 검사해야 한다.즉 M*N 만큼의 연산이 필요하기 때문에 $N = 10^..

문제https://www.acmicpc.net/problem/17099문제 설명총 N개의 대회가 입력으로 주어진다.(시작시간, 종료시간, 상금)대회를 치를 수 있는 개수에는 제한이 없다.대회가 끝나는 시간과 다음 대회가 시작하는 시간이 같으면 안 된다.최대로 상금을 벌 수 있는 방법으로 대회를 치렀을 때 최대 상금을 출력한다. 풀이문제를 보면 회의 문제랑 유사하다는 것을 느낄 수 있었다.그래서 우선적으로 생각한 알고리즘은 그리디와 DP정도였다. 문제의 조건 중 "전 대회가 끝나는 시간과 다음 대회가 시작하는 시간이 같으면 안 된다" 조건이 기존 회의 문제들과의 차이점이었다.또한 구하고자 하는 것이 최대 상금이라는 것? 정도 일단 최댓값을 구하는 것이기 때문에 누적 상금을 구하면서 DP로 푸는 것이 더 옳..

문제https://www.acmicpc.net/problem/15553문제 설명구사과의 방에는 난로가 하나 있다. 난로는 친구가 방에 왔을 때 항상 켜야한다.N명의 친구가 집에 방문할 것이다.i번째 친구는 시간 $T_i$에 도착하고 $T_{i+1}$에 나간다.방은 좁기 때문에 한 번에 한 명만 방문할 수 있다.난로는 아무때나 켤 수 있고, 끌 수 있다. 난로를 켜려면 성냥을 이용해야 하는데 총 K개의 성냥을 가지고 있다.처음에는 난로가 꺼져있다.이 때 난로가 켜져 있는 시간을 최소로 했을 때 시간을 구한다.풀이문제를 요약하자면, K개의 성냥을 사용해서 난로를 켜고 끄면서 전체 난로 가동 시간을 최소로 만드는 것이 목표다. 그래서 처음에는 자연스럽게 “난로를 최대한 덜 켜야겠다”는 생각이 들었고, 그리디로..

문제https://www.acmicpc.net/problem/4370문제 설명백준이와 동혁이는 곱셈 게임을 한다.이 게임은 정수 p에 2~9사이의 숫자 중 하나를 곱하면 되는 게임이다.p = 1로 시작하고, n을 정한다.백준이부터 무조건 게임을 시작한다.(번갈아가면서 2~9사이의 수를 곱한다.)이 때 p ≥ n에 먼저 도달하는 사람이 이기게 된다.둘 모드 완벽하게 게임을 한다고 가정할 때 이기는 사람이 누구인지 구한다. 풀이이 문제는 결국 백준이와 동혁이가 서로 최선의 선택을 반복했을 때 누가 먼저 n에 도달하느냐를 구하는 문제이다. 처음 문제를 봤을 때 가장 어려웠던 부분은 최선의 선택이 무엇인지 파악하는 것이었다. 그래서 먼저 게임의 흐름을 단계별로 정리했다. 우선 게임은 항상 백준이가 선공으로 시작..

문제https://www.acmicpc.net/problem/1548문제 설명세 수 x+y>z, x+z>y, y+z>x의 관계를 만족하면 세 수는 삼각관계에 있다고 한다.마찬가지로 길이가 N인 수열 B의 모든 원소 B[i], B[j], B[k]가 삼각관계에 있으면 이 수열은 삼각 수열이라고 한다.이 때 i,j,k는 모두 다른 값이다.수열 A가 주어졌을 때, 이 수엻에서 적절히 몇 개의 원소를 빼서 이 수열을 삼각수열로 만들려고 한다.삼각 수열의 최대 길이를 구한다. 풀이처음에는 DP로 푸는 LIS 문제인가? 싶었다. 문제를 다시 보니 세 개의 조건을 모두 확인할 필요는 없었다.수들을 오름차순으로 정렬했을 때 x ≤ y ≤ z 라고 하면, 삼각관계 조건인x + y > z, x + z > y, y + z >..