일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 29 |
30 |
- brute force
- 삼성테스트
- BOJ
- 깊이 우선 탐색
- 미로찾기
- 백준
- deque
- 후쿠오카 요도바시 하카타
- 삼성시험
- 후쿠오카 4박 5일
- 후쿠오카 캐널시티
- 큐
- 삼성 SW 테스트
- 시뮬레이션
- 다이나믹 프로그래밍
- DP
- 후쿠오카 여행경비
- BFS
- dfs
- queue
- IOS
- 플로이드 와샬
- 너비 우선 탐색
- 알고리즘
- 완전 탐색
- 일본 여행
- 하카타역
- 플로이드
- 완전탐색
- 후쿠오카
- Today
- Total
목록2017/04/28 (14)
맛있는감귤
문제 : https://www.acmicpc.net/problem/1074기초 분할 정복 문제재귀를 구현할 머리가 안되는지 완전 탐색이나 DP보다 이게 더 어렵게 느껴질 때가 많다.다행히 2^N꼴이기 때문에 쉽게 접근이 가능하다.n==2, 2*2의 제일 작은 사각형이 될 때까지 4등분으로 나누어주고 (line. 31~34) Z모양으로 cnt를 차례대로 증가시켜주자.123456789101112131415161718192021222324252627282930313233343536373839#include #include int N,R,C,cnt=0;void dnc(int n,int r,int c){ if(n==2){ if(r==R && c==C) { printf("%d\n",cnt++); return ; }..
문제 : https://www.acmicpc.net/problem/5214출처Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #5 4번 이 문제는 입력만 잘 받으면 BFS로 해도 시간초과가 나지 않는다.핵심은 임의의 열의 개수를 어떻게 vector에 push하느냐 이다.문제 테스트 케이스를 돌려보면1 : 10 11 2 : 10 3 : 10 12 4 : 11 5 : 11 13 6 : 12 13 14 7 : 12 13 8 : 14 9 : 14 10 : 1 2 3 11 : 1 4 5 12 : 3 6 7 13 : 5 6 7 14 : 6 8 9 가 나온다. 잘 활용해서 풀어보도록 하자. 12345678910111213141..
문제 : https://www.acmicpc.net/problem/14226간단한 BFS이지만 visited 배열을 잘 활용하지 못한다면 원하는 정답이 안나올 것이다.현재 글자수 뿐만아니라 클립보드에 저장 돼 있는 글자 수도 고려해줘야 한다.핵심 visited[글자수][클립보드]1234567891011121314151617181920212223242526272829303132333435363738394041#include #include using namespace std;int S,cnt=0;queue q;bool visited[2002][2002];int main(){ scanf("%d",&S); q.push(make_pair(1, 0)); visited[1][0]=1; while(!q.empty()..
문제 : https://www.acmicpc.net/problem/13913기존 1697 숨바꼭질 과 같은 문제지만 추가로 지나온 경로를 출력을 요구한다는 점에서 차이가 있다.처음에는 queue에 경로 벡터를 추가해서 노드마다 경로 값을 가지는 무식한 짓을 벌였다.어처피 목적지에 도달하는 최소 경로중 하나만 출력하면 되기 때문에 배열 하나로 지나온 경로를 관리하는 방법으로 AC를 얻었다.visited[다음 경로] = 현재 경로 가 된다. 그리고 목적이에 도달했을 때 목적지에서 출발지까지 뒤로 탐색해 vector에 push한 다음 다시 출력하게 되면 원하는 경로가 출력될 것이다.123456789101112131415161718192021222324252627282930313233343536373839404..