목록Algorithm/구현 (12)
Mini
[구현] 프로그래머스 방문길이 // set
https://school.programmers.co.kr/learn/courses/30/lessons/49994?gad_source=1&gad_campaignid=22199869887&gbraid=0AAAAAC_c4nB6yISFBx5mGvyOG08zAQ87t&gclid=CjwKCAjwsZPDBhBWEiwADuO6y9aUyXD7gRRtDHQNWI8nlF7PY_7YefwJekHo0m-V-AOfGdA5TBefwxoCEsgQAvD_BwE 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 풀이좌표를 (0,0)으로 변경set에 from, to를 정렬후 넣기 (좌->우, 위->아래 순서)set.size가 정답일것import..
[세모] 프로그래머스 가장많이 받은 선물 // 구현, 해시맵, 문자열을 인덱스로
* 풀이1일단 문제를 읽으며 도식화를 진행.문제의 예시에서 힌트를 얻어, 그래프형태로 만들기graph[i][j] : i가 j에게 준 선물 수문제1 : string을 배열의 인덱스로 쓰려면?map을 이용해 매핑문제2 : 둘다 주고받지않는것을 어떻게 판단?graph[i][j], [j][i]가 둘다 0인경우처음 제출 코드 (답이 2배가 되는 문제)import java.util.*;class Solution { public int solution(String[] friends, String[] gifts) { int answer = 0; int n = friends.length; HashMap m1 = new HashMap(); //str to index..
[틀림] 백준 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. 내리막: 앞으로의 공간 필요최적화하기가로/세로 방향 체크를 같은 로직으로 처리하려면?=> 전치행렬을 사용하면 동일한 함수로 처리 가능!엣지 케이스 생각하기- 연속된 경사로가 필요한 경우- ..