본문 바로가기

Algorithm12

[소프티어/Softeer] 나무 공격 C++ 문제 링크 : https://softeer.ai/practice/9657 틀린 코드- 시간 초과 떴음. for문 범위를 잘못 설정했음. 배열의 인덱스(0,1,2,...)와 번째 수(1,2,3,...)가 다르다는 거를 유의할 것.- 환경 파괴범의 위치를 2차원 배열에 굳이 다 저장할 필요 없고, 각 행에 몇 명 있는지만 저장하면 됨. g[n][m] 없애고 arr[n] 사용하도록 코드 고쳤음.- 숲의 요정이 지나가는 행에 있는 환경 파괴범의 인원이 1명 이상이라면 그 행들의 인원 수만 1씩 줄이면 됨. 공격이 두 번 시행되므로 이와 같이 인원 수를 줄이는 동작을 두 번 시행.#includeusing namespace std;int n,m, l,r, ll, rr;int main(void){ cin >> .. 2024. 11. 1.
[백준/BOJ] 2292번 벌집 C++ 문제 링크 : https://www.acmicpc.net/problem/2292 문제위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다. 풀이수열로 생각.1, 7(= 1+6), 19(= 1 + 6*1 + 6*2), ... 이런식으로 늘어남.N이 위치한 층의 번째 수 알아내면 됨.13은 2번째 항인 7보다 크고 3번째 항인 19보다 작은 수니까 13에 해당하는 값.. 2024. 10. 15.
[백준/BOJ] 23971번 ZOAC 4 언어 : C++문제 링크 : https://www.acmicpc.net/problem/23971 문제2021년 12월, 네 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 오프라인 대회를 대비하여 강의실을 예약하려고 한다.강의실에서 대회를 치르려면 거리두기 수칙을 지켜야 한다!한 명씩 앉을 수 있는 테이블이 행마다 W개씩 H행에 걸쳐 있을 때, 모든 참가자는 세로로 N칸 또는 가로로 M칸 이상 비우고 앉아야 한다. 즉, 다른 모든 참가자와 세로줄 번호의 차가 N보다 크거나 가로줄 번호의 차가 M보다 큰 곳에만 앉을 수 있다.논문과 과제에 시달리는 성우를 위해 강의실이 거리두기 수칙을 지키면서 최대 몇 명을 수용할 수 있는지 구해보자. 풀이w를 (1+m)로 나눈 몫과 h를 (1+n)로 나눈 몫의 곱으로 구할.. 2024. 10. 15.
[알튜비튜] 01. 정렬 대표적인 정렬 알고리즘 ∘ O(n^2) : Insertion sort, Selection sort, Bubble sort ∘ O(nlongn) : Quick sort, Merge sort, Heap sort 버블 정렬 (Bubble sort) ∘ 인접한 두 원소 비교 ∘ (왼쪽 원소) > (오른쪽 원소) 면 swap ∘ 가장 큰 원소부터 오른쪽에 정렬됨 ∘ 데이터가 하나씩 정렬되면서 비교에서 제외됨 * 2750번 : 수 정렬하기 여기서 시간 초과될지 안 될지는 어떻게 예상해? 합병 정렬 (Merge sort) ∘ 분할 정복(Divide and Conquer) 방식으로 설계된 알고리즘 ∘ 하나의 배열을 정확히 반으로 나눔 (Divide) ∘ 나뉜 배열들을 정렬 (Conquer) ∘ 다시 하나의 배열로 합치.. 2023. 7. 4.

티스토리툴바