전체 글
-
6. KMP, Knuth-Morris-PrattCS/Alogrithm 2020. 6. 19. 18:30
대표적인 문자열 처리 알고리즘 중 하나인 KMP를 소개해보려 합니다. 알고리즘 이름은 해당 알고리즘을 고안한 분들의 이름을 따서 만들어졌습니다. 문자열 관련 알고리즘 또한 다양한데요. 해당 알고리즘은 문자열 A를 기준으로 문자열 B에 포함된 개수를 찾는 것이 핵심입니다. 해당 알고리즘의 대표 문제인 찾기(백준 1786번)에도 관련 내용에 대한 설명이 나와 있습니다. 알고리즘을 이해한 후에 해당 문제도 한번 풀어보시면 좋을 것 같습니다. 간단한 예시를 들면 아래와 같은 문자열에서 문자열 A가 총 몇 개 포함되어 있는지 찾는 문제입니다. 문자열 B: Apple is not green Apple but, red one. 문자열 A: Apple 역시나 눈으로 찾긴 쉽습니다. 간단하게 2개가 바로 보이네요. 컴퓨..
-
5. LCA, Lowest Common Ancestor (최소 공통 조상)CS/Alogrithm 2020. 3. 5. 17:28
몇 달간 많은 일이 있었습니다. 수료도 했고, 해외 연수와 CES 참관... 스프링 인강, 알고리즘 스터디 등등.. 그중에 소마 친구들과 같이 알고리즘 스터디를 하다가 공부하게 된 LCA라는 알고리즘을 소개해볼까 합니다. LCA는 기본적으로 트리에서 사용되는 알고리즘입니다. 간략하게, 트리에 대한 내용은 트리와 그래프 포스팅을 참고해 주세요. exponential-e.tistory.com/33 트리와 그래프 컴퓨터공학 전공 중이시라면 당연히 두 자료구조의 이름은 들어보셨을 겁니다. 하지만 뭐.. 저는 학교 다니면서 그 차이점에 대해 전혀 알지 못했었는데요. 그렇게 여러 문제를 접하며 박살 exponential-e.tistory.com 일상생활에서 트리구조는 족보 또는 가계도를 예로 들을 수 있습니다. 이..
-
트리와 그래프CS/DS & OOP 2020. 3. 5. 14:46
컴퓨터공학 전공 중이시라면 당연히 두 자료구조의 이름은 들어보셨을 겁니다. 하지만 뭐.. 저는 학교 다니면서 그 차이점에 대해 전혀 알지 못했었는데요. 그렇게 여러 문제를 접하며 박살이 난 후에야 그 중요성을 알게 되었습니다.. 하하; 그래서 이 글에선 문제를 제대로 이해하기 위해선 반드시 정의와 그 차이를 알아야 하는 두 자료구조에 대해 알아보겠습니다. (가볍게 어떤 것이고 이런 차이가 있다 정도로만 짚고 넘어가보겠습니다. ㅎㅎ) Tree? 트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. (참고: wiki) Graph? 그래프는 일부 객체들의 쌍들이 서로 연관된 객체의 집합을 ..
-
4 - 1. Disjoint-set 예제 (10216번: Count Circle Groups)CS/ProblemSolving 2019. 11. 29. 17:54
백준 10216번(Count Circle Groups) 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net SW Maestro 10기가 끝났습니다. 최종 결과 나올 때까지 오지게 문제만 풀려다가, 서로소 집합 관련 문제를 올리려 했던 게.. 기억나서 부리나케 왔습니다. ㅎㅎ 따로 분류는 안되어있지만, 저는 서로소 집합으로 해결한 문제를 가져왔습니다. '배열로 처리해서 바로 인접한 그룹의 개수를 센다.'라고 생각하실지도 모르겠지만, 시간 복잡도만 생각해보아도.. 살짝 위험해 보입니다. 또한 인접하..
-
4. Disjoint-set, Union-find (서로소 집합)CS/Alogrithm 2019. 5. 22. 22:05
SW 마에스트로 합격 이후로 정신없이 지내서.. 이제야 글 하나를 씁니다. 올해는 이 글이 마지막 글이 될 것 같아요... (그래도 가능하면 관련 문제에 대한 글 한두 개 정돈 쓰도록 하겠습니다.) 오늘 설명드릴 알고리즘은 서로소 집합입니다. Union-find, Disjoint-set 모두 서로소 집합을 의미하는 용어인데요. 후자가 좀 더 의미에 와 닿는 것 같아요. 사실 이 알고리즘에 대한 설명을 쓸지 말지 고민을 많이 했습니다. 제가 가장 좋아하는 알고리즘(이를 응용한 MST 포함해서요) 중 하나인데요. '이렇게 글을 쓸 정도로 잘 알고 있나?' 라고 생각을 해보면 그건 아닌 것 같아서요. 최대한 자세하게 적도록 해볼게요. DisJoint-Set, Union-find 말 그대로 서로소 집합입니다. ..
-
1. SWM(Software Maestro) 10기 면접까지 간략 후기Daily 2019. 4. 2. 17:44
뭐.. 자랑 글입니다...ㅋ 어찌어찌하다 보니 10기 연수생으로 들어가게 되었습니다. ㅎㅎ 아 대표 이미지는 이 글의 내용과 관련은 없습니다. 제가 문제 푸는 사이트에서 아도겐 코드로 풀다가 입력 잘못받아서 삭제해버린.. 마음 아픈 추억이 담긴 이미지입니다.ㅠㅠ 추후에 지원하실 분들에게 조금이나마 도움이 되어보자라는 생각으로 몇 자 적어봅니다. 저는 정말 일말의 기대 없이 지원했기 때문에 저에 대한 내용을 매우 사실적으로 표현하고 진심을 다해서 임했었습니다. (사실 조금의 부풀려 말하는? 이런 것들이 필요하다고들 하는데.. 대부분의 지원서 쓸 때나 면접 볼 때든 말이죠.) 1. 지원서 작성 기대는 안 했다고 해서 대충 쓰진 않았습니다. 말씀드린 대로 사실대로 제 현황을 적었고 제 생각들을 차분히 써 내려..
-
3 - 1. Eratosthenes' Sieve 예제 (1963번: 소수 경로)CS/ProblemSolving 2019. 3. 30. 19:13
백준 1963번(소수 경로) 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 안녕하세요.. 후 요즘 지원서 쓰고 코딩 테스트 본다고 정신이 없네요.ㅠㅠ 자주 글을 올려야 하는데... (자주.. 올려볼게요..) 엇! 근데, 잠깐 안한거같은데.. 많은게 바뀌었네요. ㅎㅎ (티스토리 짱짱맨!) 본론으로 넘어가서... 이 문제는 소수를 탐색하는 문제입니다. 일반적인 예제에서 에라토스테네스의 체만 쓰기엔 좀 아쉬워서 BFS에서 응용하는 문제를 가져와봤습니다. 문제 설명 자체가 한눈에 확 들어오진 않습니다.. 그 와중에 정말 다..
-
3. Eratosthenes' Sieve (에라토스테네스의 체)CS/Alogrithm 2019. 3. 26. 21:03
소수 판별 알고리즘은 정말 많은데요.그 중에서도 가장 많이 쓰이고 간편한 '에라토스테네스의 체'입니다. 어떤 수 N에 대하여, 소수 판별하는 코드를 만들때 가장 나이브한 방법은 2부터 N까지 하나씩 다 나눠 보는 방법이 있습니다. 소수판별.java(Naive)12345678910111213141516171819import java.io.BufferedReader;import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = I..