목록알고리즘 문제/BOJ (413)

기술 블로그

14890번 경사로

삼성 SW 역량 테스트 기출문제이다. 어려웠었다. 나는 행과 열도 서로 겹치는 부분을 어떻게 생각해야할지 몰라서 다른 분의 코드를 보았다. 그런데, 정답 코드들도 보니, 행과 열은 서로 안 겹쳐도 되는 것 같다. 행과 열을 나누어서 생각하면 된다. https://www.acmicpc.net/problem/14890 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911..
알고리즘 문제/BOJ 2018. 9. 8. 21:50
1941번 소문난 칠공주

백트래킹으로 풀려다가 안 풀려서, 다른 사람의 코드를 참고하였다. 문제에서 서로 가로나 세로로 반드시 인접해야한다. 라고 나와있다. 따라서, ┼ 같은 십자 모양은 DFS, 백트래킹으로 탐색할 수 없기 때문에 다른 아이디어가 필요하다. 문제의 조건을 요약하면 다음과 같다. 25명의 여학생들 중에서, 7명을 뽑는다. 7명 중 최소 4명 이상은 '이다솜파'여야 한다.또한, 뽑은 7명의 학생들은 서로 서로 연결되어 있어야 한다. 즉, 뽑은 7명의 학생이 연결되어있는지만 DFS로(chk 함수) 검사하면 된다. https://www.acmicpc.net/problem/1941 123456789101112131415161718192021222324252627282930313233343536373839404142434..
알고리즘 문제/BOJ 2018. 9. 6. 22:56
1613번 역사

처음에 단순히 BFS 문제인줄 알았다. 그러나, 제출을 해보니 시간 초과가 떴다. BFS를 2번 실행해서 그런 것 같다. 결국 플로이드 와샬 알고리즘 풀어야 한다. https://www.acmicpc.net/problem/1613 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include #include #include #include #include #include #include using namespace std; vector v; vect..
알고리즘 문제/BOJ 2018. 9. 5. 01:39
2146번 다리 만들기

https://www.acmicpc.net/problem/2146 DFS와 BFS 2개 모두 활용하는 문제이다. DFS를 통해 각 섬들을 그룹화 시켜주고, BFS를 통해 퍼져나가는 작업을 실행한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include using namespace std; #define Max 101 int m[Max][Max], N, answer = 2e9;int dy[4] = { 0, 1, 0, -1 };int dx[..
알고리즘 문제/BOJ 2018. 9. 4. 22:37
14502번 연구소

삼성 SW 역량 테스트 기출문제이다. 2가지 풀이 방법이 있다. 접근 방법 등 모두 기억하자. 첫 번째, BackTracking 활용두 번째, 3중 For 문 활용 https://www.acmicpc.net/problem/14502 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118#include #include #inc..
알고리즘 문제/BOJ 2018. 9. 2. 20:25
9328번 열쇠

BFS 문제이다. 단지, 새로운 열쇠(a ~ z)를 획득하였을 때만, 주의 해주면 된다. 또한, map[y][x]를 '.'로 바꾸는 것도 신경쓰면 된다. https://www.acmicpc.net/problem/9328 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712..
알고리즘 문제/BOJ 2018. 9. 2. 17:29
14500번 테트로미노

두 번째 풀이 방법은 신선하여 첨부하였다. 삼성 SW 역량 테스트 기출 문제이다. 방문 여부(visit)를 잘 생각해줘야한다. 방문 여부를 생각하지 못 하여(다음 테트로미노를 위한 재사용), 다른 분의 코드를 참고하였다. 이 문제를 통해 기억해야할 것1. 36, 40, 92, 98 번 째 줄은 반드시 써줘야한다. 그래야 다음 모양의 테트로미노를 계산할 때, 다시 한 번 정사각형 한 칸의 크기를 사용할 수 있다.2. otherShape 함수는 DFS로는 탐색할 수 없는 모양(ㅗ)을 위해 따로 만들어준 함수다. https://www.acmicpc.net/problem/14500 1234567891011121314151617181920212223242526272829303132333435363738394041..
알고리즘 문제/BOJ 2018. 8. 30. 14:00
1389번 케빈 베이컨의 6단계 법칙

기본적인 BFS 문제이다. 문제 유형에 '플로이드 와샬 알고리즘'이 있어서, 쫄았다.(?) (배웠긴 했지만, 까먹었기 때문이다. 꼭 다음 주 내로 각종 알고리즘들을 복습해야겠다.) https://www.acmicpc.net/problem/1389 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104#include #include #include #include #include #include #i..
알고리즘 문제/BOJ 2018. 8. 30. 01:44
이전 Prev 1 ··· 45 46 47 48 49 50 51 52 Next 다음