전체 글
-
[BOJ] 14725번 - 개미굴 (Trie 자료구조 )BOJ 2021. 3. 11. 22:49
이번에 포스팅 하게 된 것은 바로 문자열 알고리즘 중 하나인 Trie 자료구조 이다. 맨 처음에 뭔지 모르고 있다가 한 번 알게 된 뒤로 신기하고 기억해두면 좋을 것 같아 한 번 글로써 정리 해보았다. 간단하게 말하자면 문자열 검색시 시간복잡도를 문자열의 길이인 M 즉 O(M)만큼 줄여주는 자료구조이다. 예를들어 여러개의 단어들이 있다고 가정하자. ["ABC", "ABCD", "ABD", "ACBD", "ACD"] 의 단어들이 있다고 보겠다. 트라이 자료구조에서는 이 문자열들의 저장 형태는 아래의 그림처럼 저장이 된다. (하위 코드도 참조) 먼저 첫번째 원소인 "ABC" 를 대입 해보자. 파이썬의 경우에는 dictionary를 이용하여 구현 할 수 있게 되고, C언어의 경우 포인터를 활용해서 구현 해놓은..
-
[BOJ] 1238번 - 파티BOJ 2021. 3. 9. 22:00
아는 형과 같이 알고리즘을 풀다가 이 문제에서 좋은 것을 배워 포스팅 해보려고 한다. 배운 만큼 블로그도 한 번 홍보해보겠다. (좋은글 많아요~!) degurii.tistory.com/ 데구리 블로그 웹 개발과 알고리즘을 공부합니다. degurii.tistory.com 다시 본론으로 돌아가 보자. 단순히 문제만 봤을 때는 다익스트라 혹은 플로이드 와샬 알고리즘으로 풀 수 있을 것 같아 안 풀고 넘어가려고 했지만, 아는 형 말을 듣고 얼른 기억 해놨다가 오늘 풀게 되었다. 물론 실제로 다익스트라로 이 문제를 풀 수 있을 것 같지만, 점의 제한 개수가 많아지거나 한다면 시간이 좀 빠듯할 수 있다. 플로이드로 풀기엔 O(N^3) 이기 때문에 시간 초과가 날 것이다. www.acmicpc.net/problem/..
-
[BOJ] 2096번 - 내려가기BOJ 2021. 3. 9. 01:30
solved.ac 에서 클래스 관련해서 새롭게 업데이트 되면서, 단계별로 문제를 풀어보는 중이다. 마땅히 좋은 문제들이 없고, 대부분 포스트 했던 문제이거나 쉬운 구현 문제들 이었기 때문에 오늘에야 블로그를 쓰게 된다. 이번에 풀어볼 문제는 간단한 dp 문제였고, 메모리만 잘 해결하면 되는 문제였다. 메모리에 관해서 블로그 글을 쓴 적이 없다고 생각해서 이번 글을 적게 되었다. www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 프로그래머스에서 비슷한 문제를 풀어 봤던 것 같..
-
[SW 마에스트로] 12기 1차 코딩 테스트 후기코테 및 면접 후기 2021. 3. 7. 00:22
백준 사이트에도 홍보가 올라왔고, 아는 형이 SW마에스트로를 2019년도에 했었던 적이 있다. 추천을 해줘서 지원한 것도 있고, 코딩테스트 경험을 쌓아보고자 지원한 것도 있다. 코테보는 전날 친구 4명이 우리집에 자서 혼란 속에서 봤던 것 같다... 중간중간에 밥도 먹으면서 서둘러 풀었던 것 같다. 어쨋든, 결론은 첫번째 관문을 통과 했다!! (^오^) 작년 후기들을 보면서 어떤 유형의 문제들이 나오는지 한 번 봤는데, sql 부터 web 개발까지 다양하게 나왔었다. 이번에도 역시 비슷하게 나왔다. 총 8문제에서 알고리즘(6문제) + SQL(1문제) + web(1문제)로 나왔다. SQL 문제는 어렵진 않았는데 배웠던 내용이 자꾸 헷갈리기도 해서 디버깅하는데 시간을 좀 썼다. WEB관련 문제는 미디어 쿼리..
-
[Spring] 왜 백앤드 개발자가 되고 싶은지JAVA/Spring Boot 2021. 3. 4. 20:27
웹 개발을 많이 해본 것은 아니지만 클라이언트, 서버를 다 개발을 해 본 경험은 있다. 디자이너와 협업으로 프론트 개발을 했을 때는 디자인 적으로 수정할 것들이 많았고, 리액트를 활용했기 때문에 상태관리 부분에서 힘들었던 것 같다. 물론 개발은 native로 해서 이것저것 많이 찾아보면서 완성 시켰다. 서버 개발은 많이 해본 적은 없지만 배포까지 Node js(express)를 활용해서 사이트를 만들어 본 적이 있다. 원하는 데이터를 던져주고 배포하는 단계까지 공부량이 좀 많았지만, 배포까지 완성 했을 때의 희열은 잊지 못했다. 둘 다 깊게 해본 것은 아니지만, 프론트에서 상태관리를 어떻게 효율적으로 할 지 고민을 했던 적도 있고, 디자인을 할 때 어떤 식으로 해야 유지 보수가 쉽게 될 지, API 문서..
-
[BOJ] 1766번 - 문제집BOJ 2021. 3. 4. 17:36
최근 코테를 본 SW마에스트로에서 위상정렬 관련 문제가 나와서 알고리즘을 공부한 뒤 여러 문제들을 풀어봤다. 위상정렬에서는 충분한 조건이 주어지지 않으면 답이 여러가지가 나올 수가 있는데 이 과정에서 (항상 ~ 가 작은 순서로 한다) 등의 조건이 주어졌을 때 어떻게 해야할 지 잘 알려주는 문제이다 예를 들어 사람 3명이 옆의 조건을 만족하여 출력한다고 해보자. 2번이 1번보다 앞에 나와야 한다. 이 조건을 만족하도록 줄을 세울 때, 정답은 [ 2, 3, 1 ], [ 2, 1, 3 ], [ 3, 2, 1] 이런식으로 여러가지 답이 나올 수 있다. 하지만 여기서 위의 조건을 만족하고 가능한 나이가 많은 순서대로 출력한다고 생각하면 ( 가정 1 < 2 < 3 ) 답: [ 3, 2, 1 ] 이 될것이다. 이와 ..
-
[KAKAO] 순위검색 (2021 KAKAO BLIEND)KAKAO/level 2 2021. 3. 1. 18:53
한 달전 부터 일주일 간 계속해서 이 문제를 풀기 위해서 도전했지만.... 시간초과와 자료구조를 어떻게 해야할 지 몰라 굉장히 어려웠다. 뭔가 카카오 문제들은 스스로 풀어보고 싶었고, 대부분 이런 구현 관련 문제였기 때문에 더욱 그랬다. 오늘 이 문제를 풀 것이라 다짐하고 앉아서 곰곰히 생각해봤지만, 도저히 엄두가 안 났던 것 같다. 생각해낸 무식한 방법들이 있었지만 '설마' 라고 생각만하고 말았던 것이다. (물론, 내가 푼 풀이와 같지는 않았다.) 그래서 조언을 얻고자 친구한테 힌트를 달라고 했다.. 내 궁금증을 바로 풀어주는 힌트였기도 했고 사실상 문제를 출제한 사람의 의도이기도 했던 것 같다. 받은 힌트 : 'java backend junior chicken' 으로 들어온 information 을 ..
-
[BOJ] 9466번 - 텀 프로젝트BOJ 2021. 3. 1. 04:17
어제 SW마에스트로 코딩 테스트를 보면서 다시 한 번 좀 더 많은 문제를 풀어봐야겠다고 생각했다. 자바 문법도 공부하고 있고, 창업 활동에서 했던 프로젝트 디자인 수정도 해야해서 정신이 없기도 하지만 알고리즘은 꼬박꼬박 푸는 중이다.. SW마에스트로도 몇 문제 더 풀었지만 알고리즘을 쓸 것 없이 완전 구현 문제였기 때문에 포스트를 굳이 하지 않기로 했다. 물론 구현 중 어려웠던 부분이 있더라면 쓰게 될 것 같다. 이번 문제에서는 dfs 부분(약한 부분이라 생각)의 문제를 한 번 풀어봤다. 70% 에서 시간 초과 계속 나서 결국 블로그들을 찾아 해결했다.. 아직까지 어떤 부분에서 답지를 보며 스킬을 익히는것이 더 이득이고, 그렇지 않은 지 정확히 모르겠다. 어떤 사람은 답지를 보는게 좋다고 말하곤 한다. ..