본문 바로가기

전체 글

 (189)
[알고리즘] 미로탈출 https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=cpp 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 간단한 BFS문제입니다. 특이점이라면 시작점에서 레버까지한번, 레버에서 도착지까지 한번 두번 BFS를 해야한다는 점이겠네요 이것을 모듈로 분리하는 것이 좋아보이긴 하지만 저는 일단 그냥 별도로 했습니다.using namespace std;int N, M;struct Point{ int r, c, dist;};int solution(vector maps) { int answer = 0; N = maps.size()..
[알고리즘 풀이] 구명보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr간단한 그리디(투포인터) 문제입니다. a + b를 합쳐 n에 가까운 수를 만들어야합니다.배열의 최대크기가 5만이기 때문에 하나하나 찾아 배열에서 제거하더라도 시간초과가 나지는 않겠지만 투포인터 방식으로 풀면 간단하면서도 빠르게 해결할 수 있을 것입니다. 투포인터를 위해 먼저 people을 정렬한 후 limit에 부합한다면 포인터를 움직여가는 식입니다. #include #include #include using namespace std;int solutio..
[쿼리] 부모의 형질을 모두 가지는 대장균 찾기 분화 시작 개체 = 부모 개체 분화가 된 개체 = 자식 개체 부모의 형질을 모두 보유한 대장균의 ID, GENOTYPE, PARENT_GENOTYPE 을 출력해야합니다.ID, PARENT_ID, SIZE_OF_COLONY, DIFFERENTIATION_DATE, GENOTYPE (개체ID, 부모개체ID, 개체 크기, 분화 날짜, 개체 형질) 입니다. GENOTYPE 십진수를 이진수로 바꿔서 계산해야합니다. 예를 들어 5라면 101, 3이라면 11과 같이 생각해 PARENT의 GENOTYPE과 CHILD의 GENOTYPE을 계산해야됩니다. 다만 비트연산자를 사용한다면 쉽게 계산할 수 있겠네요 비교를 위해서는 parent table, child table로 나눠 join해야합니다. SELECT CHIL..
[알고리즘] 괄호 회전하기 https://school.programmers.co.kr/learn/courses/30/lessons/76502 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 평범한 스택문제입니다. 괄호하면 바로 스택이 떠오르죠 '['가 top이라면 ]가 들어왔을 때 pop을 하는 등의 여러 응용을 하게됩니다. 해당 문제는 기본적인 괄호 stack문제에서 순환 키워드만 들고왔습니다. 단순히 인덱스를 순회하면서 같은 함수를 타게 만들어주면됩니다. 더 최적화할 수 있겠지만 빠르게 코딩해보았습니다.#include #include #include using namespace std;bool check(string& s, int s..
[알고리즘] 붕대 감기 https://school.programmers.co.kr/learn/courses/30/lessons/250137 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr간단한 구현문제입니다. 문제의 조건을 읽고 실수하지 않는 것이 가장 중요하겠습니다. // t초 붕대를 감는다.// 1초마다 x씩 회복하며 성공한다면 y만큼 추가로 회복한다 = t*x+y// 공격을 받으면 중단당함// bandage = [시전시간, 회복량x, 추가회복량y]// attacks = [공격 시간, 데미지] 의 배열라는 특성을 가지고 있습니다. 따라서 공격을 당하면 회복을 하지 않고 멈추기 때문에 이에 대한 제어 순서를 정해야하며, 전체의 시간흐..
[1일 1알고] 가사 검색 https://school.programmers.co.kr/learn/courses/30/lessons/60060 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr이번 문제는 Trie를 활용하는 문제입니다. 문제에서는 특정 단어들에 대해 검색을 할것이며 이 때 ?(와일드카드 문자)가 들어갈 수 있습니다.다만 ?는 접두 혹은 접미사로만 붙을 수 있기 때문에 문제의 해결이 쉬워집니다. 일단 조건을 보았을 때 각 단어에 대해 무작정 찾는 것은 불가능할 것임을 알 수 있습니다. 이를 위해 Trie를 사용합니다. Trie에 필요한 정보는 다음과 같습니다.1. 현재 Trie Node에 들어가는 문자 ch2. 현재 Trie N..
[1일 1알고] 표 병합 https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr1일 1알고라고 이름을 정해놓고서 매일 올리지 못하고 있네요 오늘은 union-find를 응용하는 문제입니다. 표가 주어지고 이에대한 명령어를 수행하는 문제입니다. 명령어로는 UPDATE, MERGE, UNMERGE가 있습니다. 다행히도 표가 50x50 크기로 정해져있기 때문에 UPDATE를 할 때 완전탐색을 하더라도 시간적으로 문제는 없을 것입니다.다만 MERGE, UNMERGE는 그룹의 전체를 바꾸는 것이기 때문에 어떻게 해결할지에대한 솔루션이 필요..
[1일 1알고] 공 이동 시뮬레이션 https://school.programmers.co.kr/learn/courses/30/lessons/87391 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr이동을 위한 쿼리와 목적지가 주어지고, 목적지로 도달하기 위한 출발지의 개수를 구하는 문제입니다. 조건을 보면 알다시피 n, m이 이미 10^9이기 때문에 절대로 하나하나 계산해서 문제를 풀 수는 없을 것입니다. 그렇다면 보통 이런 문제는 도착지에서 쿼리를 역산해나가면서 범위를 체크하는 것이 일반적일 것입니다.다만 문제가 있다면 범위를 어떻게 설정할지겠죠일단 x, y의 시작 끝 범위를 각각 지정해야하기 때문에 저는 sx, ex, sy, ey로 지정했습니다..

티스토리툴바