Algorithm/구현

[틀림] 백준 16235 나무제테크 // 구현, 배열에 여러정보필요한경우, 삭제보다는 새로할당

https://www.acmicpc.net/problem/16235* 풀이dp문제인줄알고 괜히쫄았음구현은 추상화를 잘하고 나눠서 각각 구현하는게 답인듯.좌표별로 나무정보가 여러개 필요한문제vector arr[14][14]에 각 좌표에 있는 나무들의 나이를 저장죽은 나무를 어떻게 삭제할지vector에서 삭제보다tmp에 산 나무들 저장후,clear후재할당여름에 양분을 어떻게 더해줄지각 좌표에 대해 죽을때마다, 더해줄 양분을 계산, die_cnt에 누적끝나고 yangbun[i][j]에 die_cnt만 더해주면됨. #includeusing namespace std; typedef long long ll;int n,m,k; //맵크기, 나무수, k년int A[14][14]; // 겨울에 줄 양분int yangbu..

[세모] 백준 1269 대칭차집합 // 카운팅스타? 맵또는 배열

https://www.acmicpc.net/problem/1269* 풀이1set에 넣고, binary_search로 찾아서 제거 #includeusing namespace std; int t;int n,m;vector a,b;set s;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=0;i>tmp; a.push_back(tmp); s.insert(tmp); } for(int i=0;i>tmp; b.push_back(tmp); s.insert(tmp); } sort(b.begin(),b.end()); //정렬주의!! for(int ..

[틀림] [알고리즘] 백준 15685 드래곤 커브 // 구현, 기하문제는 규칙을 찾아라

https://www.acmicpc.net/problem/15685* 풀이과정시도1너무복잡.. gg * 큰돌풀이상태를 정의함각 그림을 상태(숫자)로 표현!!숫자에서 규칙찾기vector에 [방향][세대] = { 방향정보들 } 저장#includeusing namespace std; int ret;int n,x,y,d,g;vector v[4][11]; //v[방향][세대] : { ... } 방향정보들int dy[] = {0,-1,0,1}; // 오위좌아int dx[] = {1,0,-1,0};int vis[104][104];void go(int x, int y, int d, int g) { int _x = x; int _y = y; vis[y][x]=1; //시작점 체크 // 주의 : 0세대부터 ..

[알고리즘] 백준 14891 톱니바퀴 // 구현, 배열회전

https://www.acmicpc.net/problem/14891* 내풀이0-idx로 만들기solve함수가 최종본시계, 반시계를 예시를 통해 해보면서 결정vv에 회전대상 {톱니번호, 방향}을 담는게 특징실수한부분 : i를 회전할게아니고 vv[i].first를 회전해야함#includeusing namespace std; vector topni[4]; //topni[0] : {1,0,1,0,1,1,1,1}vector> v; // 명령어들vector> vv; // [{회전대상톱니 idx, 방향}, ... ]int k;void goleft(int cur, int dir) { int nxt=cur-1; if(nxt=4) { return; } if(topni[nxt][6]!=t..

[알고리즘] 백준 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 { ..

[알고리즘] 백준 14890 경사로 // 구현, 전치행렬이용, cnt 이용법

https://www.acmicpc.net/problem/14890* 문제 해결 방식문제 단순화하기처음에는 "한 줄"만 생각합니다.- 가로 한 줄에서 경사로를 어떻게 놓을 수 있을까?- 어떤 조건에서 경사로를 놓을 수 있고, 없을까?상태 추적하기현재 상황을 추적할 변수가 필요함을 깨닫습니다.- 같은 높이가 몇 칸 연속되는지- 경사로를 놓고 있는 중인지=> 이 두 가지를 하나의 변수(cnt)로 표현할 수 있다!패턴 발견하기높이 차이에 따른 패턴을 분석합니다:1. 같은 높이: 여유분 증가2. 오르막: 이전 여유분 필요3. 내리막: 앞으로의 공간 필요최적화하기가로/세로 방향 체크를 같은 로직으로 처리하려면?=> 전치행렬을 사용하면 동일한 함수로 처리 가능!엣지 케이스 생각하기- 연속된 경사로가 필요한 경우- ..

백준 14719 빗물 c++ // 구현, 그리디

https://www.acmicpc.net/problem/147191. 의사코드1. 높이에따라 2차원배열을 만들어줌2. 값이0인곳에 물이 찰수있는지 탐색함3. 좌측이 1이있고 우측에 1이있어야 물이찰수있음빈칸들(0)에 대해 O,X 가능한지 불가능한지 조사함.2. 전체코드#include using namespace std;int Y,X,num, a[504][504],ret;vector> v; //탐색대상위치int left(int y, int x) { if (x = X) { return 0; } if (a[y][x] == 1) return 1; return right(y, x + 1);}//해당좌표에 빗물이 찰수있는지int go(int y, int x) { //좌측에 ..

프로그래머스 귤고르기 c++ // 공간복잡도 공식, 구현

https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 공간복잡도 공식 512MB == int배열[1억] 임을 기억하자. 2. 의사코드 1. arr을 정렬함 //a[i] : i의 등장횟수 ex) arr : 2 2 2 1 1 k=6, O O O 2. k와 arr[i]를 -하면서 k가 0이될때까지 뺴면됨. 3. arr[i]가 0이될때마다 ret++ 4. k가 0이되면 종료 and 마지막 0이된숫자를 세주기위해 ret+1 3. 전체코드 #includ..