목록전체 글 (629)

기술 블로그

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
2117번 홈 방범 서비스

문제 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu 풀이 : https://www.swexpertacademy.com/main/learn/course/lectureHtmlViewer.do 마름모를 판단할 수 있으면, 쉬운 문제였으나, 마름모를 판단하지 못 한다면 어려운 문제다. 우선, 들어가기 전에 BFS는 마름모 모양으로 퍼져 나간다는 것을 기억하자. 아래의 코드()를 실행해 보면, 각각 과 처럼 나온다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515..
알고리즘 문제/SW Expert Academy 2018. 9. 1. 23:59
2105번 디저트 카페

어려웠던 문제였다 단순 BFS 문제인줄 알고, BFS로 접근하였다가 아닌 것 같아서 바로 다른 풀이를 생각해보려 하였으나, 잘 떠오르지가 않았다. 그래서 다른 분의 코드를 참고하였다. 풀이 ebook도 참고하였다. 백트래킹 문제인줄은 몰랐다. 열심히 공부해야겠다. 문제 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu 풀이 : https://www.swexpertacademy.com/main/learn/course/lectureHtmlViewer.do 12345678910111213141516171819202122232425262728293031323334353637383940..
알고리즘 문제/SW Expert Academy 2018. 8. 31. 17:03
14500번 테트로미노

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