일지 & 개발

문제 요약알고리즘 분류: 이진 탐색, 수학난이도: Silver3문제내용:1번부터 N개번 징검 다리가 있다.첫 징검다리는 아무대나 점프할수 있다.그 다음 징검다리는 이전 이동한 거리보다 1이상 더 긴거리로 이동해야 한다.N번 까지 최대 몇번 건널수 있는지 구하여리첫줄에 케이스 T가 주어지고 각 케이스마다 N이 주어진다.사이트: https://www.acmicpc.net/problem/11561 문제풀이이번 문제에서 최대 징검다리수가 10^16 이다. 이정도 숫자이면 1 부터 10^16까지 탐색하면 시간초과가 나올것이다. O(N) 탐색이 아닌 O(logN)의 탐색으로 처리할수 있도록 해야 시간복잡도 문제를 해결할수 있다. 그래서 이번 문제는 이진 탐새으로 풀어야 할수 있다. 이진 탐색 관련글은 아래에서 확인..

문제 요약알고리즘 분류: 이진 탐색, 수학난이도: Silver3문제내용:X: 게임 횟수, Y: 이긴 횟수, Z: 승률(정수)계속 이긴다고 가정 했을때 몇판 더해야 승률이 변하는지 구하여라 만약 변하지 못하면 -1로 반환 하여라사이트: https://www.acmicpc.net/problem/1072 문제풀이 이번 문제는 하나씩 +1 씩 대입해서 정답은 나오지만 최대 숫자가 100억이다. 그리고 승률은 소수가 아닌 정수이다. 그럼 변화할라면 1%올라가야 하는데 1000억기준으로 올라갈라면 최대 10억번을 탐색 해야 한다. 그럼 초당 연산 1억기준으로 O(N)탐색 하면 오류가 날수 있다. 그래서  O(logN)탐색 시간초과 이내로 끝내야 통과가 된다. 그래서 이진탐색으로 해결할것이다. 이진탐색에 대한 내용은..

문제 요약알고리즘 분류:  배열, 시뮬레이션, 구현난이도: Medium문제내용:8 × 8 체스말이 주어진다. 체스말에서 king 1명, queen N명이 있다.Queem 중에서 왕을 잡을수있는 Queen의 위치들을 반한 하여라단 앞에 가로 막는 퀸이 있으면  그것은 제외 해야 한다.사이트 주소: https://leetcode.com/problems/queens-that-can-attack-the-king/description/문제풀이 이번 문제는 구현 문제중에서 시뮬레이션 문제이다.  각 Queen을 이동 시켜  King까지 갈수 있는지 체크만 하면 되는 문제이다.  일단 퀸이 움직일수있는 방향은 대각선, 가로, 세로 총 8군대이다. 하지만 각 queen이 8방향 탐색하면 시간적으로 비효울이 나와서 반대..

문제 요약알고리즘 분류:  Tree, 재귀호출난이도: Medium문제내용:nums배열, 리스트를 주어 줬을때 아래와 같은 트리를 완성 하여라nums에서 가장 큰 값을 루트 노드로 만듭니다.가장 큰 값의 왼쪽 부분 배열로 왼쪽 서브트리를 재귀적으로 만듭니다.가장 큰 값의 오른쪽 부분 배열로 오른쪽 서브트리를 재귀적으로 만듭니다.사이트 주소:https://leetcode.com/problems/maximum-binary-tree/description/문제풀이 이번 문제는 이진 트리를 완성시켜야 되고 완성시키기 위해서 재귀호출을 사용 해서 풀것이다. 트리에 대한 자세한 글은 아래 글에서 확인 하여라https://jih3508.tistory.com/87 [알고리즘 이론] 트리(Tree)이론 이번에 볼 자료구조는..

문제 요약알고리즘 분류: Two Pointer난이도: Medium문제내용:difficulty, profit, worker 있다.dificulty[i]는 난이도이고 profit[i]는 diffculty[i]수행시 보상이다.worker는 일하는 사람 최대 할수 있는 난이도를 나타내고 diffculty 이하만 수행 할수 있다.worker들이 최대 보상 받을수 있는 합친 값을 나타 내어라사이트 주소: https://leetcode.com/problems/most-profit-assigning-work/description/문제풀이 이번 문제는 브루드포스 같은 모든 경우의 수로 풀면 시간 초과가 난다. 그래서 최적의 시간 복잡도를 돌려야 하는 투포인트 문제이다. 투 포인터 대한 설명은 아래글에 참고하여라https..

설명은 나중에 올리겠다.

문제 요약알고리즘 분류: Array, 구현난이도: Medium문제내용:nums 배열/리스트를 준다.nums에 아래조건하에 2차원 리스트로 변경한것을 반환 해야한다..각 리스트에 중복된 숫자가 없어야 한다.사이트 주소: https://leetcode.com/problems/convert-an-array-into-a-2d-array-with-conditions/description/문제풀이 이번 문제는 간단한 구현문제이다. 구현은 아래와 같이 하면된다.2차원 리스트를 선언한다.각 리스트 1행부터 탐색해서 num이 있는지 확인한다.없으면 없는 행에 추가한다.리스트 각 행마다 탐색했는데 다 있으면 새로 행을 추가해서 num을 담는다.이렇게 구현하면 시간 복잡도는 nums 개수 탐색하는것과 리스트 포함하는지 확인..

문제 요약알고리즘 분류: Hash, Ascill Code, 문자열난이도: Medium문제내용:a-z 를 0-25까지 표현한다.(ex. a = 0, b = 1, c = 3 ...... ,z = 25)문제에서 문자열 s, k정수를 준다.문자열 s에서 k만큼 자르고 자른 문자열에서 각 알파벳을 숫자로 변환하고 합친다.합친것을 숫자에서 알파벳으로 변한다. 넘어가면 26나머지 값을 알파벳을 변환한다.자른 문자열에서 처리한 것들을 합친것을 반한하여라사이트 주소: https://leetcode.com/problems/hash-divided-string/description/문제풀이 이번 문제는 문자열을 각 문자형으로 변환후 Ascill Code로 처리하는 문제이다. 문자형 Ascill Code로 변환해서 처리하는 문..