빠에야는 개발중

에피소드 어쩌다보니 회사에서 기존에 운영하고 있던 데모 시스템의 UI를 수정하게 됐는데, React.js를 사용한 WEB UI였다. 로컬 테스트를 위해서 클라이언트와 서버(golang으로 작성되어 있음)를 띄웠고 로그인을 시도했는데, CORS 경고가 떴다. 그래서 실제로 동작하고 있는 클라우드 서버의 네트워크 로그를 보며 공부해보았다. CORS란? CORS란 Cross Origin Resource Sharing의 약자로 브라우저의 현재 웹페이지가 이 페이지를 받은 서버가 아닌 다른 서버의 자원을 호출하는 것을 의미한다. 이것을 허용하면 악의적인 도메인으로의 요청을 무조건 허용하게 되어 보안 문제가 발생할 수 있다. 그래서 HTTP 스펙에서 이에 대한 기준을 제시하고 있다. 나는 CORS를 ip만 같으면 ..

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

생각한 것 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를 사용하면 현재 인덱스..

내가 해본 걸 너에게 알려줄게 이 책은 이렇게 말하는 것 같다. “너 자바 배웠어? 잘알아? 써봤어? 그럼 이건 어때?”. 저자가 개발자로서 경험한 것들 중 도구로서의 사용법을 알려주는 듯 했다. 시중에는 자바의 문법이나 철학을 말하는 책이 많이 있지만 내가 원했던 건 그걸 실제 서비스에서 사용해보면서 부딪혔던 문제와 그 해결법을 자세하게 알려주는, 어찌보면 사소할 수 있고 어찌보면 가장 중요한 것일 수 있는 주제였다. 이 책은 그런 점에서 내 이목을 끌었고 다른 책들을 제쳐두고 내 책장에서 선택받았다. 지금도 자바를 사용하고 있고 하나의 프로젝트를 끝마쳐가는 즈음의 나에게 지금까지 해온 것들을 돌이켜보고 더 좋은 방법, 놓치고 있었던 포인트를 집어줄 수 있지 않을까 하는 호기심도 이 책을 읽게 되는데 ..