문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 어떻게 풀 것인가? 문제를 처음 봤을 때 우선적으로 백트레킹을 이용한 순열과 조합을 떠올렸다. 하지만 중요한 한 부분을 놓쳐서 계속 문제를 틀렸는데, 이는 문제에서 "암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다." 라는 부분을 놓쳤다. 이에 그래서 모음의 갯수를 카운트하는 로직을 구성하여 문..
RelativeLayout이란 상대 뷰의 위치를 기준으로 정렬하는 레이아웃 클래스이다. 즉, 화면에 이미 출력된 특정 뷰를 기준으로 방향을 지정하여 배치한다. 사용되는 속성 android:layout_above : 기준 뷰의 위쪽에 배치 android:layout_below : 기준 뷰의 아래쪽에 배치 android:layout_toLeftOf : 기준 뷰의 왼쪽에 배치 android:layout_toRightOf : 기준 뷰의 오른쪽에 배치 align 속성 상대 뷰의 어느 쪽에 맞춰서 정렬할지를 정하는 속성이다. 사용되는 속성 android:layout_alignTop : 기준 뷰와 위쪽을 맞춤 android:layout_alignBottom : 기준 뷰와 아래쪽을 맞춤 android:layout_al..
LinearLayout이란 LinearLayout은 뷰를 가로나 세로 방향으로 나열하는 레이아웃 클래스이다. orientation이라는 속성을 통해서 horizontal(가로)이나 vertical(세로)값을 방향을 지정한다. LinearLayout은 방향만 설정하면 뷰를 추가한 순서대로 나열한다. 화면에서 벗어나더라도 줄을 자동으로 바꾸지 않는다. 위 그림 처럼 만약 LinearLayout의 orientation 속성 값을 vertical로 지정했다면 세로로 나열하고, horizontal로 나열한다면 가로로 나열한다. 방향만 설정한다면 뷰를 추가한 순서대로 나열한다. 그렇다면 가로세로가 중첩된 구조는 LinearLayout으로 만들 수 없을까? 아니다. 이럴 때는 LinearLayout을 중첩하면 된다...
문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 어떻게 풀 것인가? DFS를 이용한 탐색을 사용하였다. 추후에 포스팅을 통해서 설명할테지만, 범위가 크다면 StackOverFlow를 피하기 위해서 재귀보다는 Stack을 이용한 DFS 방식을 사용하는 것을 선호한다. DFS를 이용하여 음식물 쓰레기의 영역 범위를 구하고 가장 큰 값을 반환하면 된다. 이는 코드를 통해서 보는 것이 훨씬 쉽다. 풀면서 ..
문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 어떻게 풀 것인가? BFS나 DFS를 이용한다면 간단하게 문제를 풀 수 있다. 탐색을 통해서 영역의 갯수를 구하고 그러한 수를 리스트에 넣어서 답을 도출하면 된다. 딱히 풀이 할 게 없지만, 몇몇 실수는 있었다. 변수의 갯수가 늘어서 간단한 것들을 놓쳤다. 풀면서 놓쳤던점 변수의 양이 늘어나면 실수를 한다는 점을 발견했다. 항상 꼼꼼하게 보자. 이 문제를 통해 얻어갈 것 ..
문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 어떻게 풀 것인가? Stack을 이용한 DFS를 활용하여 문제를 풀어야한다. DFS를 통해서 접근한 영역의 갯수와 영역의 넓이를 구한다면 아주아주 쉽게 문제를 풀 수 있다. 풀면서 놓쳤던점 DFS에서는 2가지의 방식으로 문제를 풀 수 있다. 바로 재귀와 Stack을 활용한 방법이다. 다만, 재귀를 통해서 문제를 푼다면 StackOverFlow가 발생한다. 이러한 부분을 처음에 놓쳐서 문제를 다시 ..
문제 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 어떻게 풀 것인가? 우선적으로 DP에 대한 풀이를 떠올렸다. 하지만 DP 즉 점화식으로 풀려고하니 좀 머리가 아프고 직관적이지 못하다는 생각이 들었다. 그래서 HashMap을 이용한 메모제이션 기법을 이용하기로 생각했다. 문제에서 주어진 재귀함수는 중복 계산이 많이 발생하므로, 메모이제이션(Memoization)을 사용하여 중복 계산을 피할 수 있다. 메모이제이션은 한 번 계산한 값을 저장해두고..
