Cloud.log

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 설명 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + ..

7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 설명 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다. 예시) 이름 (몸무게, 키) 덩치..

1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 설명 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 풀이 예를 들어 단어가 GCF와 ACDEB일 때, 100*G + 10*C + F*1, 10000*A + 1000*C + 100*D + 10*E + B*1. Solut..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 설명 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 1로 연결된 곳은 하나의 단지다. (대각선에 집이 있는 경우는 연결된 것이 아니다.) 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 총 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 풀이 ✓ BFS 알고리즘 이용 https://dev-cloud.tistory.com/161 -> 유사한 문제이다. BFS와..

그래프 탐색(Graph Search) 그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것을 말한다. 단순히 그래프의 노드를 탐색하는 것으로 문제를 해결한다. 그래프 탐색에는 BFS/DFS가 있다. ✔ BFS(Breadth First Search) 정의 너비 우선 탐색이라는 뜻이고, 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. 아래의 그림을 보면서 쉽게 이해해보자. 위의 그림과 같이 6개의 노드와 5개의 간선(노드의 개수-1)이 있다. 노드 1번부터 시작해서 2번을 탐색하고 다음으로 4번 노드를 탐색하는 게 아닌 3번 먼저 탐색하는 것이다. 3번 옆에 아무것도 없으므로 다시 2번 노드로 돌아와서 2번 노드의 하위 노드 중 하나인 4번을 탐색한다. 4번을 끝냈으면 다..

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 설명 위의 그림과 같이 크기가 5x5인 그리드가 주어졌다고 하자. R은 빨간색, B는 파란색, G는 초록색을 나타낸 것이다. 같은 색끼리 인접해 있으면 그건 하나의 구역이다. 이 문제는 적록색약이 아닌 경우와 적록색약인 경우로 나눠서 구하는 문제이다. 적록색약인 경우는 빨간색과 초록색을 구분하지 못해서 같은 색으로 보일 것이다. 따라서 두 경우를 나눠서 구역을 구해보자. 아래는 구역을 색깔별로 구분해서 구역을 나타낸 것이다. 그리드 안에 검은색 선은 구역을..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 설명 위 사진은 미로를 나타낸 것이다. 1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸이다. Start칸에서 End칸까지 가야하는데, 지나갈 수 있는 최소의 칸을 구하면 된다. 주황색 형광으로 칠한 곳이 지나갈 수 있는 최소 칸 개수를 센 것이다. 칸 개수를 셀 때 시작칸과 마지막칸도 포함된다. 그럼 이제 문제를 풀어보자! 풀이 BFS 이용 1. 파이썬에서 BFS를 구현하기 위해서는 큐가 필요하다. 따라서 큐를 만든다. 파이썬 덱 모듈 내에 스택과 큐가 내장돼 있어서 사용하기 편한 덱 ..

build를 실패하면 저 빨간색 줄에 BUILD FAILED 라고 뜬다. 이전 포스팅에서 JDK 1.8.0_291 버전을 설치했는데 ./gradlew를 됐지만, ./gradlew build를 했더니 빌드가 실패했다고 떴다. 스프링 프로젝트를 생성 당시에 스프링 부트 3.0 미만 버전들은 가급적이면 자바 11을 설치해야 하는데 그걸 간과하고 있었다. 스프링 부트 3.0 이상은 Java 17 이상을 사용해야 한다. 나는 생성 당시 Spring Boot 2.7-을 선택했어서 자바 11을 사용했어야 했다. 만약 현재 버전을 확인하고 싶다면 윈도우 + R -> cmd -> java -version 이라고 쳐본다. JDK 11을 설치해주고 PATH, JAVA_HOME 경로를 재설정한다. JDK 11 Version ..

인텔리제이에서 빌드하고 실행하는 과정에서 오류가 났다. 콘솔에서 ./gradlew를 쳤더니 JAVA_HOME 에러가 난 것을 볼 수 있다. 오류를 잡기 위해 구글링을 열심히 해봤다. (이틀동안..) 첫 번째 시도. 1. 윈도우 검색창에 시스템 환경 변수 편집을 치고 들어간다. 그럼 시스템 속성 창이 바로 뜨는데, 저기서 빨간 색 줄의 환경 변수로 들어간다. 2. 환경 변수 창 -> 시스템 변수의 JAVA_HOME을 클릭하고 하단의 편집 버튼을 누른다. 3. 변수 값에서 맨 뒤에 있는 ;(세미콜론)을 제거한다. 그런데 나는 애초에 세미콜론이 없었다. 그래서 다른 방법을 찾았다. 두 번째 시도. 1. 환경 변수 창 -> 시스템 변수의 PATH를 클릭하고 하단의 편집 버튼을 누른다. 그럼 편집 창이 나오는데 ..

15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 설명 1 ~ N까지 자연수 중에서 M개를 고른 수열을 나열해서 출력하라는 문제이다. 또한 같은 수를 골라도 된다. 풀이 풀이는 간단하다. 1부터 N까지 수를 리스트에 다 담는다. 중복된 숫자도 들어가야 하니 중복순열을 사용한다. 중복순열은 순열과는 약간 다르게, 같은 숫자를 중복해서 담을 수 있다. ✎ itertools 라이브러리에서 product 함수를 import 한다. ☐ product(list, repeat = 뽑을 개수) Solution import s..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 설명 노드 개수를 7개라고 가정하자. 예제 입력에 둘째 줄부터 트리 상에서 연결된 두 정점이 주어진다고 했으니 그림으로 표현하면 다음과 같다. 파란색 숫자는 예제에 입력된 두 정점을 순서대로 연결된 것을 표현한 것이다. 풀이 이 문제는 DFS와 BFS 문제로 풀 수 있는데 필자는 DFS로 풀었다. for _ in range(N-1): a, b = map(int, input().split()) #노드와 연결된 걸 표현하기 위해 인접 리스트에 각각 저장 graph[a].append(b) graph[b].append(a) 위 코드를..

그리디 알고리즘 정의 탐욕 혹은 욕심쟁이 알고리즘이라고도 하며, 탐욕이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 따로 알고리즘의 사용 방법을 알고 있어야 한다거나, 외워야 하는 건 없다. 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 다시 말해 특정한 문제를 만났을 때 단순히 현 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다. 대표적인 문제로는 거스름돈이 있다. 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JO..

2587번: 대표값2 어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + www.acmicpc.net 문제 어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 평균 이외의 또 다른 대표값으로 중앙값이라는 것이 있다. 중앙값은 주어진 수를 크기 순서대로 늘어 놓았을 때 가장 중앙에 놓인 값이다. 다섯 개의 자연수가 주어질 때 이들의 평균과 중앙값을 구하는 프로그램을 작성하시오. 입력 첫째 줄부터 다섯 번째 줄까지 한 줄에 하나씩 자연수가..

9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x..

10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서..