알고리즘 문제풀이

알고리즘 문제를 풀며 더 좋은 풀이를 발견하거나필요한 알고리즘의 공부를 하거나등등 문제해결능력 향상에 이바지하기 위해글을 포스팅

유클리드 호제법유클리드 호제법 - 위키백과, 우리 모두의 백과사전

인수: 어떤 수나 식을 곱하기로 표현했을 때 곱해지는 수소수: 인수가 1과 자신이 전부인 수소인수: 한 수의 인수 중 소인 것의 집합어떤 수의 인수의 수는 제곱근의 2배또는 2배-1이다. 속도 개선에 도움이 된다.매개변수 n이 3,4 등 너무 작을 경우 뒤에 나오는 i

문제n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.1, 2, 32, 1, 3

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.n행 n열 크기의 비어있는 2차원 배열을 만듭니다.i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸

C++의 기본적인 컨테이너의 사용법과 for문 if문 만으로 프로그래머스 2단계까지 풀며주먹구구로 푸는 것에 한계에 부딛혔다. 코딩테스트를 풀기위해 기본적인 알고리즘과 주변개념들에 대해 알아보자.알고리즘: 문제를 해결하기 위한 절차나 방법컴퓨터 프로그램은 정교한 알고리

문제 설명OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄

자료구조의 스택, 큐, 환형 큐, 힙, 트리, 그래프에 대해 알아보고 C++에서 직접 사용해보자.후입 선출(Last In First Out-FIFO)메모리가 새로 들어오는 데이터의 위치가 메모리 말단(일명 '탑 포인터')선입 선출 FIFO(First In First O

최솟값 찾아 정렬최종 정렬 상태까지 회전첫번째 인덱스부터 다음 인덱스와 비교하여 이동이동후 전 인덱스와 후 인덱스를 비교하여 정렬되어야 하는 상태면 또 이동이 이동이 마무리되면 1회전최종 정렬 시까지 반복초기상태의 첫번째 인덱스를 왼쪽이 오른쪽보다 크다면 교환 쭉 1회

탐색알고리즘에 대해 알아보자완전탐색재귀함수나 스택으로 구현1) 탐색 시작 노드를 스택에 삽입하고 방문처리2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리(방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸

가장 짧은 경로를 찾는 알고리즘, '길 찾기'문제로 불린다.그리디 알고리즘, DP 프로그래밍이 그대로 적용된다.1) 다익스트라 최단 경로 알고리즘가중치 그래프에서, 시작정점으로부터 다른 모드 정점까지의 최단 경로를 찾는 알고리즘우선순위 큐를 사용어렵게 생각하지 말자아래

지금 까지 정리해온 내용들이 빛을 발할 때이다. 알고리즘 패러다임이란 알고리즘 접근 패턴을 뜻한다. 한 문제에 여러가지 방식의 풀이가 있듯이 마찬가지로 한 문제에 두 개 이상의 알고리즘 패러다임이 존재할 수도 있는 것이다. 무식한 힘, 하나부터 열까지 전부다 계산해서

문제△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어

문자열 리스트 str_list에는 "u", "d", "l", "r" 네 개의 문자열이 여러 개 저장되어 있습니다. str_list에서 "l"과 "r" 중 먼저 나오는 문자열이 "l"이라면 해당 문자열을 기준으로 왼쪽에 있는 문자열들을 순서대로 담은 리스트를, 먼저 나오

문자열 my_string과 이차원 정수 배열 queries가 매개변수로 주어집니다. queries의 원소는 s, e 형태로, my_string의 인덱스 s부터 인덱스 e까지를 뒤집으라는 의미입니다. my_string에 queries의 명령을 순서대로 처리한 후의 문자열

소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다.기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니

l부터 r까지 순회하며 i에 5나 0이 아닌 다른 수가 있는지 확인l 부터 r까지 순회각 숫자를 문자열로 변환 후, 그 문자열을 집합으로 반환고유한 요소의 집합을 나타내는데 사용{} 또는 set() 함수를 통해 생성순서 없음(인덱싱, 슬라이싱 불가능)가변해시 가능한 요

board를 순회하며 만약 1이라면 안전하지 않으니 주변을 2로 바꾸고 끝나면 0의 숫자를 세는 아이디어directions, 상,하,좌,우,대각선 확인is_valid, 확인 중 board의 인덱스 범위를 벗어나는지 아닌지 확인하는 함수enumerate는 iterable

이것이 코딩 테스트다 with python단순하지만 강력한 문제 해결 방법현재 상황에서 지금 당장 좋은것만 고르는 방법그리디 알고리즘 유형의 문제는 창의력이 필요함'가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시됨당신은 음식점의 계산을 도와

이것이 코딩테스트다 with 파이썬작성속도가 빨라야 한다.문법을 제대로 알아야한다.라이브러리를 많이 알고 있으면 유리하다.파이썬은 변수의 표현 범위를 고려하지 않아도 된다.(자동으로 크기에 따라 메모리를 차지한다.)리스트를 여러 개 선언하고 그 중에서 크기가 1000만

수학의 점화식(재귀식을) 그대로 소스코드로 옮겼기 때문에 간결하다.점화식의 개념은 다이나픽 프로그래밍에서 중요하게 사용된다.수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식$a\_{n+1} = f(a_n)$함수 f를 수열$a_n$의 점화식이라고 한다.특

0. 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지