![]()
문제 https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 풀이 문제가 길고, 부연 설명도 많은 편이지만, 한마디로 요약하자면 다빈치 코드라는 게임에서 이기는 최적의 경우를 계산한다고 생각하면 편할 것이다. 당연하게도 상대방이 낼 카드를 알고 있다면, 플레이어는 가장 근소하게 이기거나, 지는 걸 원할 것이다. 즉 문제의 목표는 상대방의 카드에 따라서 가장 적합한 카드를 찾는 것이다. 이렇게 ..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 평소와 같이 DFS/BFS로 생각을 하고 풀었지만, 평범한 DFS/BFS 문제는 아니었다. 테스트케이스에서 주는 혼란을 주는 것도 있었다. 테스크케이스를 예로 들어서 설명해보겠다. [ ICN, SFO] , [ICN, ATL] , [SFO, ATL] , [ATL, ICN], [ATL, SFO]라는 티켓이 있다. 0번 index -> 1번 index로의 값은 항공권으로 갈 수 있다는 ..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제가 굉장히 길었지만, 실제로는 문제의 유형을 알고 있다면 쉽게 풀 수 있는 문제였다. 내가 느끼기에 문제의 유형을 파악할 수 있는 부분은 다음과 같았다. 모든 섬을 최소한의 비용으로 연결해라! 다리를 여러번 건더더라도, 도달할 수 있으면 통행이 가능하다 다음 정보를 통해서 해당 문제는 MST(Minimum Spanning Tree)라고 생각했다. MST 문제도 주어진 N개의 ..
![]()
어쩌다? 프로젝트가 끝난지는 오래되었지만, 규모가 큰 기능을 새로 만들기보다는 기존의 프로젝트에 대해 의미있는 개선을 하자는것이 팀의 생각이었고, 저도 그렇게 생각했습니다. 프로젝트 시작 전 짧게나마 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의 크기가 크지 않고, 이동할 수 있는 방향의 개수가 적어서 충분히 완전탐색으로 풀 수 있을 것이라고 판단을 했다. 하지만 고민은 하나의 배열로 풀 수 있을까였다. 퍼즐을 밀고, 해당 탐색을 마친다면 이전의 퍼즐 배열로 돌아와야하는데 하나의 배열을 이용하면 풀 수 없을 것이라고..
