CS/ProblemSolving
-
4 - 1. Disjoint-set 예제 (10216번: Count Circle Groups)CS/ProblemSolving 2019. 11. 29. 17:54
백준 10216번(Count Circle Groups) 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net SW Maestro 10기가 끝났습니다. 최종 결과 나올 때까지 오지게 문제만 풀려다가, 서로소 집합 관련 문제를 올리려 했던 게.. 기억나서 부리나케 왔습니다. ㅎㅎ 따로 분류는 안되어있지만, 저는 서로소 집합으로 해결한 문제를 가져왔습니다. '배열로 처리해서 바로 인접한 그룹의 개수를 센다.'라고 생각하실지도 모르겠지만, 시간 복잡도만 생각해보아도.. 살짝 위험해 보입니다. 또한 인접하..
-
3 - 1. Eratosthenes' Sieve 예제 (1963번: 소수 경로)CS/ProblemSolving 2019. 3. 30. 19:13
백준 1963번(소수 경로) 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 안녕하세요.. 후 요즘 지원서 쓰고 코딩 테스트 본다고 정신이 없네요.ㅠㅠ 자주 글을 올려야 하는데... (자주.. 올려볼게요..) 엇! 근데, 잠깐 안한거같은데.. 많은게 바뀌었네요. ㅎㅎ (티스토리 짱짱맨!) 본론으로 넘어가서... 이 문제는 소수를 탐색하는 문제입니다. 일반적인 예제에서 에라토스테네스의 체만 쓰기엔 좀 아쉬워서 BFS에서 응용하는 문제를 가져와봤습니다. 문제 설명 자체가 한눈에 확 들어오진 않습니다.. 그 와중에 정말 다..
-
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 - 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개..
-
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앞으로의 모든 게임에서 지지 않는다지지 않는 다는 것은 '이기는 것만 고려한다.'라는 뜻입니다...