본문 바로가기

분류 전체보기

 (157)
#2012 등수 매기기 https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 실버 3의 문제이다. 그냥 문제를 보고 조금 끄적여보다보니까 입력받은 예상등수를 오름차순 정렬해야 할 것 같다는 생각이 들었다. #include #include #include using namespace std; int main() { freopen("input.txt","r",stdin); int n; long long sum=0; vector expect; cin>>n; for(int i=0;i>n..
음료수 얼려 먹기 전형적인 DFS/BFS문제이다. 그냥 map을 돌면서 연결된 영역의 개수를 구해주면 되는 문제이다. DFS로 풀수도 있고 BFS로도 풀 수 있다. 연습을 위해 두가지 코드 모두 작성하였다. - BFS코드 #include #include #include #include using namespace std; int n,m,cnt; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; int map[1001][1001]; int visited[1001][1001]; queue q; void bfs(int x,int y){ q.push(make_pair(x,y)); visited[x][y]=1; while(!q.empty()){ x=q.front().first; y=q.front().sec..
#16953 A→B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A >a>>b; int ans=-1; q.push(make_pair(a,1)); while(!q.empty()){ long l..
Greedy (탐욕법) 그리디 알고리즘은 어렵지 않으면서도 가장 많이 코테에 출제된다고 한다. 그만큼 중요하기도 하고, 많이 풀어봐야하는 문제 유형이다. 그리디 알고리즘의 핵심은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 이다. 이 알고리즘은 현재 가장 좋아보이는 방법만을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같이 은연중에 기준을 제시해준다. 이런것을 보고 그리디 알고리즘 사용 문제구나! 눈치 챌 수 있으면 된다. ++그리디 알고리즘은 주로 정렬 알고리즘과 자주 같이 출제 된다. 예시로 거스름돈 문제를 들겠다. 문제: 카운터에는 500원,100원,50원,10원 짜리 동전..
게임 개발 #include #include #include using namespace std; bool flag=false; int n,m; int nowx,nowy; int dir; int cnt=1; int dx[]={0,1,0,-1}; int dy[]={-1,0,1,0}; int map[51][51]; int visited[51][51]; void move(int x,int y){ visited[x][y]=1; while(true){ flag=false; for(int k=0;k>nowx>>nowy>>dir; for(int i=0;imap[i][j]; } } move(nowx,nowy); cout n >> m; // 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기 cin >> x >> y >> direc..
#1789 수들의 합 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 실버 5의 문제이다. 처음엔 되게 막막 했었는데 생각 보다 쉬웠다. #include #include using namespace std; int main() { //freopen("input.txt","r",stdin); long long s,n; cin>>s; int i=1; int res=0; long long sum=0; while(true){ sum+=i; res++; if(sum>s){ cout
#18310 안테나 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 실버 3의 문제이다. 문제를 천천히 읽어보고 손으로 조금 끄적여 봤을때, 중간값이 답이 될것 같다는 생각이 들기는 했는데 예외가 너무 많을 것 같아서 완전 탐색으로 코드를 작성 했다. 결론은 시간초과였다. 다음은 시간초과의 코드이다. #include #include #include using namespace std; vector house; vector cost; int main() { //freopen("input...
#1449 수리공 항승 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 실버 3의 문제이다. 생각보다 단순한 문제였는데 너무 꼬아서 생각하느라 풀기가 힘들었다. #include #include using namespace std; int pipe[1001]; int main() { freopen("input.txt","r",stdin); int n,l; int tape=1; cin>>n>>l; if(l==1){ cout

티스토리툴바