본문 바로가기

분류 전체보기361

Trie (트라이 자료 구조) 본인이 이해하기 위해 작성한 글입니다. 이 포스팅은 트라이가 뭔지는 알겠는데 막상 짜려면 기억이 잘 안나시는 분이 보면 유용할 것입니다. 링크: www.notion.so/Trie-875eeb41921f4559b87a38f1e4136e7e 틀린 내용이 있다면 피드백 주시면 감사하겠습니다. 2020. 8. 6.
[BOJ]16397번: 탈출 문제: https://www.acmicpc.net/problem/16397 단순 BFS 문제입니다. 중복 방문하지 않도록 이미 탐색해본 숫자는 VISITED 배열에 저장해주면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ16397.java 2020. 8. 6.
[2020 카카오 인턴십] 경주로 건설 문제: https://programmers.co.kr/learn/courses/30/lessons/67259 https://codingjuny.tistory.com/41 위 출처를 참고하여 "비용"으로 BFS를 돌려야한다는 아이디어를 얻었습니다. 경주로를 설치하면서 식별할 수 있는 정보는 3가지입니다. 그래서 저는 상태공간을 VISITED[DIR][N][N] 으로 선언하였습니다. VISITED[DIR][N][N] 정의: DIR 방향으로 N,N좌표에 도로를 놓는 최소 비용 방향, Y좌표, X좌표 (방향 정보가 있기 때문에 Y,X, 좌표 하나만 가지고 움직여도 경주로를 표현할 수 있습니다.) 도로를 설치하면서 모든 방향을 탐색해봐야 합니다. (단, 현재 진행하던 방향과 반대방향은 무한 루프에 빠지게 되니 그.. 2020. 8. 4.
[006]Valid Palindrome 문제: https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3411/ 팰린드롬 찾기 문제입니다. 숫자와 영문자를 제외한 나머지 문자는 제외하고 팰린드롬인가를 물어보는 문제입니다. 맨 처음에 재귀로 풀었는데 생각보다 테케 문자열이 깁니다. 그러므로 재귀로 풀면 TLE이 납니다. 그래서 저는 deque를 활용하여 팰린드롬을 체크하였습니다. HEAD와 TAIL이 일치하면 계속 빼주다가 deque 사이즈가 1 또는 비게 되면 그 문자열은 팰린드롬입니다. class Solution { public: deque dq; bool isPalindrome(string s) { strin.. 2020. 8. 3.

티스토리툴바