Coding Diary

문제 및 코드 1. 생각 // 생각 // 그냥 구현하면 될듯 // 구현 // n번째 피보나치 수를 구하는 함수를 만들기 // 위 함수의 결과를 1234567로 나눈 나머지를 리턴하기 재귀보다 메모이제이션이 낫다 2. 회고 n의 범위에 따른 피보나치 수열의 값을 고려하지 않고 무작정 재귀로 풀었더니 시간초과 오류가 났다. n이 엄청나게 큰 경우 그에 따라 피보나치 수열의 값도 엄청나게 커지는데 아마 그걸 int에 담을 수 없어서 1234567로 나눈 나머지를 저장해야 하지만 그걸 저장하는 부분을 재귀함수에 반영하지 않았다. 엄청 커지면 int, long으로도 표현 불가능한듯. 그래서.. 원래 풀었던 재귀함수에 1234567로 나눠 보려고 했는데 시간초과 계속 발생... 다른 풀이 참고해서 풀었다 3. 기억..

문제 및 코드 1. 생각 // 생각 // 그냥 냅다 구현... // 구현 // n을 2진수로 변환했을 때 1의 개수를 구한다 // while을 돈다 // n을 1 증가시킨 후의 n을 2진수로 변환한 후 1의 개수를 구한다 // 만약 위에서 구한 n의 1 개수와 1 개수가 같으면 break 정확성은 맞지만 효율성에서 틀림... 2. 회고 정확성은 맞는데 효율성은 틀림. 이런 부분이 가장 난감하다... while 돌면서 1씩 증가하면서 다 살펴봐서 그런걸까? 아니면 replaceAll 메소드가 시간을 많이 잡아 먹는 걸까? replaceAll을 없애고 그냥 2진수 String을 for문 돌면서 1의 개수를 세어주니 통과가 되었다... replaceAll의 시간복잡도는 O(n*m)이고 2진수 String을 f..

문제 및 코드 1. 생각 // 생각 // 그냥 문자열 처리 잘 하면 될 것 같음 // 구현 // s가 1이 아닐 때 동안 while 돈다 // s에서 0을 다 공백으로 바꾼다 // 원래 s와 공백으로 바꾼후의 s의 길이의 차이를 누적 // s를 s의 길이를 이진수로 바꾼 걸로 변환 2. 회고 어렵지는 않았는데 String 관련 메소드가 생각 안 나서 참고했다... 기억해야지 3. 기억 String str = "aa"; str.replaceAll("a","b"); StringBuilder sb = new StringBuilder(); sb.append("aaaacc"); sb.reverse(); int num = 6; Integer.toBinaryString(num); // String 결과를 리턴 4. ..

문제 및 코드 1. 생각 // 생각 // 큰 수랑 작은 수랑 곱해야 그나마 작아지니까 한쪽은 오름차순 정렬 한쪽은 내림차순 정렬해서 곱하기.. // 완전탐색까지는 아닌 것 같고... 저렇게 접근하면 풀릴 것 같은ㄷ // 구현 // A를 오름차순 정렬, B를 내림차순 정렬 // 배열 길이만큼 돌면서 인덱스 같은 원소끼리 곱한 결과 합 누적 2. 회고 그냥 오름차순 정렬 후 인덱스 접근만 뒤에서부터 해주면 되는데 역순 정렬 하려다가 괜히 이상한 데 시간 쏟았네... 왜 이 생각을 못했지? 3. 기억 Arrays.sort(배열이름, Collections.reverseOrder())을 통해 역순 정렬이 가능하지만 이때 배열 원소는 원시 타입이 아니라 객체 타입이어야 한다. 즉 int는 안 되고 Integer는 ..

문제 및 코드 1. 생각 // 생각 // 일단은 문자열 처리하는 문제로 보임 // 구현 // 맨 첫 인덱스이면서 숫자가 아니면 대문자로 // 그리고 이전 문자가 뭐였는지 저장을 한다 // 맨 첫 인덱스 아니면 이전문자가 공백이면 대문자로 2. 회고 자료구조나 알고리즘을 딱히 생각하지 않아도 되는 문자열 처리 문제로, 문자열 및 문자 관련 메소드를 많이 알아두면 쉽게 풀 수 있음 단어 처음인지 어떻게 생각하지? 고민하다 이전이 공백이면 된다는 생각이 들어 이전이 공백인지 확인하도록 함 String에서 charAt한 후 다시 String을 어떻게 만들지? String에서 바로 바꾸는 건 안되는데 이러다가 StringBuilder가 생각났다 3. 기억 Character 관련 메소드 Character.isDig..

문제 및 코드 1. 생각 // 0: 벽, 1: 벽 아님 // 생각 // 시작점부터 시작해서 상하좌우를 살피면서 1이면 거기로 가고 0이면 안 가고 // 근데 최단 경로로 가야 하니까 bfs // 구현 // 시작점을 bfs에 넣기 // bfs // 시작점과 maps를 매개변수로 받기 // bfs 위한 큐 생성 // 시작점을 큐에 넣기 // 큐가 비어있지 않을 때까지 반복 // 큐에서 하나 빼고 방문했다고 표시하고 길이 1 증가 // 큐에서 뺀 거 기준으로 상하좌우 돌기 위해 for문으로 4번 돌기 // 시작점 기준 상하좌우가 maps 안에 있으면서 1이면 해당 위치를 큐에 넣기 초반에 생각했던 걸로 이 구현 틀은 틀렸다... 2. 회고 visited 배열의 행 열을 반대로 설정했었다... 곰곰이 생각해보니..

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

문제 및 코드 1. 생각 // 생각 // 감이 안 잡힌다... 그래서 다른 걸 참고 함 // 구현 // dfs 돌면서 만든 단어들을 담을 list를 만든다 // words를 돌면서 각 words를 시작점으로 해서 dfs를 돈다 // 만든 단어 담긴 list를 돌면서 word와 같은 것의 index를 리턴한다 // dfs // 그 동안 만들어진 단어들 담을 list와 앞으로 담을 단어를 매개변수로 보낸다 // 앞으로 만들 단어가 만들 수 있는 최대 단어 길이보다 크면 함수 종료 // 단어 담을 list에 앞으로 담을 단어 없으면 넣기 // for문으로 words를 돌기 // 재귀적으로 dfs 호출 2. 회고 완전탐색으로 분류되어 있기도 하고 완전탐색이 맞는 것 같긴 한데 이걸 어떻게 풀어야 하는지 도저히 ..

문제 및 코드 1. 생각 // 생각 // 트리 형태로 연결되어 있다, 그리고 예시 사진을 보니 dfs 혹은 bfs로 돌면서 확인하면 될 것 같다 // 시작점에서 연결되어 있는 다른 것들을 다 돌면서 count만 하면 된다 dfs, bfs 딱히 상관 없을 것 같다 // 저번에 재귀 계속 했으니 이번에는 큐로 구현할 수 있는 bfs를 해보자 // 구현 // wires를 돌면서 연결리스트를 만든다 // wires를 돈다 // 해당 원소의 전선을 끊는다 // 시작에서 bfs 돈 값과 끝에서 bfs 돈 값의 차이와 현재 answer 중 최솟값이 answer // 끊었던 전선을 다시 붙인다 // bfs 2. 회고 문제 접근법은 떠올리기 쉬웠다. 그리고 bfs도 저번에 복습해서 구현하는데 어려움은 없었다. 그런데 연..

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