목록Algorithms (59)
혼종 꼬지마루
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo(이 글이 문제가 될 시 삭제하도록 하겠습니다.) 시뮬레이션 카테고리로 올려두긴 했지만 DFS + BFS로 풀었다 먼저 구슬을 쏘는 순서를 DFS로 정해 준 뒤, BFS로 연쇄적으로 삭제한 아래로 내리는 순서로 해결했다 하지만 시간효율은 썩 좋지 않은 1.8s가 나옴 다른 사람들은 더 짧은 시간이 걸리는데 아마 내 코드 중에 맵을 카피하는 과정에서 시간을 많이 잡아먹은 듯 하다 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484..
BFS로 풀려다가 메모리초과랑 런타임이 오지게 난 문제 원래 아이디어는 BFS로 탐색 후 도착하면 그 경로를 역추적하여 마킹하는 과정을 전부 돌아봐주는 방법 map과 큐, check와 경로를 저장하는 배열까지 만들었으니 메모리가 초과날만 한듯 DFS로 풀기 두려웠던 것은 시간초과가 날 것 같다는 생각에 BFS로 했던 것인데 메모리라니... 결국 DFS로 풀었다 1. 시작점을 돌면서 DFS 탐색 시작 2. 갈 수 있는 위치면 체크하고 들어간다 3. 도착했다면 리턴하며 1을 반환 12345678910111213141516171819202122232425262728293031323334#include #include #define MX 10005using namespace std; char map[MX][50..
간단한 시뮬레이션 문제 O(S)면 끝나기 때문 입력받은 K 를 26으로 나눈 나머지로 바꿔 준다. 그리고 한 문자식 꺼내어 보며 k씩 올려준다. 이때 주의할 것은 소문자의 경우 k를 올려주면 아스키 코드값을 넘어가버린다. 중간에 한번 변환시키고 연산하면 바로 나옴 1234567891011121314151617181920212223242526272829303132333435#include #include #include #define MX 100002using namespace std; string str;int k, s; int main(void){ scanf("%d %d\n", &k, &s); getline(cin, str); k %= 26; for (int i = 0; i
간만에 원큐에 푼 문제라 기분이 너무 좋다... 그냥 재귀로 싹다 돌려줘도 되는 문제 물론 전체 포지션을 다 고려한다고 했을 경우에는 O(11^11)이라 밥먹고 오면 풀릴 시간이지만 문제 조건이 '한명당 적합한 포지션은 최대 5개'라는 조건이 붙어 있어서 O(5^11) 까지 줄어드는 문제 1234567891011121314151617181920212223242526272829303132333435363738394041#include #define SIZE 13using namespace std; int S[SIZE][SIZE];bool check[SIZE];int C, dab; void dfs(int d, int sum){ if (d == 11) { dab = dab > sum ? dab : sum; r..
dp를 처음 시작하면서 이 문제를 꼭 풀어보면 좋다고 생각하는 문제 dfs로 검사하며 return하는 과정에서 메모이제이션을 해주는 문제로 필수문제라고 생각 1. 맵정보를 입력받으며 dp를 -1로 초기화 2. dfs로 내리막길을 찾으며 탐색 그 위치에서의 dp는 방문한 것을 체크하기 위해 0으로 만든다. 3. 도착점에 도착하면 1을 반환한다. 4. 만약 방문한 점이고, dp가 -1이 아니라면 그 지점의 값을 반환한다. 123456789101112131415161718192021222324252627282930313233343536#include #define MX 503using namespace std; int map[MX][MX], dp[MX][MX];int dx[] = { 0, 0, -1, 1 };..
문제를 잘못 이해해서 한번 틀린 문제... 무작위가 아닌, '한줄로 이어 붙였을 때 사전 순서'라는 점에 초점을 맞추면 그다음 부터는 쉬워진다 입력을 받으며 x인 부분은 구조체 배열로 그 위치를 담아주고, A~L인 부분은 check해준다. 그다음 부터는 한 위치씩, 모든 경우의 수를 넣어주고 끝까지 넣고 난 후 조건에 맞으면 flag를 달아주고 출력하면 끝 조건을 검사하는 부분에서 따로 머리써서 단순화 시키기 보다는 그냥 무식하게 인덱스로 다 찾아서 더해줬다...ㅎ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #define MX 60using name..
https://www.swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKpmwua-VoDFAUV(이 글이 문제가 될 시 삭제하도록 하겠습니다.) 과거 삼성전자 SW Test A형을 딸 때 1시간 만에 풀었는데 복원문제라는 소문 듣고 풀어봤다 아주 살짝 더 쉬운 문제인데... 더 오래걸린... 이제 코딩아이디어가 빠르게 안되나보다... 1. SAMSUNG 문자열을 target배열에 각 문자의 갯수를 저장한다. 2. 그리고 나서 L, 면접관 이름, 점수 P를 입력받는다. 3. 조합으로 dfs탐색 이때 중요한 것은 check배열에 면접관의 이름에 있는 문자의 갯수를 더하고 빼주며 검사한다 4. 매번 검사하며, targ..
dp문제 중에 무조건 풀어야하는 기초문제인 것 같습니다. 한 열에서 스티커를 선택하지 않을 경우, 첫번째 행의 스티커를 선택할 경우, 두번째 행의 스티커를 선택할 경우로 나누어 이전 열에서 가장 큰 값을 더해주는 식으로 dp를 풀어주면 N번 연산으로 끝낼 수 있습니다. 12345678910111213141516171819202122232425262728293031#include #define SIZE 100003#define MAX(X, Y) ((X) > (Y) ? (X):(Y))using namespace std; int map[3][SIZE], dp[3][SIZE];int T, N; int main(void){ cin >> T; while (T--) { cin >> N; for (int i = 1; ..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4(문제가 될 시 삭제하도록 하겠습니다.) D5이긴 한데 그렇게 어렵지는 않았던문제... 그냥 문제를 잘 못 이해해서 좀 뻘짓했음 게다가 BFS라기도 뭐하고...시뮬레이션에 BFS조금 섞은 느낌 1. 상원이의 친구를 일단 큐에 넣으며 초대장을 나눠주는 갯수를 센다. 2. 큐에서 하나씩 빼며 그 친구의 친구를 중복되지 않도록 초대장을 나눠준다. 이때 큐에 다시 집어넣지 않도록 조심! 3. 초대장을 나눠준 갯수를 리턴 12345678910111213141516171819202122232425262728293031323334353637383..
dfs의 기본문제라고 생각된 문제 1. N/2로 팀을 나눈다 2. 2중포문으로 start팀과 link 팀의 능력치를 구하고, 차이의 최소값을 구한다 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #define MX 22#define INF 987654321#define ABS(X) (X) > 0? (X): -(X)using namespace std; bool check[MX];int map[MX][MX];int N, dab = INF; void dfs(int d, int pos){ if (d == N / 2) { int start, link; start = link = 0; for (in..