전체 글
-
2 - 4. Back Tracking 예제 (3671번: 산업 스파이의 편지)CS/ProblemSolving 2019. 3. 16. 16:29
백준 3671번(산업 스파이의 편지) 저번에 잠깐 설명했던 백트래킹 문제를 하나 가져왔습니다.(열심히 썼으니... 아직 잘 모르시겠다면, 여기를 참고해주세요.) 소수를 이용하네요. 범위는 7자리니까 1 ~ 9,999,999까지 나옵니다.테스트 케이스가 최대 200개이고, 따라서 그냥 막 접근하면 시간초과가 나겠죠. 우선 소수를 빠르게 구할 수 있는 에라토스테네스의 체(Eratosthenes's sieve) 알고리즘부터 공부해보시는게 좋습니다.수학 관련 알고리즘을 다룰건 아니니까 자세한 설명은 생략하겠습니다. 아래 링크를 참고해주세요.(wiki: 에라토스테네스의 체) 우선적으로 테스트케이스를 여러번 돌려야하니까 미리 반복문 밖에서 소수를 최댓값(9,999,999)까지 구해둡니다.그리고 다음으로 백트래킹을 ..
-
2 - 3. DFS 예제 (1260번: DFS와 BFS), DFS 응용CS/Alogrithm 2019. 3. 9. 21:14
백준 1260번(DFS와 BFS) 후.. 몇일 전에 작계 훈련 갔다오고, 또 지원서 쓰느라 이제야 포스팅 합니다. ㅠㅠ 이 문제는 한창 DFS를 잘 모르고 문제를 막 풀어댈 때 겁나 털린 문제입니다.정말 기본기만 할 줄 안다면, 바로 풀 수 있는 문제이고, DFS 연습 및 구조 파악하기 좋습니다.이 문제 말고도 N과 M이라는 문제 시리즈가 있는데, 저는 그 문제를 통해서 DFS 및 Back Tracking에 대해 제대로 알게 되었어요. 어쨌든 각설하고 문제부터 읽어 봅시다. 문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정..
-
2 - 2. BFS 예제 (3197번: 백조의 호수)CS/ProblemSolving 2019. 2. 27. 20:37
백준 3197번(백조의 호수) 이 문제.. 제가 처음 풀때 정말 몇번이나 시간초과로 고생했던 기억이 있네요. BFS라고 분류 되어있지만 일반적인 BFS는 해결이 불가능합니다. 난이도가 꽤 높은 편인데 이 문제를 가져온 이유는 우리가 이제껏 공부한 내용으로 해결이 가능하기 때문입니다. 제가 아는 바에 의하면 해결법이 2가지가 존재합니다. 제가 해결한 방법은 'BFS + Binary Search' 입니다. 다른 방법으로는 'BFS + 서로소 집합(Disjoint Set 또는 Union find)'로 해결이 가능하다고 합니다. 후자의 경우엔 제가 아직도 연습이 많이 필요해서 그에 대한 설명은 못 드릴거 같아요. ㅠㅠ 열심히... 할게요(?) 문제에서 크게 신경 쓸 내용은 없습니다. 기본적인 BFS 문제인데 빙..
-
2 - 1. BFS 예제 (백준 7576번: 토마토)CS/ProblemSolving 2019. 2. 25. 19:35
백준 7576(토마토) BFS 문제부터 가져왔습니다.기본적인 BFS 문제이긴 하지만 약간의 발상의 전환이 필요한 문제라 정답율은 꽤 낮은편입니다. 구현은 인접 행렬(2차원 행렬)로 해야 할 것 같아요.구현하기 전에 우선 토마토의 조건이 몇가지가 존재합니다. 조건 1익은 토마토 주변에 덜 익은 토마토가 존재하는 경우: 다음날 덜 익은 토마토가 익은 토마토가 됨. 조건 2토마토는 저절로 익지 않음토마토가 하나라도 안 익는다면? -1 출력 조건 3토마토의 갯수는 정해져있지 않다. 조건 1, 조건 2의 경우는 BFS나 DFS로 구현하면 될 것 같다는 느낌이 듭니다.조건 3은 어떨까요? 이 문제가 어려워지는 조건이라고 볼 수 있겠네요.같이 생각해 봅시다. 물론 토마토(익은 or 덜 익은)가 고정적으로 0개나 1개..
-
2. Breadth/Depth First Search (BFS/DFS: 너비/깊이 우선 탐색)CS/Alogrithm 2019. 2. 20. 21:14
정말 기본적으로 많이쓰이는 탐색 알고리즘 BFS, DFS 입니다. 제가 처음 알고리즘을 시작한것도 이 두 알고리즘으로 했습니다.개념이나 기본 코드 자체는 간단한 편이에요.저 같은 경우엔 초창기 이 알고리즘을 공부 할 때 조금만 난이도만 있어도 손도 못댄 기억이 납니다. 알고리즘도 수학과 마찬가지로 정확한 정의 또는 개념에서 시작한다고 생각이 됩니다.(사실 잘 알고 있다 생각했음에도 상당히 문제를 풀지 못했고.. 현재도 많이 부족하다고 느낍니다. ㅠㅠ) 부족한 저를 위해서라도 다시한번 개념을 잡고 가보겠습니다. ^____^; BFS DFS 완전 탐색 알고리즘그래프, 트리, 행렬 등에서 주로 사용이미 순서가 정해진 데이터를 탐색해 나가는 방법. BFS (Breadth First Search)너비 우선 탐색 ..
-
1 - 2. Binary Search 예제 (백준: 정수 제곱근)CS/ProblemSolving 2019. 2. 17. 16:53
백준 2417(정수 제곱근) 이분 탐색 두번째 예제 입니다. 알고리즘 분류는 되어있지 않아서, 저도 우연히 접하게된 문제입니다.정답율 자체도 크게 낮지 않고, 해결 방법도 여러가지라서 사실 굳이 이렇게 풀지 않으셔도 된다고 말씀드리고 싶네요. 조건 1정수 n (0 ≤ n < 263)long 범위내에 들어오는 수 입니다. 조건 2q2 ≥ n인 가장 작은 음이 아닌 정수 q1. 루트를 씌워서 딱 떨어지는 어떤 수의 제곱수면 상관이 없고2. 소수점이 생기면 그냥 정수형으로 올림해서 출력하면 됩니다.예를들어 n이 15라면, 원래 제곱근은 3.xxxx 겠지만 4를 출력하시면 됩니다. 따라서, 자바의 경우엔 'Math.sqrt()'로 출력하시면 됩니다. 사실 저같은 경우엔 웬만하면 square root 함수를 잘 ..
-
1 - 1. Binary Search 예제 (백준 1072번: 게임)CS/ProblemSolving 2019. 2. 13. 18:12
백준 1072(게임) 이분 탐색의 예제로 풀어볼 문제입니다.실제로 이분 탐색을 대상으로 문제가 나오기보단 대부분 Parametric Search 형태로 문제가 출제됩니다.해당 문제는 Parametric Search로 보시는게 맞다고 생각합니다만, 좀 더 개념확립이 된다면 이 둘에 대한 차이에 대해서도 포스팅을 진행하겠습니다. 정답율이 꽤 낮은편인데도 불구하고 문제해결 아이디어는 생각보다 잘 떠오른 편이라 이 문제를 가져왔습니다.사실 문제 자체가 분류가 안되어있다면, 이분 탐색이 익숙치 않다면 조금 헤맬 수 있는 문제라서 마냥 쉽다고 보긴 어려울 것 같습니다. 우선 아래의 두 조건에 대해 생각해 볼게요. 조건 1앞으로의 모든 게임에서 지지 않는다지지 않는 다는 것은 '이기는 것만 고려한다.'라는 뜻입니다...
-
1. Binary SearchCS/Alogrithm 2019. 2. 10. 18:40
저는 원래 알고리즘을 탐색부터 시작했었는데... 이제와서 생각해보면 사실 그건 조금 안좋은 순서라고 생각이 됩니다.되도록이면 알고리즘 강의를 들으면서 그 커리큘럼에 맞춰 시작하시는게 좋지 않나 싶습니다.물론 현재도 완벽하게 탐색쪽을 잘 푼다 이런건아니지만, 그런 이유를 떠나서 기본기가 가장 중요한 것 같아요. 개인 적으론 DP, 수학 쪽을 주로 공부하면서 생각하는 폭을 넓히고탐색이나 그래프 파트에선 BFS, DFS 등을 접해보시는게 좋을거 같습니다. 그래서 수학이나 DP 부분을 먼저 건드려 보고싶습니다만제가 잘 알지 못하고 또 이해 못한 부분도 많아 이는 나중에 정리하고탐색과 그래프에서 그래도 꽤나 많이 쓰이는 알고리즘부터 정리를 해볼까 합니다. Binary Search 이분 탐색, 이진 탐색 두 부분으..