어쩌다? 프로젝트가 끝난지는 오래되었지만, 규모가 큰 기능을 새로 만들기보다는 기존의 프로젝트에 대해 의미있는 개선을 하자는것이 팀의 생각이었고, 저도 그렇게 생각했습니다. 프로젝트 시작 전 짧게나마 Compose를 경험해보고 편하고, 재미있다라는 생각이 들었지만, 실제 프로젝트에 적용하기에는 조금 무리가 있어서 XML로 개발을 했었습니다. Compose 공부를 하자하자 했지만, 저는 특정 목적을 가지고 공부를 하는편이라 손이 잘 안가는것이 현실이었습니다,, ㅎㅎ 그러다 운이 좋게도 팀원분께서 Compose로 마이그레이션하자고 제안해주셔서 이번 프로젝트에서 맡았던 부분을 Compose로 바꿔보았고, 그에 대한 느낀점? 경험을 적어볼까 합니다. 주관적으로 느낀점이고, 코드도 정답인 코드는 아닌점 확인해주세..
문제 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 문제를 풀다가 어려워서 알고리즘 분류를 봤고, 비트마스킹이 적혀있었다. 저번에 풀었던 외판원 순회라는 문제도 비트마스킹을 사용했고, 비트마스킹을 통해서 도시의 방문처리를 했던 것을 토대로, 숫자들을 사용했는지, 안했는지를 비트마스킹을 통해서 해결했다. 우리는 0~9까지의 숫자를 반드시 하나 이상 사용해야 한다. 이러한 정보를 비트마스킹으로 저장을 한다는 얘기이다. 예를 들어 숫자가 1일경우 visit -> visit | 1 visit | 2방문현황, k->마지막 숫자 즉 DP [1][visit][1] =..
문제 https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 문제 풀이 본론부터 말하면 해당 문제는 LIS 알고리즘을 활용하는 문제이다. 왜 그렇게 생각했느냐에 대해서 얘기해볼까 한다. 우리의 목표는 A와 B를 연결하는 전깃줄이 교차하지 않게 하면서, 최소한의 전깃줄을 제거해야 한다. 그러면 전깃줄이 교차하는 경우는 무엇일까? A의 1번은 B의 8번과 연결되어 있고, A의 2번은 B의 2번과 연결되어 있다. A의 1번 전깃줄을 연결한 상태에서 A의..
문제 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 풀이 가장 긴 증가하는 부분 수열 문제는 알고리즘의 명칭이 있을 정도로 유명한 문제이다. DP를 이용해서 그 수열의 길이를 구한 문제는 풀어본 적이 있지만, 수열의 길이와 그 수열을 구해야 하는 문제는 따져줘야할것이 많기 때문에 DP로 풀면 안 될 거 같은 느낌이 왔다. 기존의 LIS 문제는 N의 크기가 크지 않아서 N^2 알고리즘으로 DP 배열을 계속 업..
문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제 풀이 문제를 꼼꼼히 잘 읽고 흐름을 파악해서 코드를 작성하면 어려운 문제는 아니라고 생각한다. 문제를 풀기 위해 생각해야 할 점은 다음과 같다. 낚시가 진행되는 순서(낚시왕 이동, 상어 잡기, 상어 이동) 상어를 움직이는 로직 같은 칸에 있는 상어 처리하기 이렇게 크게 3개라고 생각한다. 상어를 움직이는 로직은 다양하게 구현할 수 있다. 낚시가 진행되는 순서 낚시가 ..
문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 풀이 알고리즘 자체는 정말 간단하지만 그 내부 구현이 조금은 복잡했던 문제였다. N의 크기가 크지 않고, 이동할 수 있는 방향의 개수가 적어서 충분히 완전탐색으로 풀 수 있을 것이라고 판단을 했다. 하지만 고민은 하나의 배열로 풀 수 있을까였다. 퍼즐을 밀고, 해당 탐색을 마친다면 이전의 퍼즐 배열로 돌아와야하는데 하나의 배열을 이용하면 풀 수 없을 것이라고..
문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 외판원 문제는 유명한 알고리즘 문제이다. TSP라고 하는데, 해당 문제를 풀기 위해서 DP나 Branch & Bound 알고리즘이 사용된다. 처음에는 임의의 출발점에 대해서 모든 최단거리를 구하려고 했지만, 규칙을 발견했다. 1->2->3->4->5->1와 2->3->4->5->1->2의 값이 같다는 사실이다. 이유는 항상 마지막 지점에서 출발..
문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 문제 풀이 시간초과 때문에 정말 고생했던 문제였다. 문제에서 요구한 대로 벽을 부수고, 벽을 부순 시점에서 이동할 수 있는 경로의 수를 구하는 문제이다. 정말 당연하게도 벽인 곳을 큐에 넣어서 BFS를 진행했다. while(!q.isEmpty()) { Queue child = new LinkedList(); Point cur = q.poll(); child.add(cur..
문제 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 풀이 팰린드롬 시리즈는 유명한 문제이다. 팰린드롬에 대해서 간단하게 설명하자면 가운데를 기준으로 일치하는 문자열을 의미한다. 예를 들어서 ABA라는 문자열이 팰린드롬에 해당한다. 그 외에도 문자열의 길이가 1인 문자열도 팰린드롬에 해당한다. 해당 문제를 풀기 전에 팰린드롬에 개념을 알고 문제를 진행하면 풀기 수월하다. ..
