Algorithm/구현

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

프로그래머스 달리기경주 c++ // 해쉬맵 기본정렬됨(키값기준오름차순), 구현

https://school.programmers.co.kr/learn/courses/30/lessons/178871 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 0. 해쉬맵은 키값기준 오름차순으로 기본정렬되어 있다. 내림차순하려면 선언시 greater 을 추가하면된다. 1. 의사코드 m1 : 이름, 인덱스 저장 m2 : 인덱스, 이름저장 1. calling(현재이름)으로 이전이름을 찾는다. 2. m1, m2를 각각 값에 알맞게 swap 해준다. ex : m1[kai]=3 , m1[pve]=2 ---> m1[kai]=2, m1[pve]=3 m2[3]=ka..