전체 글397

• [백준/BOJ] 15469번: N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 해설 백트래킹을 이용하여 만족하는 조건을 찾았다면 직전 단계로 돌아가 다른 경우의 수를 찾으면 된다. 소스 코드 import java.io.BufferedReader import java.io.InputStreamReader .. PS(Problem Solving)/BOJ 2022. 1. 10.

• [백준/BOJ] 2606번: 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 .. PS(Problem Solving)/BOJ 2022. 1. 7.

• [백준/BOJ] 11726번: 2×n 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 해설 dp를 사용하여 문제를 풀었다. 우선 n에 따른 경우의 수를 보자. n = 1일 경우 경우의 수는 (l) 하나이다. n = 2라 하면 (ll, =)로 2가지 경우가 있다. n = 3일 경우 (lll, l=, =l) 3가지 경우가 있다. n = .. PS(Problem Solving)/BOJ 2022. 1. 6.

• [백준/BOJ] 1463번: 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 해설 단순히 문제대로만 코드를 짜 보면 오답을 만나게 될 것이다. 예를 들어 10을 보면 10 / 2, 5 - 1, 4 / 2, 2 / 2를 통해 4번이 나오겠지만 10 - 1, 9 / 3, 3 / 3이라는 3번의.. PS(Problem Solving)/BOJ 2022. 1. 5.

• [백준/BOJ] 9095번: 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 해설 DP(다이나믹 프로그래밍, 동적 프로그래밍)를 이용하여 문제를 해결하였다. n = 2일 때 경우의 수는 1이고 n = 3일 때 경우의 수는 2 n = 4일 때는 4, n = 5일 땐 7이다. 우리.. PS(Problem Solving)/BOJ 2022. 1. 3.

• [백준/BOJ] 10815번: 숫자 카드, 1920번: 수 찾기 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 해설 이중 반복문을 실행하거나 contains 함수를 이용하여 문제를 풀 수 있지만 시간 초과가 발생하게 된다. 이를 해결하기 위해 이진 탐색을 이용하였다.. PS(Problem Solving)/BOJ 2022. 1. 2.

• [백준/BOJ] 5568번: 카드 놓기 https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 문제 상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까? 예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, .. PS(Problem Solving)/BOJ 2022. 1. 1.

• [백준/BOJ] 11576번: Base Conversion https://www.acmicpc.net/problem/11576 문제 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 세계에서도 프로그래밍을 하고 싶었던 정이는 백준 사이트에 접속하여 문제를 풀기로 하였다. 그러나 미래세계는 A진법을 사용하고 있었고, B진법을 사용하던 정이는 문제를 풀 수가 없었다. 뛰어난 프로그래머였던 정이는 A진법으로 나타낸 숫자를 B진법으로 변환시켜주는 프로그램을 작성하기로 하였다. N진법이란, 한 자리에서 숫자를 표현할 때 쓸 수 있는 숫자의 가짓수가 N이라는 뜻이다. 예를 들어 N은 17일 때 한 자릿수에서 사용할 수 있는 수는 0,.. PS(Problem Solving)/BOJ 2021. 12. 31.

• [백준/BOJ] 2447번: 별 찍기-10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/.. PS(Problem Solving)/BOJ 2021. 12. 30.

• [백준/BOJ] 11656번: 접미사 배열 https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 문제 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다. baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다. 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오. 해설 입력받은 문자열의 길이만큼 .. PS(Problem Solving)/BOJ 2021. 12. 29.

• [백준/BOJ] 1380번: 귀걸이 https://www.acmicpc.net/problem/1380 1380번: 귀걸이 입력은 번호를 가진 시나리오들로 구성됩니다. 시나리오 번호는 1부터 순서대로 증가하고, 각 시나리오는 아래의 내용을 포함합니다. 한 줄에 귀걸이를 압수당한 여학생의 수, n (1 ≤ n ≤ 100)이 www.acmicpc.net 문제 파스칼 고등학교에 다니는 많은 여학생들은 규정에 없는 귀걸이를 착용한 채 도망 다닙니다. Sneddon 교감선생님은 흔들거리는 긴 빨간 귀걸이들을 볼 때마다 압수합니다. 교감선생님은 귀걸이를 압수당한 여학생들을 숫자를 매겨 리스트를 작성하고 있습니다. 그리고 압수한 귀걸이 뒤쪽에 여학생 번호와 마음대로 선택한 'A' 또는 'B'를 함께 적어두었습니다. 모든 정규 일과와 방과 후 수업의 감금.. PS(Problem Solving)/BOJ 2021. 12. 27.

• 

  코틀린(kotlin) - 리플렉션: 실행 시점에 코틀린 객체 내부 관찰 리플렉션을 간단하게 말하면 실행 시점에 동적으로 객체의 프로퍼티와 메소드에 접근할 수 있게 해주는 방법이다. 보통 객체의 메소드나 프로퍼티에 접근할 때, 컴파일러는 메소드나 프로퍼티의 이름이 실제로 가리키는 선언을 컴파일 시점에 찾아내 해당하는 선언이 실제 존재함을 보장한다. 하지만 타입과 관계없이 객체를 다뤄야 하거나 객체가 제공하는 메소드나 프로퍼티 이름을 오직 실행 시점에만 알 수 있는 경우라면 리플렉션을 사용해야 한다. 코틀린에서 리플렉션을 사용하기 위해선 두 가지의 다른 리플렉션 API를 다뤄야 한다. 첫 번째는 자바가 java.lang.reflect 패키지를 통해 제공하는 표준 리플렉션이다. 코틀린 클래스는 일반 자바 바이트코드로 컴파일되므로 자바 리플렉션 API도 코틀린 클래스를 컴파일한 바.. Programming/Kotlin 2021. 12. 26.

• [백준/BOJ] 1251번: 단어 나누기 https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 문제 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다. 각각은 적어도 길이가 1 이상인 단어여야 한다. 이제 이렇게 나눈 세 개의 작은 단어들을 앞뒤를 뒤집고, 이를 다시 원래의 순서대로 합친다. 예를 들어, 단어 : arrested 세 단어로 나누기 : a.. PS(Problem Solving)/BOJ 2021. 12. 22.

• [백준/BOJ] 1343번: 폴리오미노 https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 문제 민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB 이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다. 폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오. 해설 AAAA와 BB인 폴리오미노 2개가 무한히 있다 한다. 나는 입력한 문자열의 길이만큼 반복문을 만들어 각 위치에 있는 문자가 X인지 .인지를 먼저 구분하였다. X일 때 cnt를 한개씩 늘.. PS(Problem Solving)/BOJ 2021. 12. 19.

• 

  코틀린(kotlin) - 애노테이션 선언과 적용 애노테이션 적용 코틀린에선 자바와 같은 방법으로 애노테이션을 사용할 수 있다. 적용하려는 대상 앞에 애노테이션을 붙이는 것이다. 애노테이션은 @와 애노테이션 이름으로 이뤄지며 함수나 클래스 등 여러 다른 코드 구성 요소에 붙일 수 있다. import org.junit.* class MyTest { @Test fun testTrue() { Assert.assertTrue(true) } } 애노테이션에 인자를 넘길 때는 일반 함수와 마찬가지로 괄호 안에 인자를 넣는다. @Deprecated("Use removeAt(index) instead.", ReplaceWith("removeAt(index)")) fun remove(index: Int) { ... } 이런 remove 함수 선언이 있다면 remove를.. Programming/Kotlin 2021. 12. 19.

• 

  코틀린(kotlin) - 애노테이션 선언과 적용 에노테이션 적용 코틀린에선 자바와 같은 방법으로 애노테이션을 사용할 수 있다. 적용하려는 대상 앞에 애노테이션을 붙이는 것이다. 애노테이션은 @와 애노테이션 이름으로 이뤄지며 함수나 클래스 등 여러 다른 코드 구성 요소에 붙일 수 있다. import org.junit.* class MyTest { @Test fun testTrue() { Assert.assertTrue(true) } } 애노테이션에 인자를 넘길 때는 일반 함수와 마찬가지로 괄호 안에 인자를 넣는다. @Deprecated("Use removeAt(index) instead.", ReplaceWith("removeAt(index)")) fun remove(index: Int) { ... } 이런 remove 함수 선언이 있다면 remove를.. Programming/Kotlin 2021. 12. 19.

• [백준/BOJ] 1021번: 회전하는 큐 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 문제 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., a.. PS(Problem Solving)/BOJ 2021. 12. 15.

• [백준/BOJ] 10866번: 덱 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여덟 가지이다. push_front X: 정수 X를 덱의 앞에 넣는다. push_back X: 정수 X를 덱의 뒤에 넣는다. pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. p.. PS(Problem Solving)/BOJ 2021. 12. 14.

• [백준/BOJ] 1966번: 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.. PS(Problem Solving)/BOJ 2021. 12. 13.

• 

  코틀린(kotlin) - 변성: 제네릭과 하위 타입 변성(variance)은 List와 List )와 같이 기저 타입이 같고 타입 인자가 다른 여러 타입이 서로 어떤 관계가 있는지 설명하는 개념이다. 변성이 있는 이유: 인자를 함수에 넘기기 String 클래스는 Any를 확장하므로 Any 타입 값을 파라미터로 받는 함수에 String 값을 넘겨도 절대 안전하다. 하지만 Any와 String이 List 인터페이스의 타입 인자로 들어가는 경우에는 절대 안전하다고 말할 수 없다. 리스트의 내용을 출력하는 함수를 보자. fun printContents(list: List) { println(list.joinToString()) } >>> printContents(listOf("abc", "bac")) abc, bac 이 경우에는 각 원소를 Any로 취급하며 모든.. Programming/Kotlin 2021. 12. 12.