TIL💡(277)
-
[백준] 14658번: 하늘에서 별똥별이 빗발친다.
https://www.acmicpc.net/problem/14658 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 문제의 조건이 상당히 중요하다. 별똥별의 위치를 나타내는 좌표의 범위가 상당히 크다.(가로, 세로로 각각 50만..) 따라서 애초에 해당 좌표를 표시하는 2차원 배열을 쓸 생각을 버리고 시작해야 한다. 대신 별똥별의 개수가 최대 100개로 크지 않다. 따라서 별똥별을 일반 벡터에 있는 것으로 처리한다. 여기까지는 잘 풀었..
2022.09.04 -
[백준] 1253번: 좋다
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 자체는 어렵지 않지만 조건을 나누는 것이 상당히 까다롭다. 코딩테스트 풀 때도 이 문제 풀이 능력을 살리기 위해서 최대한 쉽게 코드를 짜려고 해보았다. 고려한 엣지 케이스 1. 0이 있는 경우 - 0, 3, -3 - 0, 1, 2 2. 음수가 있는 경우 - -1, -2, -4 3. 동일한 값이 여러 개 있는 경우 - 1, 1, 2 이 때문에 multiset을 썼다. 4. 복합적인 케이스 - 0, 0 3, 3, 3, 3 ..
2022.09.03 -
[백준] 4485번: 녹색 옷 입은 애가 젤다지?
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net DFS, DP 방법을 시도하였으나 결국엔 다익스트라로 풀면 깔끔한 문제이다. 참고로 DFS로 풀면 시간 초과가 발생한다..ㅠ 다익스트라 알고리즘은 한 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘으로서, 이 문제 또한 출발점이 [0][0]인 하나로 지정되어있기에 가능한 풀이이다. 대신 기존의 풀이방식과 달라서 처음부터 다익스트라로 푸는 것을 떠오르지 못했다. 왜냐하면 2차..
2022.09.03 -
[백준] 13549: 숨바꼭질3 with Deque
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이제 알고리즘 문제풀이 방식을 조금 바꿨다. 이제는 더이상 미리 문제 유형을 보지 않고 도전하기로 했다. 그리고 엣지 케이스를 스스로 찾는 능력을 키우기 위해 질문 게시판도 자제하기로 노력하기로! 아무래도 그동안 외부의 힌트를 구한 탓인지 혼자 알고리즘을 풀 때 제대로 문제를 해결해나가지 못한 경우가 많았기 때문이다. 이러한 전환의 첫 시작이 된 문제, 숨바꼭질3..
2022.09.02 -
[Programmers] 전화번호 목록 with Hash
https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이전에 푼 문제인데, 복습을 위해서 다시 정리해보았다. 서로의 번호를 매치하며 서로의 번호가 prefix인지를 확인한다. 하나는 prefix 번호, 다른 하나는 mateched 번호로 설정해서 이중 루프를 돌며 검색한다. 그런데 그렇게 되면 Hash가 아니라 일반 배열로 검색해도 되지 않을까? 라는 의문이 들 수 있다. 배열에서 matched 되는 번호를 매번 찾으면 시간 복잡도가 $O(N)$이다..
2022.08.03 -
[논문] BERT: Attention Is All You Need 읽기
AI 대회 2라운드 참가 전에 이번에는 BERT에 대해서 제대로 이해하면 좋을 것 같다는 생각이 들어 논문을 처음으로 읽어봤다. 덕분에 목적과 구조에 대해 조금 더 제대로 이해할 수 있었지만, 여전히 모국어가 아닌 논문이다보니 잘 이해하지 못한 부분이 있는 것 같아서 추가적으로 한국어로 된 자료를 찾아보았다. 굉장히 유용하고 상세하게 핵심을 잘 짚어주었기에 스크랩하였다. https://nlpinkorean.github.io/illustrated-transformer/ The Illustrated Transformer 저번 글에서 다뤘던 attention seq2seq 모델에 이어, attention 을 활용한 또 다른 모델인 Transformer 모델에 대해 얘기해보려 합니다. 2017 NIPS에서 Go..
2022.07.31