일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 |
- 미로찾기
- 삼성테스트
- 큐
- 다이나믹 프로그래밍
- 삼성 SW 테스트
- 하카타역
- IOS
- brute force
- queue
- 플로이드 와샬
- 완전탐색
- dfs
- 삼성시험
- 후쿠오카 4박 5일
- 시뮬레이션
- deque
- 일본 여행
- 후쿠오카 캐널시티
- 플로이드
- 깊이 우선 탐색
- BFS
- 알고리즘
- 완전 탐색
- 후쿠오카 요도바시 하카타
- 백준
- DP
- 후쿠오카
- 후쿠오카 여행경비
- 너비 우선 탐색
- BOJ
- Today
- Total
목록2017/02 (14)
맛있는감귤
문제 : https://www.acmicpc.net/problem/9328출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 Preliminaries K번 생각보다 많이 삽질한 문제였다. 최소 경로를 구하는 것은 아니기 때문에 열쇠가 없는 문은 대기 큐에 넣어 놓고 열쇠를 구했을 때 다시 큐에 넣어주는 방식으로 해결했다. 만약 입력받을 때 요소를 구분한다면 순서가 중요하다. 왜냐하면 A와 a가 전부 테두리에 있을 수도 있기 때문이다. #include <iostream> #include <queue> using namesp..
문제 : https://www.acmicpc.net/problem/1182브루트 포스로 풀기엔 생각보다 까다로운 면이 있다. 부분 집합을 구할 때는 DP 혹은 비트마스크를 이용해서 많이 구하기 때문에부분집합을 구하는 기법을 알아두면 다른 곳에서도 유용하게 사용할 수 있다.나는 비트마스크로 풀었는데 비트마스크를 이용해 부분집합을 구하는 코드는 아래와 같다. int N[4] = {1, 2, 3, 4}; for(int i=0; i < (1
문제 : https://www.acmicpc.net/problem/1463 1차원 좌표에다가 증감이 아닌 감소만 하게 되는 연산이니 BFS로 풀 수 있을 것이라 판단하고 풀었다. #include <cstdio> #include <queue> using namespace std; queue<int> q; bool visited[1000000]; int main(){ int N,cnt=0; scanf("%d",&N); q.push(N); while(!q.empty()){ int sz=q.size(); while(sz--){ int n = q.front(); q.pop(); if (n==1){ printf("%d\n",cnt); return 0; } if(n%3==0 && n/3>0 ..
문제 : https://www.acmicpc.net/problem/2979 출처Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #6 1번 시뮬레이션 문제지만 반복문 없이 풀 수 있지 않을까 고민했지만 생각이 나지않아 말 그대로 시뮬레이션처럼 풀었다. 트럭의 구분없이 몇대가 있느냐만 고려해주면 되는 문제이다. #include <cstdio> #include <queue> using namespace std; int main(){ int A,B,C,cnt=0,ans=0; priority_queue<pair<int, bool>> q; scanf("%d %d %d",&A,&B,&C); for(..
문제 : https://www.acmicpc.net/problem/1890출처Olympiad > Baltic Olympiad in Informatics > BOI 2006 6번 DP로 해결가능한 문제다. 0,0에 1을 넣고 반목문을 돌면서 오른쪽, 아래로 이동 가능한 곳의 값을 더해준다. (dp값은 그 좌표에 도달 가능한 루트의 개수이다.) 유의할 점은 jump값을 더할 때 N의 값을 초과하지 않는지, N-1, N-1 은 연산을 제외 했는지, 경로의 개수를 고려했는지 이 정도 되겠다. 경로의 개수가 많아 BFS로 풀게 되면 메모리 초과가 나오지 않을까 싶다. #include int N; int map[101][101]; long dp[101][101]={0,}; bool visited[101][101];..
문제 : https://www.acmicpc.net/problem/5397 커서를 이동하며 문자를 삽입하거나 지워야하는 문제는 앵간하면 스택이나 큐로 풀 수 있다. 처음에는 리스트를 생각했지만 iterator로 복잡하게 할 바엔 stack이 나을 것 같아서 stack으로 해결했다. 쉽다고 생각하고 막 풀다가 testcase가 바뀌는 시점에서 줄바꿈을 안하는 멍청한 실수를 했다. #include <iostream> #include <string> #include <stack> using namespace std; stack<char> s1,s2; int T; int main(){ cin>>T; while(T--){ string s; cin>>s; for(int i..
문제 : https://www.acmicpc.net/problem/9019출처ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2011 D번횟수가 아닌 연산의 순서를 출력하는 BFS 문제.그냥 queue 으로 풀었다.100이라는 숫자가 L을 했을 때 1000이되어야하는지 1이 되어야하는지 헷갈려서 두 방식으로 다 풀어봤는데 1000이 되는게 맞았다.4636 MS 나온건 함정 #include #include #include using namespace std; int main(){ int T; cin>>T; while(T--)..
문제 : https://www.acmicpc.net/problem/5427출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 F번 일반적인 미로찾기에서 퍼져나가는 장애물이 추가된 문제다. 미로찾기 + 바이러스 라고 생각하면 된다.시간을 따로 관리했다면 3차원 배열로 풀었을텐데 일괄적으로 관리해서 2차원으로 해결했다.먼저 불이 번지는 것을 연산하고 이동을 했다. 어처피 현재 위치는 큐에 들어있기 때문에 불이 먼져 번져도 상관없음비슷한 문제 : https://www.acmicpc.net/problem/3055 #include #includ..
문제 : https://www.acmicpc.net/problem/1963출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 G번 최소 횟수를 구한다는 점에서 BFS를 이용해 풀 수 있다는 것을 유추할 수 있다. 이 문제의 핵심은 기존의 숫자를 한 자리씩 바꾸는 것과 소수판별이다. 제출횟수 대비 정답률이 굉장히 높은게 신기하다. #include <iostream> #include <queue> using namespace std; bool nextPrime(int n){ if( (n&1) == 0 ) return (n == 2); for(int i=3; i*i<=n; i++) { if(..
문제 : https://www.acmicpc.net/problem/5014출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2011 D번 1차원 BFS 문제, 주어진 U,D에 따라 상하 이동만 있다고 생각하면 된다. #include #include using namespace std; bool visited[1000001]; queue q; int main(){ int F,S,G,U,D,cnt=0; bool flag = false; cin>>F>>S>>G>>U>>D; visited[S]=true; q.push(S); while(!q.empty..