재원블로그 재원블로그

select distinct ID, EMAIL, FIRST_NAME, LAST_NAMEfrom DEVELOPERS as D left join SKILLCODES as S on (D.SKILL_CODE & S.CODE) > 0where CATEGORY = 'Front End'order by ID asc;이 문제는 Join을 이용한 문제이지만, MySQL에 비트 연산이 있는지 몰랐다면 못 풀었을 문제이다. 2의 제곱수에 따라 정해진 스킬에 대해 & 연산을 수행하고, 만약 맞는 조건이 있다면 0보다 클 것임을 조인 조건으로 걸어 문제를 풀었다.

이 문제는 bfs를 이용해서 풀었다. 일단 입력 배열의 크기가 4 * 4로 작아 완전 탐색과 같은 방법으로 풀 수 있음을 예상하고 문제를 풀었다.백트래킹으로도 문제를 풀 수 있는데, 최소를 구하기 위해 모든 경우를 무조건 탐색해야 한다는 점에서 시간 초과가 날 수도 있다고 생각했고, bfs로 풀기로 결정했다. 수레가 교차해서는 안되고, 같은 곳에 두 개가 동시에 있지 않게 하기 위해서 두 수레를 따로 움직이고, 이를 한번에 큐에 푸시하는 방식으로 구현했다.여기서 주의할 점은 블루가 먼저 움직이고, 레드가 나중에 움직이는 식으로 무조건 순서를 고정해놓으면 오답이 나올 수도 있다는 점이다. 따라서 블루가 먼저 움직일 때, 레드가 먼저 움직일 때 모두 큐에 넣어주는 방식을 사용했다.또한 Node의 visite..

이 문제는 그리디 알고리즘으로 풀었다. 이 문제에서 핵심은 카드를 버리지 않는 것이다. 즉, 버리는 대신 어딘가 저장해둔 뒤에 필요할 때 코인을 주고 쓰는 것이다.이걸 인지하면 문제가 매우 쉬워지고, 단순 구현 문제로 바뀌게 된다. 그리디 알고리즘이 적용되는 부분은 N + 1을 만들 때 적용되는데, 우선순위를 다음과 같이 해서 문제를 풀었다.1. 내가 가진 카드만으로 n + 1 만들 수 있을 때2. 버린 덱에서 한 장 + 내가 가진 카드 한 장으로 만들 수 있을 때3. 버린 덱에서 두 장 모두 가져와야 할 때 매 라운드마다 카드를 두 장 뽑을 수 있는데, 바로 discard set에 넣어서 구현을 단순화했다. 주의할 점은 루프가 다 돌아서 끝나는 경우에는 answer + 1을 해줘야 한다는 점이다.#in..

이 문제는 BFS를 이용해서 풀었다. 이 문제에서 관건은 한 번만 꺾이는 경로를 찾는 것, 모두 없앨 수 있을 때 알파벳 순으로 빠른 순으로 출력하는 것이다. 한 번만 꺾이는 경로에 대해서는 Node 구조체를 만들어 y, x 좌표와 함께 방향, 꺾인 카운트를 추가하여 BFS로 구현할 수 있었다. 알파벳 순으로 빠른 순으로 출력하는 부분에 있어서는 약간의 생각이 필요했다.그러나 만약 A와 C가 동시에 경로가 존재하고, 이를 순서를 바꾼다고해서 뒤의 결과에 영향을 주지 않는다는 것을 알게 되었다.어떤 알파벳이 사라짐으로써 경로가 생길 수도 있지만, 이는 순서와 상관없이 그 알파벳이 없어지기만 한다면 경로가 생기기 때문이다.따라서 알파벳 순서로 루프를 돌면서 가장 먼저 제거할 수 있는 부분이 생기면 즉시 제거..

이 문제는 맵과 다이나믹 프로그래밍을 이용해서 풀었다. 이 문제를 처음에 그리디로 접근하려다가 다이나믹 프로그래밍 문제임을 알게 되었다.왼손과 오른손 모두 똑같은 가중치로 특정 숫자에 갈 때가 문제였는데, 이 때 임의의 손을 선택하게 된다면 다음 숫자들에 대해 결과가 달라지기 때문에 그리디로는 풀 수 없다. 따라서 완전 탐색을 사용해야하는데, 왼손이 위치하는 숫자, 오른손이 위치하는 숫자, 현재 숫자(눌러야하는 숫자) 총 세 개의 파라미터를 통해 하나의 독립적인 상태를 만들 수 있었다. 따라서 다이나믹 프로그래밍으로 속도를 빠르게 만들 수 있어 문제를 해결할 수 있었다. 이 문제에서 가장 까다로웠던 것은 키패드의 위치와 숫자를 매칭하고, 최단 거리를 찾는 로직 두 개였다. 키패드의 위치와 숫자를 매칭하는..

이 문제는 구현 문제이다. 문제 제목 보고 1억 * 1억 배열이라 다른 방법을 사용할 줄 알았는데 입력으로 주어지는 e가 최대 5백만이라 배열로 만들 수 있었다. 가장 처음 나오는 이중 for문에 5,000,000을 넣고 카운트해보면 약 7,800만 정도의 연산을 수행하게 된다. 따라서 1초 안에 cnt를 모두 셀 수 있다. 범위를 세는 부분이 언뜻 시간을 초과할 것처럼 보이지만, starts 배열을 내림차순 정렬한 뒤 각 루프마다 구간을 계산하면 이전 결과를 활용할 수 있어 O(N)이면 해결된다. 이 때 정렬을 해도 원래 위치를 알 수 있어야 하기 때문에 pair를 사용하였다. #include #include #include #include #include using namespace std; #def..

이 문제는 bfs, 트리를 이용해서 풀었다. 이 문제에서 노드의 수가 n일 때 간선의 수가 n - 1개이고, 모든 임의의 두 점은 연결되어있으므로 입력 그래프는 트리이다. 트리는 아무 점이나 루트로 잡아도 트리이므로, 1을 루트로 잡았다. bfs를 이용해서 노드들의 depth를 계산한다. bfs 이후에는 depth가 깊은 순서대로 내림차순 정렬 후 루프를 돌린다. depth가 가장 깊은 리프 노드부터 자신의 부모를 확인한다. 이 때 자신이 이미 켜져있는 경우에는 continue한다. 만약 자신의 부모가 등대가 켜져있지 않다면 켜주고 answer++하는 방식으로 정답을 구할 수 있다. 문제에서 입력 그래프가 트리일 경우에는 bfs나 dfs를 이용한 풀이가 적용되는 경우가 많았던 것 같다. #include ..

이 문제는 bfs와 백트래킹을 이용해서 풀었다. 우선 단순히 상하좌우, Ctrl + 상하좌우 총 8가지 움직임이 가능하다. visited와 같은 방문 여부 배열을 처음부터 사용할 수는 없다. 하나의 쌍을 완료한 후에 다음 최단 거리를 위해서는 이미 방문했던 위치로 또 가야할 수 있기 때문이다. 따라서 단순히 완전 탐색을 수행하면 O(8^N) 이 되므로 N이 9만 되어도 1억이 넘어가게 된다. 생각을 다시 해본 결과 전체 로직을 bfs로 넣을 수는 없지만, 일부 로직에서는 bfs를 적용할 수 있다는 생각을 하게 되었다. 한 점에서 단순히 다른 점으로 이동하는 데에는 bfs를 이용해서 최소 비용을 구할 수 있기 때문이다. 그래서 움직임을 담당하는 함수 minMove() 를 통해 한 점에서 다른 점으로 이동하..