목록Algorithm (428)
Mini
[알고리즘] 백준 3190 뱀 // 덱 bfs, 구현, 뱀-꼬리 문제는 덱
https://www.acmicpc.net/problem/3190 * 풀이1(오답)한방향 (->) 진행만 구현후 회전함면 되는지? 안됨참고 : 시계회전은 a[i][j] = a[j][n-i-1] 임반시계 : [n-j-1][i]각 방향에 따라 dfs 돌기로함예제3에서오답 -> 표 디버깅 -> 회전시 꼬리의 위치갱신이 어려움꼬리가 (1,4) 였는데 바로 (2,4)로 되버림 // (1,5)가 되야 맞음꼬리의 상태를 어떻게해야 저장하지? -> 덱 * 풀이21-idx는 무조건 0-idx로 바꿔서 풀기!visit으로 몸통을 체크할것head가 지나가면서 visit을 기록하는 걸로 생각하면 쉬움.#include using namespace std;int sec,y,x;int n,k,L, a[104][104], vis[1..
[알고리즘] 백준 12100 Easy // 구현, 대칭구현은 한방향만 만들고 배열회전을 이용하라
* 시행착오제발 문제좀 읽자.앞부터 합쳐야 하므로 아래그림은 모두 틀린 풀이이다.그리고 한뱡향만 구현하고 회전을 이용하는게 훨씬낫다.틀린코드(초안)#include using namespace std;typedef long long ll;int ret;int n, a[24][24];void moveup() { for(int j=0;j v; for(int i=n-1;i>=0;--i) { if(a[i][j]==0) { continue; } if(i-1>=0 && a[i][j]==a[i-1][j]) { v.push_back(2*a[i][j]); --i; } else { ..
public class Main { // 1차원 배열 선언 static int[] arr = new int[100]; // 정수형 배열 static boolean[] visited = new boolean[100]; // 불리언 배열 static char[] chars = new char[100]; // 문자 배열 // 2차원 배열 선언 static int[][] board = new int[100][100]; // 정수형 2차원 배열 static char[][] map = new char[100][100]; // 문자형 2차원 배열 // ArrayList 선언 static ArrayL..
[알고리즘] 프로그래머스 요격시스템 // 그리디
https://school.programmers.co.kr/learn/courses/30/lessons/181188?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr * 풀이끝점기준 정렬끝점에서 미사일발사안되는경우( missile #include using namespace std;bool cmp(vector v1, vector v2){ return v1[1] > targets) { int ret = 1; // 첫 미사일 int n = targets.size(); sort(targets.begin(), targets.end(), cmp); ..
[맞음?] [알고리즘] 백준 2170 선긋기 // 라인스위핑은 정렬
https://www.acmicpc.net/problem/2170 #include using namespace std;typedef long long ll;int n,s,e,l,r,ret;pair p[1000000+4];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=0;i>s>>e; p[i]={s,e}; } sort(p,p+n); l=p[0].first; r=p[0].second; for(int i=1;i=p[i].first && r * 25.2.20. 2회독크게 3경우로 나눔포함하는경우,우측이 더 긴경우하나도 안겹치고 새롭게 시작 하는경우#includeusing namespace ..
[알고리즘, 틀림] 백준 1700 멀티탭 스케쥴링 // 그리디, 페이지 교체 알고리즘
https://www.acmicpc.net/problem/1700* 풀이1 vector, 배열에 삽입, 삭제 불편 -> unorder_set사용 (find O(1)임)find후 없으면 s.end를 리턴함최초로 찾은후 break 해야하는 이유#include using namespace std;typedef long long ll;ll n,k,ret;unordered_set s;int arr[104];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>k; for(int i=0;i>arr[i]; } for(int i=0;i#include using namespace std;int main() { // 입출력 최적화 i..
[알고리즘] 백준 1202 보석도둑 // 그리디, pq
https://www.acmicpc.net/problem/1202* 추론과정문제는 보석 도둑 문제인데, 각 보석은 무게와 가격을 가지고 있고, 가방에는 각각 최대 무게가 있어서 각 가방에 최대 한 개의 보석을 넣을 수 있다. 우리의 목표는 훔칠 수 있는 보석들의 최대 가격 합을 구하는 거다. 일단, 가장 먼저 생각나는 접근은 그리디 알고리즘일 것 같다. 왜냐하면 최적의 선택을 단계적으로 해나가야 하기 때문이다. 그리디로 풀기 위해서는 어떤 기준으로 선택을 해야 할지 결정해야 한다. 보석을 가격이 높은 순서대로 정렬하고, 각 보석을 담을 수 있는 가장 작은 가방에 넣는 방법이 있지 않을까? 예를 들어, 가장 비싼 보석부터 차례대로 해당 보석의 무게를 수용할 수 있는 가장 작은 가방에 배정하는 거다. 이렇게..
[알고리즘] 백준 1931 회의실 배정 // 그리디, 라인스위핑, 정렬
https://www.acmicpc.net/problem/1931* 풀이start로 정렬? -> 반례 -> 우디르end? -> 되네#include using namespace std;typedef long long ll;int n,ret;vector> v; // int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for (int i=0;i>a>>b; v.push_back({b,a}); } sort(v.begin(),v.end()); int endTime=v[0].first; ret++; for(int i=1;i