거북이-https://velog.io/@violet_evgadn 이전완료

코딩 테스트 시 필요한 이유 정규 표현식(Regular expression;regex)은 특정한 규칙을 가진 문자열의 집합을 표현하는 형식 언어이다. 여러 프로그래밍 언어나 텍스트 편집기에서 정규 표현식을 통한 문자열 검색 및 치환 기능을 지원하고 있어 만약 자유자재로 활용할 수 있다면 매우 강력한 기술이다. 하지만 정규표현식은 "패턴"을 위한 형식 언어이기 때문에 "또 하나의 프로그래밍 언어"라고 할 정도로 문법이 복잡하다. (사실 필자도 정규표현식 문법을 검색하지 않으면 정규표현식을 제대로 활용하지 못한다.) 코딩 테스트에서 정규 표현식이 필수 지식은 아니다. 왜냐하면 프로그래밍 언어 또한 검색 기능의 함수가 많기 때문에 이들을 잘 조합하면 정규 표현식 비슷한 효과의 함수를 만들 수 있다. 하지만 정..

코딩 테스트 시 필요한 이유 BitMask는 코딩 테스트에서 많이 활용되는 기법은 아니다. 만약 BitMask를 활용해야 하는 문제라면 개인적으로는 다른 문제를 푸는 게 더 효율적이라 생각할 정도로 굳이? 싶은 기법이긴 하다. 하지만 개념 및 사용 방법을 알지만 효율을 위해 다른 문제를 푸는 것과 아예 몰라서 다른 문제를 푸는 것은 매우 다른 상황이라고 생각하기 때문에 한 번 정리해보겠다. 아래에 나오는 모든 수들은 10진법이 아닌 2진법이라고 간주하고 정리하겠다. 이후 어떻게 10진법에서 BitMask 기법을 활용할 수 있는지 언급하겠다. Shift 연산(>>, 2) | 1 // (origin >> 2) | 1 -> (00010) | 1 -> 00011 추가로 BitMask는 주로 배열 Index로 쓰..

Kruskal Algorithm 크루스칼 알고리즘을 구현한 이후 제대로 구현됐는지 확인하기가 어려워 백준 문제 중 하나를 푼다는 생각으로 구현했다. https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net class Edge implements Comparable { // p1 - p2 사이 간선 길이가 len. // len 기준 오름차순 정렬해야 하므로 Comparable 인터페이스를 상속시킴 int p1; int p2; int len; public Edge(int p1, int p2, int len){ this.p1 = p1; this.p..

Union-Find 알고리즘 Kruskal MST에서 사용되는 알고리즘 중 "Union-Find 알고리즘"이 존재한다. 이를 먼저 알아야 Kruskal MST를 구현할 수 있으므로 이 알고리즘부터 알아보자. ◎ Union-Find 알고리즘이란? Union-Find는 Disjoint Set을 만들 때 사용하는 알고리즘이다. Disjoint는 "분리된, 별개의"라는 뜻을 가지고 있다. Disjoint Set이란 "분리된 집합"이라는 의미로 교집합이 존재하지 않는 부분집합들을 조작 및 저장하는 자료구조이다. 모든 부분 집합 사이에 교집합이 없는 상호 배타적인 부분 집합들로 이뤄진 자료구조라 할 수 있다. ◎ Union-Find 연산 make-set(x) Set을 초기화하는 함수 x 자체가 하나의 부분 집합이 ..

코딩 테스트 시 필요한 이유 코딩 테스트에서 가장 많이 나오는 문제 유형이 문자열 처리 유형이라고 한다면 가장 어려운 문제를 꼽으라면 그래프 문제를 뽑을 것 같다. Trie를 활용하여 풀어야 하는 문제가 아닐 경우 문자열 처리 문제는 대부분 Lv3 정도의 문제에 속하지만 그래프는 Lv3 ~ Lv4 널리 퍼져있고 문제 난이도 자체도 꽤 어려운 편이라고 할 수 있다. 그래프 문제 같은 경우 종이의 사용이 한정되어 있는 코딩 테스트의 경우 상황을 상상하기가 힘들고 대부분의 그래프 문제의 해결 방법은 Brute Force 방식인 경우가 많아 난이도가 증가한다고 생각한다. 그래프는 이 Brute Force 방식을 얼마나 효율적으로 수행하는지가 중요해지고 이 때문에 이미 수많은 알고리즘이 존재하며 이를 모를 경우 ..

코딩 테스트 시 필요한 이유 트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조이다. 대학 수업 시간에 Tree의 문자열 형태라고 공부하긴 했지만 그 당시 난이도가 너무 높고 수업에서 중요한 비중을 두지도 않았기에 그냥 넘겼다. 그런데 카카오 코딩 테스트 4 Level을 풀다 보니 문자열 관련 문제는 대부분 Trie나 DP를 사용해야지만 시간 부족 문제가 발생하지 않았다. DP는 아이디어의 문제라고 하더라도 Trie는 개념을 모른다면 사용할 수조차 없었다. 따라서 Trie에 대해서 자세히 알아보고 직접 구현까지 해보기로 하였다. 트라이 작동 원리 문자열 집합 ["word","war","warrior","world", "go", "gone", "goto"]을 트라이로 구현한 것이다. 트..

코딩 테스트 시 필요한 이유 먼저 말하고 갈 것은 아래 내용들이 필수적으로 알아야 하는 메서드들은 아니다. 하지만 Collections에는 꽤 많은 편리한 메서드들이 구현되어 있는데 이를 코딩 테스트에서 직접 구현하고 있으면 당연히 에러 발생 가능성이 있을 것이다. 귀찮고 위험성 있는 작업을 줄이고 로직을 생각하는 데에만 집중하기 위해 미리 구현된 메서드 중 활용할 것 같은 것들을 골라내는 작업이 한 번쯤은 필요하다고 생각했다. 참고로 이전에 배웠던 "Collection"은 단순한 인터페이스이며 "Collections"는 Collection들을 다루기 위한 클래스라고 알고 있으면 될 것이다. Collections 메서드 ◎ Collection 중 최대(최솟값) 찾기 Collections.max(Colle..

코딩 테스트 시 필요한 이유 이전에도 말했듯 코딩 테스트에서 나올 확률이 가장 높은 문제는 "문자열 처리" 문제이다. 진짜 문제를 풀다보면 생각 그 이상으로 문자열 처리 문제를 많이 낸다. 문자열 처리에선 split같은 String 고유 함수도 중요하겠지만 StringBuilder 객체가 매우 중요하다고 말할 수 있다. 이유는 많지만 중요한 이유는 2가지라고 생각한다. 먼저 연산 속도의 문제이다. 일반적으로 String 문자열을 합칠 때 "String + String" 형식으로 "+" 연산자를 활용한다. 하지만 "+" 연산자를 통해 String 문자열을 합치면 성능도 떨어지고 메모리도 비효율적으로 활용된다. (이유는 아래에서 자세히 알아보자) 2번째 문제는 String 객체의 경우 Index에 해당하는 ..

코딩 테스트 시 필요한 이유 코딩 테스트를 풀면서 생각보다 "char[] charArr"를 사용하는 경우가 많았다. 대부분 char[] charArr = str.toCharArray() 처리를 한 뒤 푸는 문제였다. 이 경우 2가지 처리 방법이 필요했는데 "배열을 Collection로 만들기"와 "char 배열을 String으로 만들기"이다. 물론 for문을 통해 charArr를 순회하거나 charAt() 메서드를 통해 글자 하나씩 Collection에 넣는 방법도 있겠지만 이전에 사용했던 "Stream"을 활용하고 싶은 욕구가 컸다. 마찬가지로 char 배열을 String으로 만드는 것도 StringBuilder를 사용하는 것이 아닌 바로 String 데이터로 만들고 싶었다. 따라서 이 2가지 방법을 ..

코딩 테스트 시 필요한 이유 필자는 Brute Force 방식으로 코테를 푸는 것에 대한 거부감이 있었다. 말이 좋아 Brute Force 방식이지 가볍게 말하면 일일이 세보자라는 알고리즘이고 대기업들은 코테로 이런 단순한 알고리즘 문제를 내지는 않을 것이라 생각했기 때문이다. 하지만 프로그래머스에 있는 코딩 테스트 문제를 풀어보며 생각보다 Brute Force 방식으로 풀어도 되는 문제들이 많았다. 특히 Lv2 같은 쉬운 문제들은 대부분 Brute Force 방식을 사용하고 있었다. 이렇다보니 대기업도 Brute Force 방식으로 문제를 풀도록 하는 경우가 있구나라는 생각으로 바뀌었다. 개인적으로 Brute Force 방식 중 가장 까다로웠던 것이 "조합과 순열"을 구현하는 것이었다. 원래는 이런 B..