본문 바로가기

분류 전체보기134

[Android, 내일배움캠프] 공부일지(2024-06-28) 오늘 공부한 내용 정리(2024년 6월 28일)  코드카타 문제풀이게임(Silver 3, 1072번)문제 내용 문제 풀이 방법게임 횟수(X)와 이긴 게임의 개수(Y)가 주어질 때, Z는 현재 승률이다. 형택이가 게임을 몇 번 이겨야 Z가 변하는지 출력.  해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamReaderprivate var winRate = 0private var games = 0private var winCnt = 0fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val input = readLine().split(" ").map { it.. 2024. 6. 28.
[Kotlin, 내일배움캠프] 공부일지(2024-06-27) 오늘 공부한 내용 정리(2024년 6월 27일)  코드카타 문제풀이염색체(Silver 3, 9342번, 마라톤)문제 내용 문제 풀이 방법입력받은 문자열이 사진에 정의된 규칙을 만족하면 Infected! 를, 그렇지 않으면 Good를 출력.  해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamReaderfun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val case = readLine().toInt() for (i in 0 until case) { val string = readLine() val regex = Regex(".. 2024. 6. 27.
[Kotlin, 내일배움캠프] 공부일지(2024-06-26) 오늘 공부한 내용 정리(2024년 6월 26일)  코드카타 문제풀이숫자 게임(Silver 5, 2303번, 마라톤)문제 내용 문제 풀이 방법N명의 사람들에게 5장의 카드가 주어질 때, 5장의 카드에서 3장의 카드를 뽑은 후, 뽑은 카드의 합에서 일의 자리가 가장 크게 되도록 카드를 선택해야 할 때, 각각의 사람들의 일의 자리 중 가장 큰 값을 뽑은 사람이 몇 번째 사람인지 출력.일의 자리가 제일 큰 사람이 여러 명이면 번호가 가장 큰 사람의 번호를 출력한다(그냥 가장 나중에 입력받은 사람이 우선이라는 뜻이다).  해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamReaderfun main() = with(BufferedReader.. 2024. 6. 26.
[알고리즘] 매개변수 탐색(Parametric Search)과 이분 탐색(Binary Search) 내가 작년에 바이너리 서치에 대해 올린 적이 있다.이번에 문제 풀이에서 바이너리 서치와 매개변수 탐색을 이용하는 문제를 풀고 다시 개념을 공부해보려 한다.  이분 탐색 복습(Binary Search)이분 탐색을 간단하게 복습을 해보자.아래 gif을 보면 이분 탐색이 어떻게 돌아가는지 바로 이해를 할 수 있을 것이다. 아래가 일반 검색 방법이고 위가 이분 탐색 방법인데,일반 탐색과는 다르게 중간 지점과 시작점, 끝지점을 정해서 중간값을 찾아야 하는 값과 비교 후 대소에 따라 범위를 줄여가면서 탐색한다.이분 탐색은 리스트가 정렬되어있어야 한다는 점이 특징이다.중간값을 기준으로 대소를 비교하기 때문에 조건에 부합하지 않은 절반의 데이터를 걸러가면서 탐색하기 때문에 탐색 시간이 효과적으로 줄어든다.  매개 변수.. 2024. 6. 26.
[Android, 내일배움캠프] 공부일지(2024-06-25) 오늘 공부한 내용 정리(2024년 6월 25일)  코드카타 문제풀이트리의 부모 찾기(Silver 2, 11725번)문제 내용 문제 풀이 방법루트가 1인 트리가 있고 트리 상 연결된 노드들의 정점이 주어질 때, 2번 노드부터 각 노드의 부모 노드를 순서대로 출력.  해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamReaderimport java.util.LinkedListimport java.util.Queueprivate var graph = arrayOf>()private var visited = booleanArrayOf()private var parentNode = arrayOf()fun main() = with(Buffe.. 2024. 6. 25.
[Android, 내일배움캠프] 공부일지(2024-06-24) 오늘 공부한 내용 정리(2024년 6월 24일)  코드카타 문제풀이단지 번호 붙이기(Silver 1, 2667번)문제 내용 문제 풀이 방법1이 집이 있는 곳, 0이 집이 없는 곳일 때, 아파트 단지의  개수와 각 단지 내 집의 개수를 오름차순으로 정렬해 출력.이 문제에서 아파트 단지의 정의는 1이 2개 이상 연결되어 있지 않고 1이 각각 따로 떨어져 있어도 개별의 단지로 인식한다.  해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamReaderprivate val dx = listOf(-1,1,0,0)private val dy = listOf(0,0,-1,1)private var graph = arrayOf>()private va.. 2024. 6. 24.
[알고리즘] 매내처 알고리즘(Manacher) 개념 매내처 알고리즘이란?문자열 S가 주어질 때, 팰린드롬 부분 문자열을 찾는 알고리즘을 뜻한다. 팰린드롬 부분 문자열은 S의 부분 문자열 중 팰린드롬인 경우를 의미한다(banana에서 anana가 부분 문자열 팰린드롬이다).모든 i에 대해 i번 문자가 중심인 최대 길이의 팰린드롬 부분문자열을 검색하는 알고리즘.팰린드롬의 길이는 주로 팰린드롬의 반지름의 형태로 저장된다(반지름이란, 팰린드롬의 중심으로부터 가장 먼 문자가 얼마나 떨어져 있는지를 확인하기 위한 것이다(aba에서 반지름은 1이 된다).팰린드롬의 길이가 i라면 반지름은 (i -1) / 2가 된다. 매내처 알고리즘을 알아보기 전에 팰린드롬이 정확히 무엇인지 짚고 넘어가자. 팰린드롬(회문, palindrome)뒤집어도 같은 문자열을 뜻한다.거꾸로 읽어도.. 2024. 6. 24.
[알고리즘] 그래프 탐색 알고리즘(DFS, BFS) 그래프 탐색이란?많은 양의 데이터들 중에서 원하는 데이터를 찾는 과정을 탐색이라고 하는데,그래프에서 원하는 데이터를 찾는 과정을 그래프 탐색이라 부른다. 그래프 탐색 알고리즘에는 DFS, BFS가 있다.DFS(Depth-First Search): 깊이 우선 탐색BFS(Breadth-First Search): 너비 우선 탐색 깊이 우선 탐색(DFS)깊이 우선 탐색 알고리즘은 그래프의 자식 데이터에 들어간 후, 자식의 자식 데이터를 자식의 자식의 자식 데이터를 들어가는 식으로, 한 가지를 끝까지 파고 들어가서 탐색하는 알고리즘을 뜻한다. 한 줄기를 끝까지 파고든 후, 다음 줄기로 이동해 다시 끝까지 파고드는 방식으로 작동하는 알고리즘이다.  너비 우선 탐색(BFS)너비 우선 탐색은 시작 데이터에서 자신의 자.. 2024. 6. 22.
[Android, 내일배움캠프] 공부일지(2024-06-21) 오늘 공부한 내용 정리(2024년 6월 21일)  코드카타 문제풀이수면 패턴(마라톤 문제, Bronze 1, 19843번)문제 내용 문제 풀이 방법수면 횟수만큼 수면 시작일, 시간과 수면 종료일 시간이 주어졌을 때, 수면 시간을 구해서 모두 더한 값이 주말에 풀로 잘 수 있는 시간(48시간) 보다 크다면 -1을 출력, 충분히 잠을 잔 경우에는 0을, 그 이외의 경우는 주말에 자야 하는 시간을 출력한다.  해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamReaderfun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val (sleepHour, case) =.. 2024. 6. 21.
[Android, 내일배움캠프] 공부일지(2024-06-20) 오늘 공부한 내용 정리(2024년 6월 20일)  코드카타 문제풀이진법 변환(Bronze 2, 2745번)문제 내용 문제 풀이 방법B진법 수 N이 주어질 때 N을 10진법으로 변환해서 출력.  해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamReaderfun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val (num, decimal) = readLine().split(" ") println(num.toInt(decimal.toInt()))} 풀이 과정num(변경할 수)과 decimal(변환할 진법)을 입력받는다.num을 decimal 진법으로 변환.. 2024. 6. 20.
[Android, 내일배움캠프] 공부일지(2024-06-19) 오늘 공부한 내용 정리(2024년 6월 19일)  코드카타 문제풀이절댓값 힙(Silver 1, 11286번)문제 내용 문제 풀이 방법데이터를 입력받다가 리스트에서 절댓값이 가장 작은 값들 중 원본 값이 가장 작은 값을 리스트에서 제거한다. 리스트가 비어있으면 0을 출력.  해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamReaderimport java.util.*import kotlin.math.absfun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val numbers = readLine().toInt() // o1, o2를 절댓값으로 비교 후 .. 2024. 6. 19.
[Android, 내일배움캠프] 공부일지(2024-06-18) 오늘 공부한 내용 정리(2024년 6월 18일)  코드카타 문제풀이프린터 큐(Silver 3, 1966번)문제 내용 문제 풀이 방법문서의 개수인 N과 큐에서 출력할 데이터의 index인 M이 주어지고 중요도가 숫자로 N개가 주어질 때, M에 해당하는 데이터가 몇 번째로 뽑히는지 출력.  출력 순서가 많이 헷갈릴 수 있는 문제이다. 입력 예시가6 01 1 9 1 1 1이면, 0번째 index의 값인 첫 번째 1을 값으로 잡아야 한다. 하지만 1이 첫 번째에 있다고 무턱대고 뽑으면 안 된다. 뒤에 우선순위가 더 높은 9가 있기 때문이다. 9를 먼저 빼고 나면 다음과 같이 된다.1 1 1 [1] 1가장 큰 값이었던 9를 출력했으니 출력을 1번 한 상태이다.이제 위 큐에서 최댓값은 1이기 때문에 1을 계속 제거.. 2024. 6. 18.
[알고리즘] 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘이란?그리디 알고리즘(탐욕법)이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 뜻한다. 그리디 알고리즘은 동적 프로그래밍(DP)을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안해 고안되었다. 그리디 알고리즘은 현재 상황에서 가장 좋은 결과를 선택해 나가는 방식의 알고리즘 설계 기법이다.하지만 이 가장 좋은 결과는 항상 최종적인 결과 도출에 대한 최적해를 보장해 주는 것은 아니다.   위 그림에서 가장 큰 값이 최적의 값일 때, 그리디 알고리즘은 현재 상황에서 가장 최적의 값을 구하기 때문에최종적인 답은 23이 나오게 된다(최적의 값: 128). 그리디 알고리즘은 항상 최종적인 결과 도출에 최적해를 보장해 주는 것이 아니기 때문에 상황에 맞게 사용해야 한.. 2024. 6. 18.
[Android, 내일배움캠프] 공부일지(2024-06-17) 오늘 공부한 내용 정리(2024년 6월 17일)  코드카타 문제풀이회의실 배정(Silver 1, 1931번)문제 내용 문제 풀이 방법회의의 개수 n과 n번의 회의 시작 시간과 끝 시간이 순서대로 주어질 때, 위의 시간을 최대한 활용해 사용할 수 있는 회의의 최대 개수를 출력한다.회의의 진행시간이 적은 순으로 정렬하면 편하다. 해결 코드(스포 주의)더보기import java.io.BufferedReaderimport java.io.InputStreamReaderfun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val meetingArray = Array>(readLine().toInt()) { emptyList() } for.. 2024. 6. 17.
[Kotlin] 공부일지(2024-06-15) 오늘 공부한 내용 정리(2024년 6월 15일)  1. 알고리즘 문제풀이A. 2xn 타일링 2(백준, S3, 11727번)문제 내용 문제 풀이 방법2 x n의 직사각형을 타일 1 x 2, 2 x 1, 2 x 2로 빠짐없이 채우는 경우의 수를 구해 출력.  해결 코드(스포 주의)더보기import java.util.Scannerfun main() = with(Scanner(System.`in`)) { val fillArray = Array(nextInt()) { 0 } for (i in fillArray.indices) { if (i == 0) fillArray[0] = 1 else { // 홀수 index임 if (i % 2 != .. 2024. 6. 15.
728x90

티스토리툴바