출처: [백준] 15903번 카드 합체 놀이

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입력 1

1
2

3 1
3 2 6

예제 출력 1

1

16

예제 입력 2

1
2

4 2
4 2 3 1

예제 출력 2

1

19

출처

• University > 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회 > UCPC 2018 예선 B번
  • 문제를 만든 사람: haden

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 우선순위 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
card_list = list(map(int, input().split()))

heapq.heapify(card_list)  # card_list를 heap으로 변환

for _ in range(M):
    x, y = heapq.heappop(card_list), heapq.heappop(card_list)
    for _ in range(2):
        heapq.heappush(card_list, x + y)


print(sum(card_list))

Survey (EC2, Auto Scaling, S3, RDS)

What is Amazon EC2?

Abbreviation for Amazon Elastic Compute Cloud, it provides scalable computing capacity in the Amazon Web Services (AWS) cloud.

With Amazon EC2, you can,

• Build as many virtual servers as you want,
• Manage security, network configuration, storage
• •Reduces the need to predict server traffic more

What is Amazon Auto Scaling?

With AWS Auto Scaling, you can configure automatic scaling of the AWS resources in your application in minutes.

Amazon Auto Scaling monitors your application,

• Set up scaling quickly,
• Make smart scaling decisions,
• Maintain performance automatically,
• Reliable,
• Pay only for what you need. (the lowest possible cost) more

What is Amazon S3?

Abbreviation for Amazon Simple Storage Service, it provides storage through a web service interface.

With Amazon S3, you can easily

• Organize your data,
• Fine-grained access controls according to your specific business, organization, and compliance requirements.
• Designed to provide 99.999999999% durability more

What is Amazon RDS?

Abbreviation for Amazon Relational Database Service, Amazon RDS is a web service that operates in the cloud.

With it, you can easily

• Set up, Operate, and Scale your relational database in the cloud.
• Automate Hardware provisioning, Database setup, Patching and Backups more

Survey (Detail Specification of EC2)

Instance Types:

It is divided into “General purpose(T2, T3…)”, “Computing optimization(C4, C5…)”, “Memory optimization(z1d, R5…)”, “Accelerated computing(P4…)”, and “Storage optimization(H1, I3…)”. more

Pricing Plans:

• On-Demand Instance - You are charged for what you use. However, since the unit of billing is 1 minute, even if you use 1 second, you will be charged 1 minute.
• Spot Instance – You can use EC2 resources that are not currently in use by receiving a cheap bid at auction. They are offered at a discount of up to 90% compared to the On-Demand rate.
• Reserved Instance - When you reserve the usage period (1 or 3 years) and usage (No/Partial/All Upfront) and pay the initial prepayment, you receive a discount on the hourly usage fee. more

1. 파이썬, 자바 꺾고 2위 등극 …5월 TIOBE 지수 공개

파이썬, 자바 꺾고 2위 등극 …5월 TIOBE 지수 공개

매달 프로그래밍 언어의 인기 지표를 발표하는 TIOBE에서 파이썬(Python)이 자바(JAVA)를 누르고 2위에 올랐다. (관련기사) 4월의 1위 프로그래밍 언어 자리는 지난달과 동일하게 C가 차지했다.
올해의 언어상을 수상했던 Objective-C가 지난달 20위 밖으로 퇴장한 이후 20위 내 프로그래밍 언어들의 변동은 크게 없지만, 20위 밖에서 러스트(Rust)ㆍ다트(Dart)ㆍ줄리아(Julia)가 상승세를 보인다.

2. 2위 배달앱 ‘요기요’ 인수전…신세계·야놀자 참여

2위 배달앱 ‘요기요’ 인수전…신세계·야놀자 참여

4일 투자은행(IB) 업계에 따르면 독일 딜리버리히어로(DH)와 매각 주관사 모건스탠리가 이날 진행한 요기요 운영사 딜리버리히어로코리아 예비 입찰에 신세계, 야놀자, MBK파트너스 등 국내 유통 대기업과 유니콘(기업가치 1조원 이상의 비상장사), 사모투자펀드(PEF)가 참여한 것으로 알려졌다.
야놀자는 요기요 인수로 여행·숙박 사업과 배달 서비스를 연계하는 방안을 모색하고 있으며, 야놀자가 올해 상장을 준비하는 만큼 인수 성공시 기업가치가 달라질 수 있다는 분석도 나온다.

3. 카카오가 꽉잡은 3.5조원 선물하기, 네이버도 눈독

카카오가 꽉잡은 3.5조원 선물하기, 네이버도 눈독

비대면(언택트) 흐름 속 가파른 성장세를 보이는 ‘선물하기’ 시장에서 네이버가 카카오에 도전장을 내밀었고, 카카오톡을 기반으로 한 관계형 커머스에 강점을 보이는 카카오를 상대로 네이버는 45만 스마트스토어를 앞세워 공략에 나섰다.

4일 이커머스 업계에 따르면 선물하기 시장 규모는 지난해 기준 약 3조5000억원 수준으로 추산되며, 이 가운데 3조원 가량이 카톡 선물하기 거래액으로 지난해 12월 기준 이용자만 2173만명에 이른다.

4. [단독] LG전자 모바일인력 600명, LG엔솔로 간다…왜

[단독] LG전자 모바일인력 600명, LG엔솔로 간다…왜

4일 재계와 LG전자 등에 따르면 LG전자는 지난달 휴대전화 사업 종료를 선언한 후 3400여 명의 모바일(MC)사업본부 인력의 재배치를 구체화하고 있다.
회사 측은 직원 개개인의 의사를 최대한 반영하고 있으며, 사업 부서를 해체거나 매각할 때 국내 어느 대기업에서도 전례가 없는 파격적인 조치다.

5. [OTT온에어] 넷플릭스 1Q 가입자 성장둔화…5천500억 韓 투자 ‘우려’

[OTT온에어] 넷플릭스 1Q 가입자 성장둔화…5천500억 韓 투자 ‘우려’

넷플릭스의 올 1분기 매출은 71억6천300만달러(약 8조10억원), 영업이익은 19억6천만달러(약 2조1천900억원) 수준으로 전년동기대비 각각 늘었고, 영업이익률도 27.4%에 육박하며 실적은 견고했다.
사실상 사상 최고치임에도 불구하고 600만명 이상 증가할 것이라 예측했던 넷플릭스 글로벌 가입자 순증이 398만명에 그쳤기 때문에 각국 애널리스트의 시선은 보수적이다.

출처: [코딩테스트 연습] 디스크 컨트롤러

문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

1

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력

입출력 예 1

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

풀이

• scoville리스트를 heaq구조로 바꿔주고, 조건에 맞게 두번의 heappop..
• 위 계산을 다시 scoville에 넣어주고 answer카운트 증가–> K 이상될때까지
  K이상이 될 수 없으면 return -1

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import heapq


def solution(scoville, K):
    answer = 0
    # heap = []
    # for num in scoville:
    #     heapq.heappush(heap, num)
    heapq.heapify(scoville)

    while scoville[0] < K:
        mix = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
        heapq.heappush(scoville, mix)
        answer += 1
        if len(scoville) == 1 and scoville[0] < K:
            return -1
    return answer


# print(solution([1, 2, 3, 9, 10, 12], 7))  # 2

출처: [코딩테스트 연습] 디스크 컨트롤러

문제

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

1
2
3

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

1
2
3

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

1
2
3

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력

입출력 예 1

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

풀이

• 우선순위 큐를 이용해서…
• 현재 시점에서 처리할 수 있는 작업들을 힙에 넣고, 하나를 뽑아 현재 시점과 총 대기시간을 구해주는 것을 모든 작업을 처리할 때까지 반복한다.
  힙에 push를 할 때는 작업의 소요 시간 기준으로 최소힙이 만들어져야 하기 때문에 jobs의 요소를 그대로 넣지 않고 [작업의 소요 시간, 작업이 요청되는 시점]으로 요소의 앞 뒤를 바꿔서 넣어준다.현재 시점에서 처리할 수 있는 작업인지를 판별하는 조건은 작업의 요청 시간이 바로 이전에 완료한 작업의 시작 시간(start)보다 크고 현재 시점(now)보다 작거나 같아야 한다.
  만약 현재 처리할 수 있는 작업이 없다면, 남아 있는 작업들의 요청 시간이 아직 오지 않은 것이기 때문에 현재 시점(now)을 하나 올려준다. 출처

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import heapq


def solution(jobs):
    answer, now, i = 0, 0, 0
    start = -1
    heap = []

    while i < len(jobs):
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])
        if len(heap) > 0:
            current = heapq.heappop(heap)
            start = now
            now += current[0]
            answer += (now - current[1])
            i += 1
        else:
            now += 1
    return int(answer / len(jobs))


# print(solution([[0, 3], [1, 9], [2, 6]]))  # 9

1. 애플·에픽, 세기의 ‘앱스토어 전쟁’ 마침내 시작

애플·에픽, 세기의 ‘앱스토어 전쟁’ 마침내 시작

두 회사 공방의 핵심 쟁점은 앱스토어를 운영하고 있는 애플의 독점 행위다. 에픽은 애플이 앱스토어 이외 다른 앱 장터를 허용하지 않으면서 사실상 경쟁을 막고 있다고 주장하고 있으며 앱 배포 못지 않게 인앱결제 문제도 쟁점으로 떠오르고 있다.

2. 13일부터 킥보드 헬멧 의무화…”공용이냐, 개인용이냐” 업계 ‘딜레마’

13일부터 킥보드 헬멧 의무화…”공용이냐, 개인용이냐” 업계 ‘딜레마’

다음달 13일부터 헬멧을 착용하지 않고 전동킥보드를 타면 이용자에게 범칙금 2만원이 부과된다.
업계는 헬멧 착용을 유도하되, 킥보드 이용률은 유지하기 위한 방법을 고심하고 있으며, 각사의 대처 능력에 따라 업계의 시장 점유율도 차이가 벌어질 전망이다.

3. TV도 워크맨도 다 버리더니… ‘콘텐츠’로 창사 이래 최대실적, 소니의 부활

TV도 워크맨도 다 버리더니… ‘콘텐츠’로 창사 이래 최대실적, 소니의 부활

워크맨과 TV로 1990년대까지 세계를 호령했던 소니는 2000년대부터 인터넷 시대에 대응하지 못하면서 침몰의 길로 들어섰다.

하지만, 게임과 음악, 영화 등을 포함한 엔터테인먼트 사업의 견인으로 2일 업계에 따르면, 소니그룹은 최근 발표한 2020회계연도(작년 4월~올해 3월) 순이익(연결기준)이 전년의 2배 수준인 1조1,717억 엔(약 11조9,500억 원)에 달했고, 매출액도 9% 늘어난 8조9,993억 엔(약 91조8,000억 원)으로, 순이익과 매출액 모두 사상 최대치다.

4. VR 회사 또 샀다…페이스북, 다운푸어 인수

VR 회사 또 샀다…페이스북, 다운푸어 인수

지난달 30일(현지시간) 페이스북이 VR 슈팅 게임 온워드를 개발한 ‘다운푸어 인터렉티브’를 인수했다.

페이스북은 지난 2019년 말부터 VR 개발사를 활발히 인수해왔으며, “VR을 육성하기 위해 다양한 방법을 모색하고 있다”며 “향후 몇 년간 VR 게임을 위한 놀랍고 혁신적인 계획도 가지고 있다”고 밝혔다.

5. 구글 이어 야후도 ‘이것’에 손 뗐다… ‘네이버 지식인’만 살아남은 비결

구글 이어 야후도 ‘이것’에 손 뗐다… ‘네이버 지식인’만 살아남은 비결

이달 4일 미국 야후는 2005년부터 운영해온 ‘야후! 앤서스(Yahoo! Answers) 서비스’를 완전히 종료한다.

네이버에 따르면 지식공유 서비스인 ‘네이버 지식인’의 글 생산량은 역대 최대치를 돌파했으며, 지식iN 서비스에서 한 단계 진화한 ‘네이버 엑스퍼트’는 ‘SME 대상의 마이크로 컨설팅’ 플랫폼으로 자리 잡으며 빠르게 성장하고 있다.

• 야후 앤서스는 사용자가 질문하면 다른 사용자가 답변을 달아주고 검색창에 질문을 입력하면 답이 될 만한 정보를 찾아주는 서비스로, 국내에서는 네이버 지식인과 비슷하다.
• 네이버 엑스퍼트는 결제, 라이브기술, 채팅 등 네이버가 개발한 기술들을 고도화한 서비스로, 전문가와 사용자가 일대일(1:1) 비공개로 만날 수 있다는 점이 특징이다.

6. 줌이 장악한 화상회의 플랫폼… 국내 업체들 “좀, 들어갈게”

줌이 장악한 화상회의 플랫폼… 국내 업체들 “좀, 들어갈게”

후발주자로 분류되던 국내 IT업체들도 다양한 기능을 탑재한 협업 툴을 내세우며 줌에 도전장을 던지고 있다. 한 업계 관계자는 2일 “줌은 화상회의만 가능한 플랫폼이다보니 용도가 한정적”이라며 “업무 툴을 여러 개 두기보단 하나로 통합해서 쓰는 게 효율적이라고 보기 때문에 종합 협업 툴을 지향하는 국내 업체들도 발전 가능성이 충분하다”고 설명했다.

1. 카카오 이어 네이버도 ‘대기업집단’ 반열…재계 순위 27위 ‘껑충’

카카오 이어 네이버도 ‘대기업집단’ 반열…재계 순위 27위 ‘껑충’

네이버는 사업이익 증가, 외부 신규투자 유치로 자산총액이 9조5000억원에서 13조6000억원으로 급증하면서 재계 순위가 41위에서 27위로 약진했고, 넷마블(36위), 넥슨(34위)도 자산총액이 각각 10조7000억원, 12조원으로 늘어 상호출자제한 기업집단으로 지정됐으며, 이들 기업은 상호출자가 금지된다.

공정위는 “코로나19 극복 과정에서 시중 유동성이 크게 증가해 자산가치가 급등하면서 지정집단이 대폭 확대됐다”며 “(특히) 비대면 시장이 급성장함에 따라 IT업종을 주력으로 하는 기업집단들의 성장세가 뚜렷했다”고 설명했다.

• 상호출자: 회사간에 주식을 서로 투자하고 상대회사의 주식을 상호보유하는 것

2. [단독] “쿠팡맨 말고 당근맨?”…당근마켓 ‘3000원’ 배송 서비스 나왔다 [IT선빵!]

[단독] “쿠팡맨 말고 당근맨?”…당근마켓 ‘3000원’ 배송 서비스 나왔다 [IT선빵!]

중고거래 애플리케이션 당근마켓이 거래 물품을 배송해주는 ‘당근배송’ 서비스를 내놨으며, 일부 지역의 서비스 테스트를 시작으로, 본격적인 배송 서비스가 도입될 것으로 전망된다.

당근마켓 측은 “다만, 직거래가 아니어서 실제로 물건을 확인하지 않고 진행되다가 생기는 거래 분쟁, 물품 진위 여부 등은 배송원이 확인하기 어려워 당근마켓에서 관여하지 않는다”고 설명했고 “테스트 결과와 이용자들의 반응에 따라 타지역 확대 여부가 결정될 예정”이라며 “테스트 서비스로, 아직 공식 서비스 오픈 일정은 미정”이라고 말했다.

3. “배달 거절하면 패널티” vs.“싼 배달 거절은 권리” 배달앱과 라이더 ‘충돌’ [IT선빵!]

“배달 거절하면 패널티” vs.“싼 배달 거절은 권리” 배달앱과 라이더 ‘충돌’ [IT선빵!]

“배달 콜 거절하지 마세요. 패널티 부과합니다.”(배달앱 측 입장)

“최저 단가나 장거리 배달을 거절하는 건 권리 아닌가요? 부당합니다.”(배달 라이더 측 입장)

쿠팡이츠에 이어 배달의민족도 라이더들의 배달 수락률과 배달 완료율을 표시하며, 라이더들은 배달앱이 이를 근거로 패널티를 부과할 가능성이 커졌다며 우려하고 있다.

앞서 쿠팡이츠는 ‘배달 호출(콜) 거절과 취소’를 이유로 일부 라이더에게 하루 동안 배달을 제한한다고 통보했지만, 일부 라이더들은 업무 제한 기준이 고객센터에 문의해도 “내부 규정상 기준을 공개할 수 없다”는 입장만 반복하거나, 상담원마다 언급하는 기준이 다르기 때문에 명확하지 않다고 주장하고 있다.

4. “격주로 4일 근무”… 게임업계 이번엔 복지전쟁

“격주로 4일 근무”… 게임업계 이번엔 복지전쟁

예전 게임 업계는 크런치 모드(게임 개발 막바지에 밤을 새우며 작업하는 상황)로 악명 높았지만, 요즘 업계에선 “게임 업체들이 워라밸 선진 기업들로 속속 바뀌고 있다”는 말이 나온다.

임금 인상에 복지 경쟁까지 불붙으면서 중장기적으로 기업의 인건비 부담이 크게 늘어날 것이라는 우려도 나오며, 게임 업계에서는 “임금을 대폭 인상한 데 이어 복지 지출까지 커지면서 게임 업체들의 인건비 지출 규모는 지난해 대비 20~30% 증가할 것”이라는 전망이 나온다.

5. LG폰은 없애고 특허만 남겼다…스마트가전·전장에 IP 이식

LG폰은 없애고 특허만 남겼다…스마트가전·전장에 IP 이식

LG전자가 휴대폰 사업에서 26년간 쌓은 특허와 기술력을 스마트가전, 전장 등 미래사업으로 이관하며, 휴대폰 핵심 지식재산권(IP) 자산은 차량용 커넥티비티 등을 개발하는 전장솔루션(VS)사업본부에서 적극적으로 활용할 방침이다.

LG전자는 휴대폰 사업 종료 후에도 미래준비를 위한 핵심 모바일 기술의 연구개발은 지속할 방침이고, 특히 6세대 이동통신(6G)·카메라·소프트웨어 등 핵심 모바일 기술은 차세대 TV·가전·전장부품·로봇 등에 필요한 역량으로 꼽힌다. 회사는 이 분야에서 최고기술책임자(CTO)부문 중심으로 연구개발을 지속할 예정이다.

6. 코로나 내년초엔 끝날까…’CES 2022’ 라스베이거스서 현장 진행

코로나 내년초엔 끝날까…’CES 2022’ 라스베이거스서 현장 진행

올해 비대면 진행된 세계 최대 전자·정보기술(IT) 전시회 CES가 내년에는 예년처럼 라스베이거스에서 현장 행사로 열린다.

미국 야후는 “내년 1월 백신 접종 상황이 얼마나 진척될 지도 모른다”며 “올해는 2020년 당시 방문객수 17만 명보다는 적겠지만, 상당수가 외국인 참가자라는 걸 고려하면 상황이 어떻게 될지 모르겠다”고 우려했다.

출처: [백준] 11725번 트리의 부모 찾기

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1

1
2
3
4
5
6
7

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

1
2
3
4
5
6

4
6
1
3
1
4

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
12

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2

1
2
3
4
5
6
7
8
9
10
11

1
1
2
3
3
4
4
5
5
6
6

출처

• 문제를 만든 사람: baekjoon
• 잘못된 조건을 찾은 사람: jh05013

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())

trees = {}
for i in range(N):
    trees[i + 1] = set()

for i in range(N - 1):
    a, b = map(int, input().split())
    trees[a].add(b)
    trees[b].add(a)

parents = [False] * (N + 1)


def dfs(graph, v, visited):
    for i in graph[v]:
        if not visited[i]:
            visited[i] = v
            dfs(graph, i, visited)


dfs(trees, 1, parents)
for i in range(2, N + 1):
    print(parents[i])

1. 큐냅 NAS 노린 랜섬웨어 ‘Q로커’ 사기 주의보

큐냅 NAS 노린 랜섬웨어 ‘Q로커’ 사기 주의보

데이터를 볼모로 몸값을 요구하는 악성코드, 랜섬웨어가 PC가 아닌 NAS(네트워크 저장장치)로 눈을 돌렸고, 특히 이달 중순 등장한 랜섬웨어인 Q로커(Qlocker)는 시놀로지, 에이수스토어(Asustor) 등과 함께 대만 내 주요 NAS 업체로 꼽히는 큐냅(QNAP) 제품을 노린다. 모든 파일의 암호화가 끝났다 해도 NAS 내부에 존재하는 로그 파일에 암호화에 쓰인 비밀번호가 남아 있기 때문에 NAS의 전원을 끄거나 재부팅해서는 안된다.

2. 네이버 ‘웨일’ 크롬 콧대 꺾을까… “3년 내 시장 석권할 것” 기염

네이버 ‘웨일’ 크롬 콧대 꺾을까… “3년 내 시장 석권할 것” 기염

네이버가 자사의 웹 브라우저 ‘웨일’을 통해 3년 안에 구글 크롬을 제치고 국내 웹브라우저 시장을 석권하겠다는 야심찬 포부를 드러냈다. 시장조사업체 스탯카운터에 따르면 지난해 12월 기준 웨일의 국내 브라우저 시장 점유율은 8.29%로 1위 크롬(52.77%)과 여전히 큰 격차를 보이고 있지만 지난해 1월 웨일이 0.12%의 점유율을 기록한 것과 비교하면 큰 성장을 이뤄냈다.

3. “애플, 차세대 ‘M2’칩 생산 들어가…올해 맥북 탑재될 수도”

“애플, 차세대 ‘M2’칩 생산 들어가…올해 맥북 탑재될 수도”

애플이 자체 설계한 반도체 칩 ‘M1’을 잇는 ‘M2(또는 M1X)’가 생산에 들어간 것으로 알려졌으며, M2는 세계 반도체 파운드리(위탁생산) 1위 업체인 대만 TSMC가 맡는 것으로 전해졌다. 5나노미터플러스(N5+) 공정이 도입될 전망이고, 전작인 M1과 같이 ARM 기반 시스템온칩(SOC)으로 설계될 것으로 보인다. 앞서 애플은 인텔과 작별하고 자체 설계한 반도체 칩 M1을 공개한 바 있다.

4. ‘게임사와 다른’ 개발자 잡아라…삼성SDS·LG CNS·SK㈜C&C 연봉 인상

‘게임사와 다른’ 개발자 잡아라…삼성SDS·LG CNS·SK㈜C&C 연봉 인상

삼성SDS·LG CNS·SK㈜C&C 등 주요 대기업집단 IT서비스 3사가 올해 직원들의 연봉을 예년보다 큰 폭으로 인상한 것은 개발자 처우를 개선하자는 취지다. 하지만, IT서비스 기업과 게임사 개발자들의 업무 내용 및 개발 범위가 다르기 때문에 최근 전직원들의 연봉을 대폭 인상하거나 대규모의 자사주를 지급한 게임사나 인터넷 기업으로의 인력 유출에 대한 우려와는 거리가 멀다.

5. 20년 쌓아올린 알리바바 제국, AI 무장 新生기업에 추월당했다

20년 쌓아올린 알리바바 제국, AI 무장 新生기업에 추월당했다

중국 이커머스 업체 핀둬둬는 중국 1위 이커머스 업체 알리바바가 다양한 채널로 소비자들에게 접근하는 것과 달리 인터넷 쇼핑몰이지만 PC 홈페이지 없이 모바일 앱만 운영한다. 핀둬둬는 AI를 소비자 개개인에게 최적화하여 백화점식 배열에 익숙한 인터넷 쇼핑 이용자들에 핀둬둬의 맞춤형 서비스는 엄청난 파장을 몰고 왔으며, 창업 6년 만에 알리바바의 이용자 수를 넘어섰다.

6. AI發 ‘마의 벽’에 부딪힌 자율주행차

AI發 ‘마의 벽’에 부딪힌 자율주행차

. 세계 최고 기술을 갖춘 글로벌 기업 책임자가 실적 부진을 이유로 사퇴하는가 하면 국내 유망 스타트업이 사실상 해체 수순을 밟고 있다는 소문까지 나돌고 있으며, 업계에선 “기술 진화 속도보다 비즈니스가 과속할 때 벌어지는 불일치 현상”이란 지적이 나온다.

27일 정보기술(IT)업계에 따르면 국내 자율주행 전문 기업 포티투닷의 사업회사 퍼플엠의 서영우 대표와 최고운영책임자(COO) 등 초기 멤버 상당수가 최근 회사를 이탈했고, 세계 자율주행차 기술의 ‘쌍두마차’로 꼽히는 테슬라와 구글 등 글로벌 선두주자들이 나란히 악재를 겪고 있으며, 글로벌 업체들의 ‘운전자 없는’ 자율주행차 상용화 시기는 애초 기대했던 2021년이나 2022년이 아니라 2025년 이후로 대부분 미뤄진 것으로 알려졌다.

출처: [백준] 1987번 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력 1

1
2
3

2 4
CAAB
ADCB

예제 출력 1

1

3

기타 입력

1
2
3
4

3 4
ABBC
ECED
FGDH

기타 출력

1

8

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2002 > Regional Competition - Juniors 3번

• 데이터를 추가한 사람: august14, doju, jh05013

링크

• PKU Judge Online

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 백트래킹

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import sys

input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(x, y, count):
    global ans
    ans = max(ans, count)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0 <= ny < C and passed[board[nx][ny]] == 0:
            passed[board[nx][ny]] = 1
            dfs(nx, ny, count + 1)
            passed[board[nx][ny]] = 0


R, C = map(int, input().split())
board = [list(map(lambda x: ord(x) - 65, input().rstrip())) for _ in range(R)]
passed = [0] * 26

ans = 1
passed[board[0][0]] = 1
dfs(0, 0, ans)

print(ans)

소스코드_BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys

input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs():
    global count
    queue = set()
    queue.add((0, 0, board[0][0]))

    while queue:
        x, y, ans = queue.pop()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in ans:
                queue.add((nx, ny, ans + board[nx][ny]))
                count = max(count, len(ans) + 1)


R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
count = 1
bfs()
print(count)

소스코드_실패(메모리 초과)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(x, y, cnt):
    global count
    count = max(cnt, count)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in passed:
            passed.append(board[nx][ny])
            dfs(nx, ny, cnt + 1)
            passed.append(board[nx][ny])


R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
passed = []
count = 1
dfs(0, 0, count)
print(count)