공부혜옹

문제이름이 버블소트라 일단 버블소트를 설명하자면 첫번째 인덱스부터 바로 다음 인덱스의 값과 비교하여 현재 기준이 되는 인덱스가 더 클경우 다음 인덱스와 자리를 바꿔주는 정렬이다. 1회 정렬이 끝날때마다 맨 끝순서에 가장 큰 수들이 정렬된다. 버블 정렬은 해당 블로그를 참고했다 https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html [알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 버블소트를 공부한 후 버블 소트를 직접 구현해 swap할 때마다 변수의 숫자를 증가시켜주었는데 아쉽게도 시간초과가 났다. 즉 이..

처음엔 문제 그대로 수열을 재귀적으로 계속 만들다가 수열의 크기가 n 이상이 되면 재귀를 끝내고 해당 수열[n]으로 문자를 찾아주는 코드를 작성했으나 역시나 메모리 초과로 실패하였다. 따라서 수열을 직접 구현하기보단 n자리에 위치한 문자가 m인지 o인지 자체에 집중하며 풀이했다. 수열은 세가지 조건을 합하여 만들어지는데 s(k-1) 부분 / 새로 만들어지는 부분 / s(k-1) 부분 이 새로 만들어지는 부분에 n이 위치한다면 m인지 o인지 바로 알 수 있다. 그 이유는 n에서 s(k-1) 부분 만큼의 길이를 제거하고 난 후 n이 1이면 m 그 외의 숫자이면 o이기 때문이다. 바로 이 새로 만들어지는 부분에 n이 위치할 수 있도록 계속해서 수열을 짧게 줄여주면 된다. 짧게 줄이는 방법은 다음과 같다. 1...

처음엔 정사각형이 되지 않을 조건을 먼저 생각해 보았는데 정사각형 특성상 정사각형일때만 해당되는 조건이 훨씬 명확하고 적은것같아 방향을 바꾸었다. 정사각형이 될 조건은 1. 모든 변의 길이가 같다 2. 대각선의 길이가 서로 같다 주어지는 네개의 점을 이용해 거리를 계산하면 6개의 길이가 나온다 이때 점을 미리 사각형의 형태로 나열한 후 거리를 구하는것 보다 일단 6개의 길이를 다 구한후 sort하면 나머지 두개의 길이가 대각선의 길이임을 알 수 있다. (정사각형은 변의 길이보다 대각선의 길이가 항상 길기 때문) #include #include #include #include using namespace std; int t; int x1, x2, yy1, y2; int func(int x1, int yy1..

어린왕자가 진입/이탈해야하는 경우는 출발점과 도착점 사이에 꼭 통과해야하는 원이 존재하는 경우 이다. 이때, 출발점과 도착점이 같은 원에 있다면? 그원안에 행성이 얼마나 많은지와 상관없이 ( 피해서 갈 수 있으니 ) 진입/이탈해야할 경우가 없다. 따라서 출발점과 도착점사이에 곡 통과해야하는 원이 있는지를 판별하기 위해 두 점과 원의 중심간의 거리를 비교한다. 거리가 원의 반지름보다 크다면 해당 점이 원의 외부에 위치하는 것으로 꼭 원을 통과해야한다. #include #include using namespace std; int t, n; int x1, x2, y1, y2; int x, y, r; int total; int cnt; int main(){ cin >> t; for(int i = 0; i< t;..

어떻게 하면 효율적으로 풀 수 있을까 치킨집 주위로 가까운집이 몇갠지 세서 통계내야하나 별 생각을 다하다가 결국 dfs를 이용해 완전탐색하기로 했다. 치킨집 조합을 모두 구해서 각 조합별 도시의 최소치킨거리를 구해 가장 작은 치킨거리를 보유한 조합을 선택한다. #include #include #include #include using namespace std; int n,m ; int arr[51][51]; bool check[14]; int ans = 987654321; vector chicken; vector home; int calc(pair a, pair b){ return abs(a.first-b.first) + abs(a.second-b.second); } void DFS(int idx, in..

보자마자 가장 큰 자릿수에 있는 알파벳부터 차례대로 숫자를 부여해 계산하면 되겠다라고 간단히 생각해서 코딩하다가 그렇다면 다른자릿수에 있는 같은 알파벳 ex) abcd + gaf 에서 a의 경우는 어떻게 처리해야할지 막막해졌다.. 따로 저장해서 일일히 표기를 해둘까하다가 내가 생각한 접근방법이 처음 부터 틀렸다는 생각이 들었고 다시 로직을 짜기 시작했다. 우선 가장 큰자릿수에 가장큰 수 9를 적용해야 수의 합이 최대가 된다는것은 명확한 사실이다. 문제는 가장 큰자릿수의 알파벳이 무엇인지 판별하는것. 처음에 보이는 자릿수에 따라서 무턱대고 숫자를 부여했다면 이번엔 글자 자체에 자릿수를 한번 부여해보는식으로 접근했다. 위 이미지에서 c의 경우 1000자리와 10자리 두군데에 분포해있기 때문에 c라는 알파벳 ..

배열의 원소값이 1인 부분만 사각형의 일부가 될 수 있기 때문에 0인 부분을 제외하고 생각한다. 1을 만났을때 이것이 정사각형일지 아닐지를 판단하는것이 문제 1을 만날 경우 1의 왼쪽, 왼쪽 대각선위, 위쪽 총 세부분을 검사해 가장 작은 수를 찾아 +1해주면 그것이 해당 사각형 한변의 최대 길이가 된다. 이것을 식으로 표현하면 다음과 같다 arr[i][j] = min(arr[i-1][j], arr[i-1][j-1], arr[i][j-1]) +1 예상치 못하게 fail을 받은 문제인데 '다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.' 이 주어지는 숫자 배열이 실제 숫자가 아니고 string으로 주어지기 때문에 int가 아닌 string으로 받아 인덱스 - 48을 해주어야한다. #include #inc..

도형에다가 dp 문제이기 때문에 도형을 일단 하나하나 그려보면서 규칙성을 찾고자 했다. 3X4사이즈의 벽을 그리던 와중 3X2벽에서 나온 타일의 패턴을 이용할 수 있겠다는 생각이 들어서 바로 3 * 3 = 9 가지구나! 라고 생각하고 코드를 구현했는데 당연히 틀렸다. 왜냐하면 3X2의 패턴말고 추가 패턴이 2가지 더 나오기 때문이다 (빨간 동그라미 친 패턴) 풀겠다는 의지를 가지고 3X8까지 그려본 결과 각 단계별로 추가 패턴은 2개가 나온다는 것을 확인했다. 3X6의 패턴을 파악하던중 중복이 나올 수 있다는것을 알게되었고 중복을 피하고자 하는 방법을 찾기 시작했다. 패턴을 케이스 별로 나누어 생각하는것인데 첫번째 케이스의 경우 이전과 같은 논리로 3X2의 패턴경우의 수 * 3X4의 패턴경우의 수 를 해..