문제 www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 완전한 구현 문제다. 순열을 통해 모든 경우의 수를 구한 후, 연산으로 이루어진 순열을 큐에 담아 rotate 함수에 전달한다. 회전을 구현하는 과정은 조금 지저분하게 구현했다. 이때 좌측 상단의 좌표를 (ux, uy)로, 우측 하단의 좌표를 (lx, ly)로 두고 좌에서 우로, 상에서 하로 값을 덮어 씌웠다. 이를 위해 모서리의 값을 t1, t2, t3 변수에 담아두었..
문제 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 백준 1753번 문제인 최단경로 문제와 유사한 문제다. 마찬가지로 다익스트라 알고리즘을 적용하여 해결할 수 있다. 다만, 이 문제 같은 경우 두 정점(v1, v2)을 반드시 거쳐야 한다는 제약조건을 고려해야 한다. 1번 노드부터 출발하여 n번 노드까지 이동하는 경로는 다음과 같이 두 가지로 나뉜다. 1) v1번 노드를 먼저 방문한 후, v2번 노드를 방문하..
스택, 큐, 덱이란? 데이터 값을 저장하는 기본적인 구조로 일차원의 선형(linear) 자료구조이다. (배열/리스트와 유사하게) 값을 저장(insert 또는 set)하는 연산과 저장된 값을 꺼내는(remove 또는 get) 연산이 제공된다. 그러나 매우 제한적인 규칙(LIFO, FIFO)등을 따른다. 스택(Stack): LIFO - 후입선출 스택은 가장 최근에 저장된 값 다음에 저장되며, 가장 최근에 저장된 값이 먼저 나간다. - LIFO(Last In First Out) 원칙 파이썬은 스택 자료형을 별도로 제공하지는 않지만, 리스트가 사실상 스택의 모든 연산을 지원한다. class Stack: def __init__(self): self.items = []# 데이터 저장을 위한 리스트 준비 def pu..
HTTP 용어 1) URL 및 URI URI (Uniform Resource Locator)은 웹에서 리소스 (HTML 문서 및 해당 자산)를 고유하게 식별하는 데 사용된다. 한편, URL (Uniform Resource Locator)는 자원의 위치를 나타낸다. URI가 URL보다 더 포괄적인 개념이다. URL의 구조: protocol : // hostname : port / path-and-file-name a) 프로토콜(Protocol): 클라이언트와 서버에서 사용하는 응용프로그램 레벨의 프로토콜 (예 : HTTP, FTP 및 텔넷). b) 호스트 이름(Hostname): 서버의 DNS 도메인 이름 (예 : www.xxxx.com) 또는 IP 주소 (예 : 192.158.15.20). c) 포트(P..
문제 www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 역시 삼성 SW A형 문제답게 브루트 포스문제였다. 거기에 그래프 탐색이 더해졌다. 이 문제 또한 2가지의 부분 문제로 나눠볼 수 있다. 1) 선거구를 어떻게 나눌 것인가 2) 어떻게 그래프 탐색을 할 것인가 1) 선거구를 어떻게 나눌 것인가 조합을 사용하여 선거구를 나눈다. 이때 n의 절반(1~n//2)만큼만 조합을 구하면 된다. 이는 mCn = n-mCn이 성립하는 조합의 성질을 잘 생각해보면 알 수 있다. 즉, 한 ..
