본문 바로가기 메뉴 바로가기

ACM-ICPC 상 탈 사람

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

ACM-ICPC 상 탈 사람

검색하기 폼
  • 분류 전체보기 (360)
    • 서버 관련 (9)
      • JS (5)
      • AmazonWebService (1)
      • Backend 지식 (3)
    • 일상 (13)
      • Daliy (1)
      • 잡담 (10)
      • 개인 (2)
    • 알고리즘 관련 (337)
      • BOJ (303)
      • UVaOJ (8)
      • SPOJ (1)
      • 알고리즘&이론 (25)
  • 방명록

brute force (10)
BOJ)10881 프로도의 선물 포장

문제: icpc.me/10881 세개의 상자를 하나의 큰 포장상자안에 넣어야 할 때 준비해야하는 포장상자의 최소 넓이를 구하는 문제이다. 우선 상자가 세개밖에 주어지지 않기 때문에 완전탐색을 생각해볼 수 있다. 세개의 상자를 배치하는 모양은 회전에 따라서 달라지지 않는 경우는 1열로 3상자를 배치하는 케이스와 2상자 위에 1 상자를 쌓아놓는 모양 두가지 밖에 없다. 때문에 주어진 조건으로 위의 경우에 해당 하는 모든 경우를 탐색하면 하나의 쿼리를 2*6^3의 시간만에 처리할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include using namespace std;pair a[6];int three(i..

알고리즘 관련/BOJ 2017. 6. 11. 18:43
BOJ)2503 숫자 야구

문제:icpc.me/2503 각 자리의 숫자를 임의로 설정해 준 뒤 매 쿼리를 비교해주는 계산을 하더라도 O(1000*N)의 시간밖에 걸리지 않기 때문에 완전 탐색을 해주어 통과되는 숫자의 수를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include using namespace std;int n, r;struct query { int num, strike, ball; query(int num, int strike, int ball) :num(num), strike(strike), ball(ball) {} query() {} int getfirst()..

알고리즘 관련/BOJ 2017. 6. 8. 17:34
BOJ)1405 미친 로봇

문제: icpc.me/1405 각 방향으로 이동할 확률과 이동 횟수가 주어질 때 경로가 단순할 확률을 구하는 문제이다. dfs를 통한 4방향 탐색으로 각 방향으로 이동할 확률을 곱해서 brute force 해주면 된다. 1234567891011121314151617181920212223242526272829#include #include using namespace std;int n, visited[30][30];double p[4];int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };double dfs(int x, int y, int cnt) { if (cnt == 0)return 1.0; double ret = 0.0; visited[x][y] = true; for ..

알고리즘 관련/BOJ 2017. 6. 7. 18:38
BOJ)1251 단어 나누기

문제: icpc.me/1251 단어를 세 단어로 나눈 뒤 나눈단어를 전부 뒤집어 다시 붙인 단어들 중 사전순으로 가장 앞서는 단어를 출력하는 문제이다. N이 50까지 밖에 안들어오기 때문에 가능한 경우를 전부 뽑아내도 50C3 밖에 안되므로 모든 경우를 탐색하여 결과를 확인해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include #include using namespace std;vector vt;string a;void rev(string &x, int lo, int hi) { string z = x; for (int i = lo; i = a.length() ..

알고리즘 관련/BOJ 2017. 4. 20. 16:44
BOJ)14500 테트로미노

문제:icpc.me/14500 주어진 문제의 답은 모든 경우에 테트로미노를 다 대봄으로서 구할 수 있다. 주어지는 테트로미노의 5가지 모양중 ㅜ 모양을 제외한 4가지 모양은 DFS를 통하여 탐색이 가능하고 ㅜ모양만 따로 처리를 해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include using namespace std;int n, m, a[501][501], v[501][501], r;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };bool chk(int x, int y) { r..

알고리즘 관련/BOJ 2017. 4. 17. 16:57
BOJ)14502 연구소

문제: icpc.me/14502 N,M의 범위가 매우 적기 때문에 나올 수 있는 경우를 전부 확인해줄 수 있다. 6중 포문을 통하여 모든 경우에 벽을 세워본 후 dfs를 통하여 바이러스가 얼마나 퍼질 수 있는지 조사하여 그 최솟값을 전체 크기에서 벽을 제외한 값에서 빼주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include #include #include using namespace std;int n, m, a[9][9], r, visited[9][9], b;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,..

알고리즘 관련/BOJ 2017. 4. 17. 15:53
BOJ)7573 고기잡이

문제: icpc.me/7573 그물의 둘레와 물고기의 수가 100으로 매우 적다 이를 이용하여 완전탐색을 해주면 된다. 한 물고기에 대해 그 물고기를 둘레에 포함하는 가능한 모든 그물을 만들어본 뒤 확인해주면 된다. 1234567891011121314151617181920212223242526272829303132333435#include #include using namespace std;int n, l, m, r;pair f[101];bool chk(int x, int y, int lx, int ly, int rx, int ry) { return lx

알고리즘 관련/BOJ 2017. 4. 12. 18:45
BOJ)2992 크면서 작은 수

문제:icpc.me/2992 등장하는 수로 조합가능 한 모든 수를 비교하여 그 중 최솟값을 구해주면 된다. 시간 복잡도는 O(6!)이다. 12345678910111213141516171819202122232425#include #include #include #include #define INF 987654321using namespace std;char a[7];int r = INF;int main() { scanf("%s", &a); int v = stoi(a); vector vt; for (int i = 0; a[i] != '\0'; i++) vt.push_back(a[i]); sort(vt.begin(), vt.end()); do { for (int i = 0; i

알고리즘 관련/BOJ 2017. 4. 3. 18:22
BOJ)12100 2048 (Easy)

문제:icpc.me/12100 2048 게임에서 가능한 5번의 움직임 이내에 나올 수 있는 가장 큰 블럭을 출력하는 문제이다. 하나의 상태에서 가능한 움직임은 4방향이고 N*N의 모든 블럭이 움직여야 하므로 하나의 상태에서 4방향으로 움직일 때 연산 횟수는 4*N*N이다. 5번 움직일 때 나올 수 있는 모든 횟수는 4^5이므로 모든 경우를 전부 구했을 때 시간 복잡도는 (1024*N^2*4)이므로 완전 탐색으로 해결 가능하다. 이 때 주의해야 할 점은 한번의 움직임에서 이미 합쳐진 블럭은 다시 안합쳐지므로 visited배열을 관리해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950..

알고리즘 관련/BOJ 2017. 3. 30. 18:00
BOJ)9202 Boggle

문제: icpc.me/9202 점수를 얻을 수 있는 문자열 셋이 주어진 뒤 Boggle 보드가 주어질 때 주어진 Boggle 보드에서 얻을 수 있는 최고점수 가장 긴 문자열 찾은 단어의 수를 출력하는 문제이다. 단어 사전에 단어가 30만개 까지 들어올 수 있으므로 트라이를 이용하여 해결하면 쿼리를 매번 최대 단어의 길이안에 처리해줄 수 있다. 우리는 단어 사전의 모든 단어들을 Trie에 저장해 준 후 Boggle 보드에서 Bruteforce를 통하여 모든 경우를 탐색하여 나올 수 있는 문자열들을 set에 저장해 준 뒤 답을 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505..

알고리즘 관련/BOJ 2017. 2. 4. 04:30
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Node.js로 DynamoDB 시작⋯
  • Node.js로 DynamoDB 시작⋯
  • Express와 Apollo server⋯
  • GraphQL 스키마 작성하기⋯
최근에 달린 댓글
  • 도움이 많이 되었습니다 굳굳⋯
  • 간선의 방향을 다 거꾸로 받⋯
  • 넵 요즘은 거의 node js 만⋯
  • 문제 설명 감샇바니다. :) 'B⋯
Total
315,368
Today
35
Yesterday
199
링크
  • 민호형
  • 제주시민
  • 꼴뚜기
  • 김흿
  • 태양쓰
  • 정률이
  • 정이 형
  • stack님
  • 세지니
  • 매브레이커
  • 박트리님
  • 플즈런님
  • 맹킹
  • 송이 블로그
TAG
  • MCMF
  • 트리
  • 이분 매칭
  • MST
  • dfs
  • 그리디 알고리즘
  • 수학
  • disjoint-set
  • BFS
  • 다이나믹 프로그래밍
  • KMP
  • 힙
  • 디닉
  • 좌표 압축
  • SCC
  • 이분 탐색
  • LCP array
  • 네트워크 플로우
  • 위상 정렬
  • 세그먼트 트리
  • lazy propagation
  • 다익스트라
  • partial sum
  • lca
  • 분할 정복
  • 플로이드 워셜
  • 라인 스위핑
  • 에라토스테네스의 체
  • Suffix Array
  • brute force
more
«   2021/03   »
일 월 화 수 목 금 토
  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 31      
글 보관함
  • 2020/05 (2)
  • 2020/04 (6)
  • 2020/03 (1)
  • 2018/07 (4)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바