www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 내 사번과 똑같은 11727 번 문제를 우연히 발견해서 풀어보았다. 2xn 타일링 문제는 쉽게풀려고 한다면 엄청 쉬운 dp문제로, 점화식을 잘세우면 끝난다. 솔직히 2x3까지의 경우의수를 구하고 2x1, 2x2인 경우를 활용하여 2x3의 경우의 수를 다 시도해보면 쉽게 나올 수 있다. dp[1] = 1 dp[2] = 3 dp[3] = 5 이므로, dp[3] = dp[2] + dp[1] + 1 dp[3] = (dp[2] * dp[1]) + 2..

www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제를 딱 보았을땐 bfs? DP? 라고 헷갈린다. 하지만 BFS에서 조금 응요한 다익스트라인것을 알 수 있다. 왜냐하면 벽을 최소한으로 뚫은 위치를 계속찾아나가야하기 때문이다. 핵심부분은 다익스트라처럼 더욱 적은 부순 wall의 개수를 찾아 나가야 한다는 것이다. ''' 미로는 N*M 크기이며, 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않..

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어� www.acmicpc.net 다익스트라의 응용이다. N이 1000, M이 10000이므로 다익스트라를 사용해도 충분하다. 목적지 X에 갔다가 다시 되돌아와야하므로, 각 노드가 출발점인 경우에서 X까지의 최소거리를 저장하고 X가 목적지 일때 다른 곳 모두의 최소거리의 각각의 합의 최대값을 출력하면 된다. import sys import heapq input = sys.stdin.readline N, M, X ..

출처: 이것이 취업을 위한 코딩테스트다. 힙 자료구조는 우선순위 큐를 구현하기 위해서 사용하는 자료구조 중 하나다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제 한다는 점이 특징이다. 즉, 데이터를 우선순위에 따라 처리하고 싶을 때 사용하는 자료구조이다. (대부분의 프로그래밍 언어에는 우선순위 큐 라이브러리를 지원하기 때문에, 코딩 테스트 환경에서 직접 구현할 필요는 없다.) 파이썬에서는 PriorityQueue, heapq가 있는데, heapq가 동작이 더 빠르다. 우선순위 값을 표현할 때는 정수형 자료형의 변수가 사용된다.

클라우드 컴퓨팅의 개념에 대해 설명하고, - 클라우드 : Programmable Resouce Management => Programmable Resource Life Cycle Management => Programmable Service Management API를 만드는 사람은 클라우드 개발자 그 API를 쓰는 개발자는 클라우드 네이티브 개발자라는 인식이 있음. 근데 클라우드개발자는 다른 클라우드 API를 사용하는 사람임. => 그래서 꼬임. 클라우드와 클라우드 네이티브를 명확히 구별할 수는 없다. 하지만 "코드"를 사용한다는 공통점은 있다. Iaas : Used by API, 어떤것이는 사용자가 API를 통해서 뭔가를 만드는 것. Paas : Used by Framework (spring, .Ne..

출처: 이것이 취업을 위한 코딩테스트다. 다익스트라 최단 경로 알고리즘은 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘이다. 다익 스트라 최단 경로 알고리즘은 "음의 간선"이 없을 때 정상적으로 동작한다. (실제로 GPS에 쓰인다.) 다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. 알고리즘의 원리를 간략히 설명하면, 다음과 같다. 1. 출발노드를 정한다. 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한..

자동화는 크게 매크로기반 자동화 IT 프로세스 자동화 RPA로 구분된다. 매크로는 엑셀의 VBA를 떠올리면 되고, IT프로세스 자동화는 여러 시스템에 연계된 작업을 자동화하는 것이다. ex) 구글 docs api 자동화, 시스템 운영 및 장애 관련 대응 시 필요한 데이터 수집 및 문서 작성 RPA는 자동화 대상과 범위가 훨씬 넓다. 매크로가 사용자 수준에 쓰는 기능이라면, IT프로세스 자동화는 팀에서, RPA는 전사 측면에서 사용한다. 또한 매크로, IT프로세스 자동화는 활용 범위가 제한되어 있다. 왜냐하면 시스템,데이터 측면에서 업무 절차를 바라보기 때문에 응용 시나리오가 뻔하기 때문이다. 하지만 오토메이션애니웨어, uipath 등 RPA 선도 기업이 제시하는 자동화는 적용 시나리오가 무궁무진하다. 사..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net python으로 푸는데 in 을 사용해서 값이 존재하는지 판단하여 풀 수 있을 것이라 생각했으나 python의 in은 O(N) 연산이라고 한다. O(N) 연산이기 때문에 100000**2 이고 이진 탐색을 쓰면 정렬에 O(NlogN), 찾는데 O(logN)이므로 훨씬 빠르게 찾을 수 있다. 앞으로는 되도록 이진탐색을 이용하는 습관을 들이는것이 바람직한것 같다. '''..