정신차려 하프물범 정신차려 하프물범

최단 경로 최단 경로(Shortest Path) : 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘. 최단 경로 문제는 보통 그래프를 이용해 표현한다. 각 지점(국가, 학교) -> '노드', 지점간 연결된 도로 ->'간선'으로 표현된다. 코테에선 최단 경로를 출력하는 문제 보단, '최단 거리'를 요구하는 문제가 많이 출제된다. 학부 수준의 다익스트라(Dijkstra) 최단 경로 알고리즘 플로이드 워셜(Floyd-Warshall) 알고리즘 벨만포드 알고리즘 최단 거리 알고리즘엔 3가지가 있지만, 그 중에서도 코테에 자주 등장하는 것은 2가지이므로 이것만 우선적으로 설명한다. 최단 경로 알고리즘의 대표적 유형 3가지 한 지점에서 다른 특정 지점까지의 최단 경로 (다익스트라) 한 지점에서 모든 지점까..

문제 링크 https://www.acmicpc.net/problem/17276 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 풀이 코드 시간을 줄이기 위해 코드가 길어졌음. -> 제한 시간이 3초라 안길었어도 될 뻔했다.. 주대각선, 가운데열, 부대각선, 가운데행 이 4가지 줄만 바뀌므로, 원래 배열에서 이 4가지를 빼서 before 배열에 담아둔다. after 배열에 바뀌는 부분만 담는다. 각도에 따라 처음 배열의 주 대각선 원소들이 놓여지는 방향이 다르므로, 규칙에 따라 8가지로 나누었다. (시간 제한이 3초나 되기 때문에 누적해서 계속 돌려도 통과하는 것 ..

문제 링크 https://www.acmicpc.net/problem/22858 22858번: 원상 복구 (small) 수가 적혀있는 $P_1, P_2, ..., P_N$ $N$개의 카드가 있다. 1부터 N까지 수가 하나씩 존재하는 $D_1, D_2, ... , D_i , ... D_N$ 가 있다. 이때 $D_i$는 $P_{D_i}$ 값을 $i$ 번째로 가지고 오는 것을 의미한다. 이러한 www.acmicpc.net 풀이 코드 P 카드를 D의 규칙에 따라 이동하는 문제 원래 카드인 P를 다시 찾는 것이므로 결과 카드인 S를 D의 규칙 반대로 이동시키기. P[Di] 카드를 i번째로 옮기기 -> S[i] 카드를 Di로 옮기기 from copy import deepcopy n, k = map(int, input..

최적의 해를 구하기에 시간이 너무 많이 걸리거나 메모리 공간이 많이 필요한 문제가 있다. 이는 컴퓨터의 연산 속도, 메모리 공간에 대한 제약이 걸려 효율적인 알고리즘이 필요하다. 다만, 이런 문제들 중에서도 메모리 공간을 약간 더 사용하여, 속도를 비약적으로 높이는 방법이 있는데 이 중 대표적인 방법이 다이나믹 프로그래밍(Dynamic Programming)기법(동적 계획법)이다. 다이나믹 프로그래밍이란? 한번 해결된 부분 문제의 정답을 메모리에 기록하여, 한번 계산한 답은 다시 계산하지 않도록 하는 문제 해결법 이다. 다이나믹 프로그래밍은 *점화식을 그대로 코드로 옮겨 구현할 수 있다. (점화식: 인접한 항들 사이의 관계식) 대표적인 예시 문제가 피보나치 수열 문제이다. 피보나치 함수 코드 # 피보나치..

문제 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 풀이 코드 1 처음엔 출석 학생부터 누적합을 어떻게 활용해야 하나 고민했는데, 누적합에 대한 개념이 제대로 안섰나보다. 구간 M 누적합 attend = [0] * (N + 3) for i in range(3, N + 3): if not visited[i]: attend[i] = attend[i-1] + 1 else: attend[i] = attend[i-1] # 3. 답 프린트 answer = [] for s, e..

이진 탐색탐색의 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 기법.특징이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때만 사용데이터의 개수가 1000만개를 넘어가거나 탐색 범위의 크기가 2000만-1000억 이면 이진 탐색으로 접근하길 권한다.3가지 변수(시작점, 끝점, 중간점)가 사용된다.시작점, 끝점 : 탐색하고자 하는 범위를 나타내기 위해 사용중간점 : 중간점에 있는 데이터와 찾고자 하는 데이터가 일치하는지 비교기위해 사용.시간 복잡도: O(logN) -> 한 번 비교때마다 반 씩 줄어드니까!소스코드 (재귀, 반복문)1. 재귀# 이진 탐색 소스코드 구현 (재귀 함수)def binary_search(array, target, start, end): if start > end: ..

코딩테스트의 정렬 알고리즘이 사용되는 경우는 크게 3가지 유형으로 나눌 수 있다.1. 정렬 라이브러리로 풀 수 있는 문제2. 정렬 알고리즘의 원리에 대해 묻는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알아야 풀 수 있음.3. 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으론 풀 수 없고, 계수 정렬 등 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있는 문제.정렬 라이브러리또한 병합 정렬과 삽입 정렬이 합해진 방식이므로, 비교하기 위해 기본 정렬 방식부터 정리하려 한다.1. 정렬 알고리즘정렬 정의 및 특징정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열한 것을 말한다.정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(..