본문 바로가기

알고리즘

 (43)
삼성 SW 역량테스트 기출 :: 연산자 끼워넣기 문제링크 : https://www.acmicpc.net/problem/14888 난이도 : 하 /* * 연산자 끼워넣기 : https://www.acmicpc.net/problem/14888 */ #include #include #define FOR(i, n) for(int i = 0 ; i > n; FOR(i, n) cin >> nums[i]; FOR(i, 4) cin >> op[i]; mmax = INT32_MIN; mmin = INT32_MAX; } int operate(int a, int b, int op){ switch(op){ case 0: ..
삼성 SW 역량테스트 기출 :: 경사로 문제 링크 : https://www.acmicpc.net/problem/14890 난이도 : 하 /* * 경사로 https://www.acmicpc.net/problem/14890 * * 가로로 건널 수 있는지 확인하는 함수 하나를 만들고 * 보드를 회전시켜서 세로도 확인 */ #include #include #include #define FOR(i, n) for(int i = 0 ;i < n ; i ++) using namespace std; int n, l; int board[100][100]; int rotBoard[100][100]; bool occupied[100][100]; void rotate(){ FOR(i, n){ FOR(j, n){ rotBoard[i][j] = board[n-j-1][..
삼성 SW 역량테스트 기출 :: 로봇 청소기 문제 링크 : https://www.acmicpc.net/problem/14503 난이도 : 하 * 문제에서 방향을 북동남서 순서로 줬는데, 북서남동으로 풀어서 헤맴.. 1. 북,동,남,서 방향으로 한 칸을 움직일 때의 인덱스 변화를 vector dirs;에 저장해 두고(setDir()부분) 인덱스를 계산함 2. 문제의 지시대로 로봇 청소기의 움직임을 cleanNext에 구현 /* 로봇 청소기 */ #include #include #include #define FOR(i, n) for(int i = 0 ; i < n ; i ++) using namespace std; int n, m, r, c, d, rslt; int board[52][52]; //direction 0: 북, 1:동, 2:남, 3:서 /..
ALGOSPOT 문제 풀이 기록 DINAMIC PROGRAMMING문제 날짜 난이도 비고 COINS 170825 중 알고리즘을 잘못 생각함. 다시 풀어볼 것 TILING2 170826 하 피보나치 수열을 행렬의 devide&conquer로 푸는 풀이로 다시 풀어볼 것 DIAMONDPATH 170827 하 stack overflow. 항상 max+1의 배열을 할당할 것 NUMB3RS 170828 중하 2차원 배열의 memset. 쓴것 갯수만 초기화 X. 할당한 갯수 전체를 초기화해야 함. + D&Q로 더 최적화 가능 PACKING MORSE ARCTIC 171022 다시풀어보기 KAROKU 다시풀어보기
algospot :: ARCTIC 남극기지 문제 : https://algospot.com/judge/problem/read/ARCTIC알고리즘 문제 해결 전략 p. 450 처음에 문제를 잘못 이해해서, 한 도시에서 다른 한 도시로만 전파를 전달 할 수 있다고 생각하고 풀었다... 그랬더니 시간초과가 나와서 알고리즘 문제해결 전략 책에서 decision부분만 참고해서 다시 풀었다. 맨날 vector만 쓰고 queue는 거의 처음 써본다. [최종코드]#include #include #include #include #include #include #include #define FOR(var, ed) for(int var = 0 ; var < ed; var++) using namespace std; int tc, n; vector locations; d..
algospot :: DARPA DARPA Grand Challenge 문제 : https://algospot.com/judge/problem/read/DARPA알고리즘 문제 해결 전략 p. 449 (동적 계획법으로도 풀 수 있다고 나와 있지만) 최적화문제를 결정문제(yes/no 로 답이 나오는 문제)로 바꿔서 푸는 유형의 문제이다. [최적화 문제를 결정문제로 바꾸는 방법]1. "가장 좋은 답이 무엇인가?" -> "x 또는 그보다 좋은 값이 있는가?"라는 결정문제 형태로 바꿈.2. 결정 문제를 쉽게 풀 수 있는 방법이 있는지 찾아봄.3. 결정문제를 내부적으로 이용하는 이분법 알고리즘을 작성. [이분법의 함정]어떤 문제의 정답이 4.2라고 가정하자. 그런데 연산 중 수치적 오차가 생겨서 4.2에 대해 참 또는 거짓을 반환했다고 하자. 그러면 optimize()는 4.2를 상한..
algospot :: ALLERGY 알러지가 심한 친구들 문제 : https://algospot.com/judge/problem/read/ALLERGY알고리즘 문제 해결 전략 p.429책을 참고하지 않고 코드를 작성함 [알고스팟 STEP.1]비트마스크를 이용해서 지금까지 음식을 먹을 수 있는 사람들을 저장하고, 모든 사람들이 음식을 먹을 수 있을 때에 음식의 수의 최소값을 출력했다. *void getInput() 입력을 받는 함수이다. 이름은 names벡터에 따로 저장해두고FOR(i, n){ cin >> names[i]; }food번째 음식에 대해 음식을 먹을 수 있는 이름들이 나오면, 그 이름을 갖고 있는 인덱스를 names에서 찾아서 그 값을 비트마스크로 환산하여 allergic[food]에 더했다. 이렇게 하면 food번째 (음식을 먹을 수 있는 사람)번..
algospot :: BOARDCOVER2 게임판 덮기 2 문제 : https://algospot.com/judge/problem/read/BOARDCOVER2 알고리즘 문제 해결 전략 p.423 [알고리즘 STEP. 1] 일단, 입력받은 블록을 4방향으로 돌려서(0도, 90도, 180도, 270도) 미리 저장해 둔다. 저장 할 때는 왼쪽 가장 위의 인덱스를 0,0으로 두고 나머지를 상대 위치로 변환해서 pair 형태로 저장한다.(void generateRotations(vector block)) vector rotations; //roatations : block을 회전시켜 만든 4가지 블록을 pair의 벡터로 저장 void generateRotations(vector block){ //vector&block 아니고 그냥 복사 rotations.clear();..

티스토리툴바