문제 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인 문자열도 팰린드롬에 해당한다. 해당 문제를 풀기 전에 팰린드롬에 개념을 알고 문제를 진행하면 풀기 수월하다. ..
문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 해당 문제는 MST(Minimum Spanning Tree) 알고리즘을 사용하는 문제이다. 왜냐하면 N개의 정점(별)을 이어서 그래프(별)를 만드는데 최소의 비용을 구하라는 문제이기 때문이다. 원래 MST의 문제라면 정점간의 간선에 가중치를 입력으로 제공하지만, 해당 문제는 각 좌표를 제공해서, 정점 간의 거리까지 구하는 문제이다. 가중치를 제공해주지 않았기 때문에 MST를 제대로 ..
📕문제 https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 🔎문제 풀이 해당 문제는 문제를 읽고 어떤 알고리즘을 사용해서 접근해야 할지 바로 알아야 한다. 친구들의 사탕을 모조리 뺏어버린다 해당 문구를 통해서 유니온 파인드를 통해서 모든 노드의 부모 노드를 설정해야 함을 알 수 있다. 주어진 친구들의 관계를 통해서 묶음으로 친구들을 분류해야 한다. 그리고 얻을 수..
프로젝트를 하면서 Ui State와 Ui Event를 통해서 데이터에 대한 변화와 사용자 입력에 대한 변경사항을 UI에서 반영하도록 코드를 작성했습니다. 하지만 기존 코드의 문제점(?)과 제가 UI Layer에 대한 이해도와, Ui State, Ui Event 코드를 잘못이해한 거 같아서 UI layer에 대한 역할과 state, event에 대해서 공부해봤습니다 ㅎ 개인적으로 공부하고 적은 글이라는 점이라서 정확하지 않을 수 있어요 UI Layer 공식문서에서 권장하는 Clean Architecture중 하나의 영역입니다. UI 레이어에 대한 역할은 다음과 같습니다. 화면에 어플리케이션 데이터를 표시하고, 사용자 상호작용의 기본 지점으로의 역할을 수행하는 것 말이 조금은 딱딱한 감이 있는데, 쉽게 말하..
문제 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 문제 풀이 접근방법에 대해서 정말 난감했던 문제였다. 맨 앞과 뒤로만 접근을 할 수 있다..? -> Dequeue를 써야 해서 옮겨줘야 하나?라고 생각했었다. 하지만 손으로 경우의수를 만들어서 계산을 해보니 이전에 풀었던 문제와 비슷한 느낌이 들었다. https://jja2han.tistory.com/368 [백준 2631] - 줄 세우기(Kotlin)[골드4] 문제 https://www.acmic..
문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 시간초과에 많이 좌절했던 문제였다. 배낭문제랑 비슷해서 접근방법은 배낭문제랑 비슷하게 했다. 특이한 점은 가방마다 보석을 하나 담아야 하기 때문에 그 부분을 신경 써줬다. 우선 입력받은 보석을 정렬했다. 우선 무게 순으로 내림차순 정렬했다. 무게가 같다면 보석의 가치로 내림차순 정렬했다. 이유는 단위무게가 높더라도, 가벼..
문제 https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 문제 풀이 DP 문제로 판단하는 과정은 어렵진 않지만, 어떤 방법으로 풀어야 할지는 아직도 어려운 것 같다. Top-down으로 풀지, Bottom-up으로 풀지, 재귀를 호출할지 등등.. 나는 개인적으로 Bottom-up을선호한다. 해당 문제가 DP인 이유는 이전 선택지에 현재 선택지가 영향을 받기 때문이다. 대부분 나는 이런 문제라고 판단이 되면 DP라고..
문제 https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 문제 풀이 접근방법에 대해서 많은 고민을 했었다. 시간제한이 1초이고, 이닝의 최대수가 50이며, 순서를 결정해야 하는 타자의 명수는 8명이었다. 그렇다면 시간복잡도는 50*8!*@인데, 시간복잡도가 1초는 안넘길거 같아서 타자의 대한 모든 경우의 수를 계산해도 문제가 되지 않을것이라고 판단했다. 8P3인 이유는 4번 타자는 첫번째 선수로 결정되었기 때문이다. 순열에 대한 코드는 정말 간단하다. ..
문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 문제 풀이 모든 좌표에 대해서 종이를 계속 바꿔가면서 붙이고, 최소한의 종이 개수를 구하면 될 것이라고 판단했다. 이유는 배열의 크기가 그렇게 크지 않다. 10*10이므로 n^2이더라도 넉넉하다고 생각했다. 종이의 종류가 많지 않다. 즉 하나의 좌표에서 종이의 종류대로 붙여가면서 확인을 하더라도 크게 시간이 오래 걸리지 않을 것 같았다. 따라서 나는 종이가 들어갈 수 있는 좌표에 대..
