전체글397

• 

  [백준/BOJ] 16202번: MST 게임 문제 https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 해설 제목에서부터 알 수 있듯이 MST를 응용하는 문제이다. 최소 신장 트리를 구하기 위해 크루스칼 알고리즘을 사용하였다. 문제에서 가장 중요한 문장은 아래 문장이다. 각 턴이 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거한다. 결론적으로는 한 턴이 끝날 때마다 가장 작은 간선을 제거하여 k만큼 .. PS(Problem Solving)/BOJ 2022. 8. 12.

• 

  [백준/BOJ] 2146번: 다리 만들기 문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 해설 문제를 해결하기 위한 과정을 생각해보자. 섬을 구분한다. 각각의 섬을 연결할 때, 최소의 다리 수로 이어질 수 있도록 한다. 크게 두 가지로 나눌 수 있다. 1번 과정부터 보자. 입력에 육지인 부분은 1로 들어온다. 나는 섬을 1, 2, 3의 번호로 나눌 것이기 때문에, 1이 들어오면 -1로 저장을 해주었다. 모든 입력을 받은 후, 아직 방문하지 않은 육지인 곳이 있다면 bfs를 수행시켜준다.. PS(Problem Solving)/BOJ 2022. 8. 11.

• 

  [백준/BOJ] 11779번: 최소비용 구하기 2 문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 해설 https://jjunsu.tistory.com/249에서 했던 1916번: 최소비용 구하기 문제의 상위 버전이다. 최소 비용을 구한 후, 몇 개의 도시를 거쳤는지, 어떤 도시를 방문했는지를 같이 출력해야 한다. 최소 비용을 구하는 방법은 위 문제와 같이 다익스트라 알고리즘을 사용하여 구하면 된다. 이제 어떠한 도시를 거쳤는지 경로를 알아야 한다. 어렵게.. PS(Problem Solving)/BOJ 2022. 8. 10.

• 

  [Android] Android Naming Convention(안드로이드 네이밍 컨벤션) Naming Convention 코드 컨벤션 중 하나이다. 소스 코드와 문서에 있는 변수명, 타입, 함수명 등의 식별자에 사용되는 문자열을 정할 때 사용되는 규칙이다. 각각의 언어, 프로젝트, 개발 도구에 따라 다르다. 3번째에서 알 수 있듯이, 네이밍 컨벤션은 안드로이드에서 뿐만 아니라 다른 언어에서도 쓰이며, 각각 다른 규칙을 가지고 있다. 네이밍 컨벤션의 주목적은 가독성을 높이는 것이다. 이를 사용함으로써 협업을 할 때, 팀원 또는 자신이 다른 사람이 작성한 코드를 보다 빠르게 이해할 수 있으며, 팀의 생산성과 효율성을 증가시킬 수 있다. 꼭 협업을 하지 않더라도, 자신의 코드를 관리하기에도 필요하다. 그럼 안드로이드의 네이밍 컨벤션에 대해서 알아보도록 하자. 안드로이드에서의 네이밍 컨벤션은 XML.. Android 2022. 8. 9.

• 

  [백준/BOJ] 1956번: 운동 문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 해설 플로이드 와샬 알고리즘을 사용하여 해결할 수 있는 문제이다. 우선 초기값을 설정할 배열을 map이라 하자. map을 INF(100000000)으로 초기화해주었다. 이후 플로이드 와샬 알고리즘을 수행하여 각 정점에서 각 정점까지의 최단 경로를 구해준다. 플로이드 와샬 알고리즘의 수행이 끝났다면, 사이클을 찾아야 한다. map[i][j]와 map[j][i].. PS(Problem Solving)/BOJ 2022. 8. 9.

• 

  [백준/BOJ] 2458번: 키 순서 문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 해설 플로이드 와샬 알고리즘을 사용해서 문제를 해결하였다. 초기값을 저장할 배열을 BooleanArray로 선언하여 입력으로 알 수 있는 학생들끼리의 관계를 true로 해준다. 이 때 배열[i][j] = true라면, i가 j보다 작다가 되고, 배열[j][i] = true라면, j가 i보다 작다가 된다. 플로이드 와샬 알고리즘을 수행하며, 배열[i][k]와 배열[k][j]가 모두 참일 시, 배.. PS(Problem Solving)/BOJ 2022. 8. 9.

• 

  [백준/BOJ] 11404번: 플로이드 문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해설 문제의 이름에서부터 알 수 있듯이 플로이드 와샬 알고리즘을 사용하면 된다. n의 범위가 (2 ≤ n ≤ 100)이고, m의 범위가 (1 ≤ m ≤ 100,000)이기 때문에 각 노드 사이의 비용 초기값을 10,000,000으로 설정하였다. 이 문제에서 주의할 점은 다음과 같다. 시작 도시와 도착 도시가 같은 경우는 없다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. .. PS(Problem Solving)/BOJ 2022. 8. 8.

• [백준/BOJ] 11403번: 경로 찾기 문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 플로이드 와샬 알고리즘을 사용하여 해결할 수 있는 문제이다. 플로이드 와샬 알고리즘의 기본 문제인만큼 플로이드 와샬에 대해 잘 모른다면 플로이드 와샬을 읽어보면 좋을 것이다. 0이면 간선이 존재하지 않고, 1이면 간선이 존재한다. 그렇다면 예시를 들어보자. 1 - 3은 간선이 없다하고, 1 - 2와 2 - 3은 간선이 있다고 하자. 그렇다면 1 - 2는 1이고 2 - 3은 1이므로 1 - 2 - 3이 되어 1 - 3은 간선이 존.. PS(Problem Solving)/BOJ 2022. 8. 8.

• 

  [알고리즘] 플로이드 와샬(Floyd Warshall) 플로이드 와샬(Floyd Warshall) 알고리즘이란? 이전에 공부했던 다익스트라 알고리즘은 특정 정점에서 시작하여 다른 특정 정점 또는 모든 정점으로의 최단 경로를 구하는 알고리즘이었다. 플로이드 와샬 알고리즘 또한 다익스트라 알고리즘과 같이 최단 경로를 구하는 알고리즘이다. 다만 다익스트라 알고리즘과의 차이점은 "모든 정점에서 모든 정점으로의 최단 거리"를 구하는 알고리즘이라는 것이다. 또한 다익스트라 알고리즘에서는 가장 적은 비용을 하나씩 선택하며 알고리즘을 수행했지만, 플루이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 또한 다이나믹 프로그래밍 알고리즘에 의거한다. 동작 단계 위의 그래프를 예시로 들어보겠다. 이 때, 각 정점이 다른 정점으로 가는 비용을 배열의 형태로 보면 .. Algorithm 2022. 8. 8.

• 

  [백준/BOJ] 1520번: 내리막 길 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 해설 DFS로만으로 풀려다가 도저히 풀리지 않아 다른 분들이 써놓은 풀이를 참고하였다. DFS만을 이용하면 시간초과가 나게 되어 DP를 함께 사용하는 방법을 알 수 있었다. 각 현재 지점에서 4방향으로 탐색을 한다. 이 때 갈 수 있는 경우의 수를 저장하면서, DFS를 수행하게 된다. 만약 이미 탐색했던 지점이라면, 그 지점에서 갈 수 있는 경로의 수를 반환해준다. 도착 지점에 도착하게 되면 1을.. PS(Problem Solving)/BOJ 2022. 8. 8.

• 

  코틀린(kotlin) - 우선순위큐(PriorityQueue) 정렬 기준 백준 또는 CodeForce 등을 풀다보면 우선순위 큐를 사용할 일이 많다. 이 때 우선 순위 큐에 들어가는 자료형이 Int, Double, String 등 한개로만 이루어져 있다면, 아무 조건없이 넣었을 때 오름차순으로 정렬될테고, reverseOrder() 명령어를 통해 역순으로 정렬할 수도 있다. val pq = PriorityQueue() pq.add(1) pq.add(2) pq.add(3) val rpq = PriorityQueue(reverseOrder()) rpq.add(1) rpq.add(2) rpq.add(3) /* pq -> 1, 2, 3 rpq -> 3, 2, 1 */ 하지만 자료형이 하나가 아닌, Pair 또는 Triple 혹은 데이터 클래스와 같은 것을 PriorityQueue의 .. Programming/Kotlin 2022. 8. 7.

• 

  [Android] View(뷰), Widget(위젯), Layout(레이아웃) 모든 애플리케이션의 기초가 되는 것은 View, Widget, Layout이다. 이들에 대해 알아보자. View(뷰) View란 무엇인가? 단순 해석해보면 "보다"이다. 말그대로 View는 우리가 볼 수 있는 화면을 구성하는 모든 구성 요소이다. 네이버 웹툰을 예시로 들어보겠다. 네이버 웹툰은 각각의 웹툰들과, 광고, 버튼 등으로 이루어져 있다. 이들은 모두 View다. 이처럼 사용자가 눈으로 확인할 수 있는 아이콘, 이미지, 텍스트, 버튼 등등 모두 View라고 할 수 있다. 그렇다면 눈에 보이는 것만 뷰일까? 아니다. 눈에 보이지 않는 뷰도 있다. 보이는 뷰는 Widget이라 하며, 보이지 않는 뷰는 Layout이라 한다. 뷰는 뷰 자체로도 존재할 수 있지만, 뷰 안에 또 다른 n개의 뷰가 들어갈 수.. Android 2022. 8. 7.