Coding Diary

문제 및 코드 1. 생각 맨 처음에 2차원 배열 만들고 그걸 1차원으로 바꾼 후 추출하려고 했는데 도저히 안 돼서 찾아보니 어차피 저렇게 하면 시간 초과 난다고 하더라.. 2. 회고 위와 같이 생각해서 풀려고 했지만 시간 초과 난다고 했음. 그래서 다시 조건 살펴보니 n이 너무 커서 for문 돌면 복잡도가 너무 커질 것 같다는 생각을 하게 됨. 도저히 다른 방법은 생각이 안 나서 찾아봤더니 배열의 index를 나눈 몫과 나머지 중 큰 값에 1을 더하면 해당 배열에 들어갈 값을 구할 수 있다고 함. 해보니 되긴 하는데 어떻게 이런 생각을 해낼 수 있는지... 아직 이해가 잘 가진 않음. 그리고 long과 int 사이 형 변환을 언제 해야하는지 잘 파악을 못해서 좀 애먹음. 3. 기억 long -> int ..

문제 및 코드 1. 생각 // 생각 // citations 정렬 후 반복문 돌기 // 구현 // h-index 최댓값은 citations의 길이부터 시작가능 // citations 정렬 // citations를 돈다(내림차순으로) // 각 값이 h-index보다 크거나 같으면 지금까지 count 1 증가 후 다음으로 // 각 값이 h-index보다 작으면 h-index와 count비교해서 다르면 종료 후 h-index 1 줄이고 다시 반복 // 각 값이 h-index보다 작으면 h-index와 count비교해서 같으면 해당 h-index 리턴 2. 회고 맨 처음에 위와 같은 생각을 가지고 풀었는데 딱 한 테케가 실패했다. 다른 테케들을 넣어봤지만 도저히 못 찾겠어서 다른 글들을 참고해보니 [4, 3, 3..

문제 및 코드 1. 생각 // 생각 // 중복된 합 세면 안 되니까 집합 // // 구현 // 반복문 돌아야하는데 총 도는 횟수가 elements길이*(elements길이-1)+1이다 // 확인해야 하는 길이수만큼 반복문을 돈다(1개~elements길이) // 배열을 돌면서 위의 길이 안에 속하는 원소들의 합을 구한다 // 집합에 넣는다 2. 회고 3중 for문이 생각나긴 했는데 이게 맞나.. 라는 생각과 변수 설정이 헷갈려서 다른 풀이를 참고했다. dp도 있는 것 같긴 한데.. 원형 처리를 위한 부분도 생각나지 않았는데 배워감 3. 기억 배열이 주어졌을 때 원형 처리를 하기 위해서는 특정 값을 배열 길이로 나눈 나머지를 인덱스로 하면 원형으로 값을 탐색할 수 있다. 4. 체크 풀이 횟수 시간 정답 여부..

문제 및 코드 1. 생각 // 생각 // 괄호쌍 검사니까 스택 // 구현 // 괄호쌍 검사하는 부분을 함수로 따로 만들기 // 여는 괄호면 스택에 넣기 // 닫는 괄호인데 스택 비어있지 않으면 스택에서 꺼내서 일치하는지 확인 // 회전 // s의 길이만큼 돌기 // i부터 s길이만큼 substring한 결과 + 0부터 i 만큼 substring한 결과를 확인 2. 회고 괄호쌍 검사의 경우 처음에 조건 잘못 확인해서 오류가 났음. 괄호쌍 검사할 때 조건을 잘 확인하자 회전을 어떻게 시킬까 하다가 substring 메소드 이용해서 회전을 만들어내려고 하였음. 위의 생각대로 풀고 제출했더니 테스트 13이 통과되지 않았음 혹시 몰라서 "("을 입력값으로 넣은 테케를 만들어보니 이게 문제 괄호쌍 검사가 잘못 되었..

문제 및 코드 1. 생각 // 생각 // 1과 2를 배치한 합이 n을 만들 수 있는 모든 경우의 수를 구해야 함 // 조합의 느낌 // 구현 // 규칙이 피보나치 수열... // 피보나치 수열의 값을 재귀로 구해도 되고 dp로 구해도 된다 2. 회고 여러 경우를 살펴보니 조합과 순열의 기운이 느껴졌다. 그런데 조합과 순열 코드 작성이 잘 안 돼서 다른 코드를 참고했다. 그런데 n에 따른 결과가 피보나치 수열이라고 dp로 풀더라... 그래서 나도 dp로 풀었다 dp로 풀 생각을 맨 첨에 어떻게 하지..? 3. 기억 피보나치 수열을 dp로 풀 때 들어올 값이 1인 경우를 잘 고려해야 한다. 4. 체크 풀이 횟수 시간 정답 여부 참고 여부 1 25분 O

문제 및 코드 1. 생각 // 생각 // 두 수의 최소공배수 구하는 걸 반복 2. 회고 최소공배수 구하는 함수를 만든 후 배열에 있는 수끼리 최소공배수를 구해나가면 될 것이라고 생각함. 그래서 최소공배수 구하는 함수를 먼저 구현하고자 함. 약간의 시행착오가 있었지만 반복문을 사용해서 최소공배수 구하는 함수를 만들었음. 내가 구현한 방식은 소인수분해를 이용하여 구현한 방식이고 다른 방법도 있는 것 같음. 다른 방식 중 하나는 유클리드 호제법을 활용하는 것. 유클리드 호제법에 대한 설명은 알고리즘 글 참고. 3. 기억 유클리드 호제법 재귀로 구현 public static int gcd(int num1, int num2){ // num1 > num2 라고 가정 if(num2 == 0){ return num1;..

문제 및 코드 1. 생각 모양이 트리라 트리 문제인가 생각했다가... 그냥 list에 넣어서 처리해야 하나 생각했다가.. 2. 회고 list를 만들어서 거기에 사람들 넣어두고 삭제해 나가면서 확인하는 방식으로 반복문 2개 돌았는데 이상하게 한 건지 테케부터 시간초과가 떠서 다른 풀이를 참고했다 핵심은 모든 사람을 살펴볼 필요가 없고 a와b는 계속 이기니까 a와b의 대진 순서만 구하면 되는 것. 둘의 대진 순서가 결국 같아질때 답이 나오게 된다. 3. 체크 풀이 횟수 시간 정답 여부 참고 여부 1 40분 O

문제 및 코드 1. 생각 // 생각 // numbers를 돌면서 가지치기 하면서 양수 음수로 나누어 numbers 끝까지 경우를 구한 후 수 다 더하면 되는데.. // 깊이 탐색하면 되니까 dfs인듯 // 구현 // numbers의 맨 첫 원소를 기준으로 dfs 돌기 // dfs // 들어온 원소의 인덱스, 지금까지의 합, numbers 배열을 매개변수로 받는다 // 들어온 인덱스 다음부터 다시 dfs를 돈다 // 이때 음수 양수로 나누어 dfs를 돌게 해야 한다 // 들어온 인덱스가 numbers의 길이와 같으면 // 지금까지의 합이 target과 같은지 비교한 후 답을 1 증가 ---- // 생각 // numbers 각각을 돌 때 플러스 마이너스 각각을 붙여가며 가지치기해서 결과를 확인해야 함 \ /..

문제 및 코드 1. 생각 // 생각 // 던전들을 각기 다른 모든 순서로 돌면서 탐험 가능한 최대 던전 개수를 구해야 한다 // 예를 들어 3개라면 123 132 213 231 312 321 ... // 각 던전 for문 돌면서 재귀로 완전탐색하면 되지 않을까? // 구현 // for문으로 던전을 돈다 // 각 던전을 시작으로 해서 순차적으로 다른 던전 돌도록 탐색을 해본다 // 현재 피로도가 최소 필요도보다 크거나 같다 // 현재 피로도 = 현재 피로도 - 소모 필요도 // 현재 피로도가 최소 필요도보다 작다 // 중단 ---- // 생각 // 던전을 돌 수 있는 모든 경우의 수를 돌면서 총 몇 개를 방문할 수 있는지 세어야 함 // 완전탐색, 재귀로 구현 가능 // 구현 // 방문배열 초기화 // 재..

1. 정의 완전 이진 트리로 최소 힙이라면 작은 값이 위쪽에 있고 최대 힙이라면 큰 값이 위쪽에 있다. 즉, 최소 힙이라면 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같다. 최대 힙이라면 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같다. 2. 특징 우선순위큐를 위해 사용되는 자료구조 중복된 값을 허용한다 3. 구현 배열로 구현한다 구현의 용이성을 위해 트리의 인덱스를 1로 시작한다 왼쪽 자식의 인덱스 = 부모 인덱스 * 2 오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 1 부모의 인덱스 = 자식의 인덱스 / 2 4. 연산 1) 삽입 새로운 요소가 들어오면 완전 이진 트리의 맨 뒤에 일단 삽입을 한다 삽입한 새로운 노드를 부모와 비교해가면서 최소 힙 혹은 최대 힙에 맞게 교환해 나간다 ..