https://www.acmicpc.net/problem/14719문제조건2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.고이는 빗물의 총량을 출력접근방법 정해진 알고리즘을 이용해서 푸는게 아니라, 내가 좋아하는 조건에 맞게만 풀면 되는 구현문제이다.풀이법이 여러개가 떠올랐지만, 나는 블록들중 가장 높은 높이에서 부터 시작해서 아래로 스캔하는 방식을 선택했고, 한번 빗물을 채웠으면 더 이상 채울필요가 없으므로, visited배열을 통해서 이미 빗물이 고였음을 체크해줬다.가장 중요한 빗물이 채워질 조건은 양 옆을 감싸는 블록이 적어도 2개이상은 있어야한다는것이다. 소스코드#in..

https://www.acmicpc.net/problem/20437문제조건알파벳 소문자로 이루어진 문자열 W가 주어진다.양의 정수 K가 주어진다.어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.접근방법 그냥 투포인터를 써서 각 문자에 대한 갯수를 셀 수있도록 cnt배열을두고, [문자 - 'a'] 를 인덱스로 K개 이하일때, end포인터의 위치를 이동시켜주고, K개가 되었을때, start포인터의 위치를 이동시켜주는 방식으로 접근했지만 실패했다. 이때까지의 투포인터를 요구하는 문제는 이런방식이면 전부 풀렸는데 이 문제에는 왜 적용이 안될까?어떤 문자 하나만..

https://www.acmicpc.net/problem/17615문제조건파랑/빨강 볼이 일직선상에 놓여있다.같은색 볼끼리 인접하게 놓으려고한다.바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다옮길 수 있는 볼의 색깔은 한 가지이다.접근방법 이중 for문으로 단순하게 풀수 있겠다라고 생각했지만, 입력값이 무려 50만,,,, 무조건 O(n log n)시간안에는 끝내야한다.어떻게 깔끔한 방법이 없을까 생각을 해보다가 아무리 생각해도 방법이 떠오르지않아서, 경우의수 4가지를 하나씩 직접 구현하고, 비교해줬다.두개의 색깔만 존재하므로, 중간에 볼이 끼어서 존재할수 없고, 무조건 한쪽으로 몰려서 절반으로 나뉠수밖에없다.선형탐색을 진행하며 다른 색의 공이 있으면, 뛰어넘어서 위치를 뛰어넘을..

https://www.acmicpc.net/problem/1522 문제조건와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 최소 회수문자열은 원형이다.접근방법 사실 투포인터 라기보다는 슬라이딩윈도우 방식의 풀이이다.원형으로 이루어진 문자열이므로, 원형을 직선으로 펼친 배열로 보았을때, 모든 경우의수를 비교해서 최솟값을 찾는 방식으로 접근했다. 물론 주어진 문자열의 길이가 1000이므로, O(n^2)안에 탐색할수 있으므로 사용할수 있는 방법이다. 소스코드#include #define MAX 1001using namespace std;string s;int main() { cin >> s; int n = s.length(); int res = n; int a = 0;..

https://www.acmicpc.net/problem/3758문제조건총 k개의 문제풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장한 문제에 대해 여러번 제출한다면 가장 높은 점수가 그 문제의 최종점수 (좋은데,,?)최종 점수가 같은 경우풀이를 제출한 횟수가 적은 팀의 순위가 높다.제출 횟수도 같은 경우   마지막 제출 시간이 더 빠른 팀의 순위가 높다. 우리 팀의 순위는?접근방법 딱히 접근방법이라할게 없었다. 문제의 조건이 까다로운 만큼 문제에서 요구하는 그대로 구현만 잘 해주면 되는 문제였다. 그리고 나는 따로 구조체를 만들고 그에 맞게 정렬을 해주었다.  소스코드#include #include #include #define MAX 101using names..

https://www.acmicpc.net/problem/17136 문제조건  1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류의 색종이가 있다.각 종류마다 5개씩 가지고 있다. 10×10인 종이에 색종이를 붙인다. 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다., 0이 적힌 칸에는 색종이가 있으면 안 된다. 필요한 색종이의 최소의 개수?모두 덮는것이 불가능한 경우 -1을 출력 접근방법 하나씩 범위를 넓혀주는 BFS 방법을 써야하나,,? 라는 생각이 들었지만 정형화 시킬 방법이 떠오르지 않았다. 따라서 DFS측면으로 접근했는데, 한변의 길이가 1일때부터 5일때 까지 하나씩 판단해야하고, 그럴려면 중복을 방지 하기위해 visited 배열을 활용해야한다. 이 ..

https://www.acmicpc.net/problem/2254 문제조건 감옥의 좌표 (px,py)가 주어진다.담 기둥의 좌표들이 주어진다.감옥과 담 기둥은 일직선상에 위치할 수없다.각각의 담은 감옥을 완전히 감싸야 하고, 담 안에 (부분적으로라도) 포함되는 담이 있다면 이러한 담도 완전히 감싸야 한다겹치지 않는 최대의 중첩된 담의 겹 수?접근방법 처음보는 유형의 문제라 생각만 2시간이상하다가 검색을 통해 도움을 얻었다,,,,역시 구현이나 어떤 알고리즘을 쓰는가 보다는 기하학적으로 접근해야하는 문제였다.정말 오랜만에 다시 보는 벡터의 외적이 쓰인다니,,, 역시 배운게 다 쓰이긴 한다. Convex Hull 알고리즘 이 문제에서 사용된 알고리즘이다.convex hull이 그래서 대체 뭐냐? 2차원 좌표 ..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제조건 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있다. 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 숫자를 최대로 뽑는 경우, 뽑는 숫자들을 출력하라. 접근방법 모든 경우의 수를 따져서 비교해줄려고 DF..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제조건 부모 자식들간의 관계가 주어졌을때, 계산하고자 하는 두사람의 촌수를 구해라 접근방법 트리 모양 구조를 탐색하는 그래프 탐색 방법으로 접근했다. 근데 촌수 이므로 cycle이 생길 일은 없다. 따라서 각 노드를 양방향 연결해주고 DFS로 탐색해줬다. 아버지의 형제들과 나와의 관계는 3촌으로 분류할 수 있는데, 이를 계산하는 방식은 나 → 아버지(1촌) → 할아버지(2촌)..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제조건 시작점, 시작방향, 세대가 주어진다. K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다. 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다. 접근방법 같은 모양이 계속해서 반복해서 추가되는 것을보고, DP아니면, 재귀의 형식으로 풀 수 있지 ..