빠에야는 개발중

문제를 잘 파악하자! 생각한 것 왜 저렇게 크게 써놨냐면 문제를 제대로 파악을 못해서 잘못된 코드를 짰기 때문이다. 결국 처음에는 그냥 일반적인 팰린드롬을 구현했다(효율적인지는 둘째치고...). 그러다 테스트 케이스가 실패하는걸 보고 문제를 다시 보니 "한 문자 빼고 전부 다 같은 경우"가 있었고 일반적인 팰린드롬은 다른 것들도 카운팅 해주기 때문에 실패한다는 걸 알았다. 또 삽질 그런데 나는 정말 생각없이 "단 하나"임을 놓치고 가운데에 오는 문자가 하나인 것과(홀수 길이) 두개인 것(짝수 길이)을 따로 체크를 해주도록 코드를 작성했다... 그러니 틀릴 수 밖에. 게다가 쓸데없는 연산이 생겼기 때문에 타임아웃에 걸리는건 덤... 진짜 해결책 우선 먼저번에 구현한 "잘못된 팰린드롬"과 같은 방식으로 구현..

생각한 것 YES의 조건이 "단 하나의 알파벳의 개수가 다른 알파벳보다 1개 많고, 다른 알파벳들의 개수를 모두 같을 것"이라고 생각했고, a-z를 나타내는 배열을 만들어 순차적으로 유일성을 체크해주는 로직을 생각했다. 그런데 예를 들어 aabbbcdd 라는 문자열이 있다면 배열로 나타냈을때 [2, 1, 3, 2...]로 표현할 수 있는데, 불가능을 구별하기 위해 2를 기준으로 잡고 순차적으로 체크했을때 1은 넘어가고 3은 안되고... 그런 많은 조건들이 필요해졌기 때문에 이 방법은 아니라고 생각했다. 다른 생각 앞에서 O(n) 시간 안에 할 수 있을거라는 생각에 미련을 버리지 못했었는데.. 정렬을 하면 정말 간단하게 체크할 수 있다. 빈도수 별로 정렬을 하고 각 요소들의 개수와 크기를 비교하면 된다. ..

생각한 것 단순하게 생각해서 입력받은 문자열들을 글자 단위 쪼개 리스트로 만들어 비교해서 공통되는 문자를 카운팅 해서 기존 문자열에서 빼는 로직을 생각했었다. 문자열 a를 순회하면서 문자열 b에 포함된 문자열이 있으면 빼주는 식인데 문제가 있었다. 첫번째는 "어떻게 한 글자씩 뺄 것인가?"이고 두번째는 "String에서 한글자씩 제거할 때 드는 오버헤드의 크기"였다. 보통 String.replace()로 모든 글자를 치환하는 방식을 사용하는데 이번 문제에서는 한 글자씩 제거해나가야 했다. 그리고 한 글자씩 제거하기 위해 루프를 돈다면 O(m*n)의 시간복잡도를 가지게 되므로 비효율적이다. 개선 아나그램은 결국 공통된 문자를 같은 개수만큼 가지고 있으면 된다. 그러므로 문자와 그 개수를 기억하고 선형 시간..

생각한 것 특정 키와 그 키의 빈도수를 표현하기 위해서는 역시 map 구조가 잘 어울린다고 생각했고 형태의 hashmap을 만들어서 입력값을 받아 넣어주었다. 그런데 값이 잘 들어가지 않거나 타임 아웃이 나서 실패했다. 개선 결국 필요한 출력값은 어떤 키가 됐던 간에 빈도수만 맞으면 결정된다. 즉 빈도수만 생각하는 자료구조를 하나 더 만들어주면 된다고 생각했다. 그래서 를 가지는 hashmap을 하나 더 만들어서 값을 넣고 뺄때 함께 계산해줬다. 결말 타임아웃은 여전히 난다. 아직도 완전히 풀고 있지 못한 문제다... 입력 개수가 10만개가 넘어가니 타임아웃이 난다. 아무래도 map.containsKey() 메소드가 순차적으로 값을 찾다보니 그런 것 같다. 그렇다면 특정 key나 value를 한번에 찾으..

생각했던 것 문제가 생각보다 쉽게 느껴졌기 때문에 직관적으로 구현해보았다. 주어지는 각 입력에 맞춰 a부터 b까지 k만큼 더해주었고, 마지막에 정렬을 해서 가장 큰 값을 가져오면 된다. 중간중간 미스가 있었지만 답 자체가 틀리지는 않았다. 문제점 문제는 타임아웃이었다. 주어진 범위에 해당하는 모든 원소에 접근해야하기 때문에 입력값이 100000개가 넘어가면 아무래도 오래걸렸다. 자바가 아니라 C, C++이라면 통과할 수도 있겠다고 생각했지만 꼼수 부리지 말고 알고리즘을 개선해보자. 해결 결과적으로는 스스로 답을 찾아내지는 못했다. 오름차순으로 절반의 값만 계산한다던지 하는 생각이 들긴 했지만 정답은 아닌것 같았다. 좀 더 효율적인 자료구조 활용이 필요해보였다. bfs, dfs 등의 기법이 필요해보이진 않..

생각했던 것 어떤 방식으로 하든 어쨌든 정렬인 문제다. 정렬 중 가장 빠른 정렬은 역시 퀵 정렬이기 때문에 퀵 정렬을 구현해서 스왑할때마다 카운트를 해주자! 웃기고 있네 너무나 당연하게도 퀵 정렬은 최악의 경우에 O(n^2)의 시간복잡도를 보여준다. 따라서 퀵정렬은 항상 가장 적은 swap 수를 보장해주지 못한다. 차라리 합병정렬을 하면 몰라… 그래서 어떻게 할것인가? 직관적으로 가보자 첫번째 원소부터 순차적으로 검사해서 해당 인덱스 i에서의 값이 i+1이 아니라면 원래 그 값이 있어야 할 위치와 바꿔준다. 즉 수식으로 나타내면 arr[i] != i+1 이면 swap(arr[i], arr[arr[i] - 1]) 인 것이다. 결과 맞았다… 이렇게 직관적으로 풀 문제였는데 괜히 돌아가려다가 망했다. 돌아갈거..

생각했던 것 문제에 주어진 배열을 그 상태로 분석하여 각 숫자의 위치에 따라 count 값을 조절하려고 시도했었다. 그러다 보니 두가지 생각이 나왔다. 원래 위치보다 앞에 있는 수 기준 : 앞으로 나온 숫자만큼 더해주고 그 수만큼 뒷자리의 수의 위치변화를 무시한다. 원래 위치보다 뒤에 있는 수 기준 : 원래 위치보다 앞에 있는 수들의 위치변화를 무시하고 뒤로 나온 숫자만큼 더해준다. 둘 다 시도했으나 실패했다. 그 이유는 “뒤로 간 숫자들끼리도 위치를 바꿀 수 있는 경우”를 생각하지 못했기 때문이다. 예를 들어 1 2 5 4 3이라는 배열이 주어졌다면 5가 앞으로 2번 나온 것도 더해줘야 하지만 뒤에서 서로 자리를 바꾼 3, 4도 생각해줘야한다. 앞선 두 방법은 이 경우를 고려하지 못한다. 풀이 결국 힌..

오랜만에 문제를 풀면서 간단하지만 쉽게 풀지 못했던 문제가 있었다. 결국 시간적으로 너무 오래 걸리는 것 같아 답을 찾아보았고 여러가지 것들을 배울 수 있었던 문제였다. DP 가장 먼저는 DP를 생각해내지 못했다. 경우의 수가 있고 그것들을 비교해서 최적값을 가져간다는 생각은 있었지만 선형적으로만 생각했지 메모이제이션에 대해서는 떠올리지 못했다. 배열의 크기 조절 평소에 배열을 다루면서 i+1, i+2 따위로 인덱스를 찾았는데 이렇게 하면 항상 마주치는 것이 ArrayIndexOutOfBound exception이었다. 볼 때마다 어떡하지 했었는데, 다음과 같은 두가지 방법으로 해결하면 된다는 걸 알았다. 1. 문제에 주어진 배열의 최대값보다 더 큰 배열을 만들면 된다. 2. dp를 사용하면 현재 인덱스..

왜 비교하는가? 나는 git을 사용하긴 하지만 git 커맨드를 기본적인것 외에는 잘 모른다. 처음 git을 접할 때부터 좋은 클라이언트를 함께 가져갔기 때문인데, 그것이 atlassian의 sourcetree이다. 깔끔한 인터페이스와 마우스 클릭 몇번이면 커밋, 푸시, 풀이 쉽게 되었고 특히 cli의 그것과는 전혀 다른 예쁘장한 그래프까지… 안 쓸 이유가 없었다. 그렇게 몇 년 간을 써오던 sourcetree인데 최근 들어 문제가 조금씩 나타났다. 다루는 프로젝트의 크기가 점차 커져가서 그런건지 sourcetree로 코드를 확인할 때 조금씩 버벅임이 발생했다. 특히 스태시처럼 한꺼번에 많은 내용들을 볼 때는 마우스 커서마저 느리가 만드는 위엄을 보여주었다.. 지금 쓰는 컴퓨터 내부의 문제일 수도 있지만(..

오랜만에 글을 쓴다. 전부터 궁금했던 redis에 대해서 알아보자.2015년에 ndc에서 들었던 세션 중에 마비노기 TCG 게임에서 redis를 사용하여 캐싱을 한다는 이야기를 들은 기억이 있다. 그 때 이름만 듣고 넘어갔던 녀석이 점점 많이 들리기 시작했고 최근에는 H2 데이터베이스를 사용해보면서 “인 메모리 데이터베이스”의 개념을 알게 되었고 결국 대중적 오픈 소스인 redis에 도달하게 되었다. 그럼 이것들이 다 무엇인가? In-memory Database 인메모리 데이터베이스는 디스크가 아닌 메모리에 데이터들을 저장하는 방식의 데이터베이스를 일컫는다. 처리 속도가 디스크에 비해 월등히 빠른 메모리 레벨에서 데이터를 처리함으로써 성능 향상을 도모한 것이다. 그런데 메모리에 데이터를 저장한다는 건 시..