본문 바로가기

알고리즘119

[프로그래머스] 디펜스 게임 c++ *O(nlogn)안에 풀어야 할 때 최소 힙 생각하기 풀이 1.최소 힙을 통해서 enemy 벡터를 앞에서부터 정렬해준다. 2. 최소힙의 사이즈가 k개가 넘어가면 최소힙의 제일 작은 원소 즉 0번째 값을 삭제하고 sum에 더한다. (top(), pop() 사용) 3. sum이 n보다 커지면 for문을 탈출한다. 이때 i값이 답. 모든 라운드를 막을 수 있을때는 enemy의 size 반환. **제일 큰 k개에 "무조건"을 써야되기 때문에 최대힙을 써야할줄 알았는데 최소힙을 써야했다. 왜냐하면 pop()을 할때 맨 앞에 있는 원소를 삭제하는데 제일 작은 원소를 삭제하기 위해서이다. #include #include #include using namespace std; int solution(int n, int .. 2023. 1. 1.
[백준] 1707 이분 그래프 C++ https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프라는 것을 처음 들어봤다. 두 집합으로 나누었을때 연결된 노드 끼리는 다른 집합에 속하는 것을 이분그래프라고 한다. 문제에서는 두 집합으로 나눈다고 하였는데 이것을 연결된 노드와 다른 색깔로 칠하는 것으로 표현할 수 있다. 1번 노드부터해서 각 노드를 bfs로 방문해준다. 각 노드에서 연결된 다른 노드들을 다른 색깔로 칠한다. 모든 노드를 방문하였으면 check함수를 통해서 인접한 노드.. 2022. 12. 29.
[백준] 14503 로봇 청소기 C++ https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 로봇 청소기가 움직이는 규칙은 위와 같다. 문제는 쉬웠는데 y축으로 움직이는 것을 반대로 설정해서 한참 해맸다. y-1하과 y+1을 반대로 했었다. -새롭게 알게된 것 : exit(0); - 프로그램을 종료하고 싶을 때 사용. 방문했는지를 알기위해 visit이라는 배열을 따로 사용했는데 다른 사람의 코드를 보니까 벽과 빈 칸을 입력받는 배열을 사용하여 방문한 자리는 -1로 바꿔서 풀었다. 또한 .. 2022. 12. 29.
[프로그래머스] 두 큐 합 같게 만들기 c++ https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 새롭게 알게 된 것 벡터 원소 더하기 #include accumulate(v.begin(), v.end(), 0); 삽질을 많이 했다. 첫번째는 큐 1과 큐 2 내에서 절반이 있는 경우를 찾고 그다음은 이어져서 있는 경우를 찾으려고 했는데 복잡하고 매번 합을 구해야 해서(O(n)) 시간 초과가 났다. 그래서 sum을 미리 구하고 빼고 더하는 방식(O(1))으로 바꾸려고 했는데 모든 경우의수를 구.. 2022. 12. 8.

티스토리툴바