baekjoon 5430 AC 5430번 AC 접근 vector풀려고 했는데 앞에서 지우는 방식이 없어서 포기했다. 찾아보다보니 deque라는 좋은 자료형이 있었다. double ended queue의 약자인 deque는 양쪽에서 삽입과 삭제가 가능하다. R로 방향 바꿀 때 실제 데이터의 방향을 바꾸지 않고 기록만 해두었다가 그 방향대로 출력만 ...

baekjoon 7569 토마토 7576번 토마토 접근 7576토마토의 3차원 버전이다. 원소 3개짜리 자료형을 queue에 넣기 위해 tuple이라는 것을 사용했다. 원소값 불러오는 방식이 pair에 비해 좀 다르다는 것 빼면 큰 차이 없다. 코드 #include <iostream> #include <vector> #in...

baekjoon 7576 토마토 7576번 토마토 접근 보자마자 딱 bfs 생각이 났다. level나눠서 했던 bfs가 생각나면서 같은 level에 각각 거리 1씩 더 탐색하는 방식이 떠올랐다. 초기에 익은 토마토가 여러개라면 그 토마토들과 모두 연결되어 있는 부모 토마토(node)가 있다 생각하면 완벽히 bfs 모양이다. 코드 #include...

baekjoon 1931 회의실 배정 1931번 회의실 배정 접근 회의실 배정은 유명한 그리디 알고리즘 문제이다. k-1번째까지만 greedy랑 optimal solution이랑 같다고 해보자. greedy는 항상 일찍 끝나는 것을 고르니 optimal solution의 k번째 회의보다 더 먼저 끝나는 k번째 회의를 가지고 있을 것이다. 그런데...

baekjoon 14940 쉬운 최단거리 14940번 쉬운 최단거리 접근 bfs 거꾸로 접근하면 된다. 조금 변형해서 상하좌우로 탐색하도록 했다. 코드 #include <iostream> #include <queue> using namespace std; int main(){ ios::sync_with_stdio(fal...

baekjoon 1620 나는야 포켓몬 마스터 이다솜 1620번 나는야 포켓몬 마스터 이다솜 접근 그냥 숫자 검색은 vector, 단어검색은 map으로 저장하면 되겠다 생각했는데 찾아보니 unordered_map(hashmap)이라는 것이 있었다. hash table을 이용해서 저장하니까 더 빨리 검색될 거 같았다. 코드 #include &lt...

baekjoon 10026 적록색약 10026번 적록색약 접근 연결되어 있는 것끼리 한 묶음으로 묵여야 하는데, 그 묶음의 개수를 세야겠다고 생각했다. CLRS공부하면서 dfs가 탐색하다가 더 없으면 점프해서 다른 묶음으로 넘어갔던 생각이 나서 dfs로 풀어서 몇 번 점프 했는지 세면 되겠다고 생각했다. 코드 #include <iostre...

baekjoon 16928 뱀과 사다리 게임 16928 뱀과 사다리 게임 접근 처음엔 dp로 풀고자 했다. \(dp(i) = 1 + min(\sum_{k=1}^{6}dp(i+k))\) 이런식으로 말이다. 그리고 a –> b로 가는 사다리가 있으면 dp(a) = dp(b) 이런식으로 예외처리 하면 될 줄 알았다. 하지만 이렇게 되면 사이클이 있...

baekjoon 7662 이중 우선순위 큐 7662번 이중 우선순위 큐 접근 정방향 우선순위 큐와 역방향 우선순위 큐를 통해서 풀 수 있겠다고 생각했다. 처음에는 수가 중복될 수 있다는 발문을 보지 못하고 큐 2개 만들고 그냥 어짜피 최대, 최소만 찾으면 되고 만약 최대와 최소가 크기가 반대가 되면 EMPTY반환, 이런식으로 만들었다. 하지만 그...

baekjoon 9019 DSLR 9019번 DSLR 접근 D, S, L, R연산 함수로 따로 만들어서 진행. 처음에는 vector에 계속 D, S, L, R연산한 결과를 추가해서 4k+i꼴로 full 4-ary tree를 만들 생각했음. 이렇게 하면 index계산만으로 문자열 뽑아낼 수 있다는 이점 생각함. 하지만 이렇게 하면 중복된 결과가 나...