알고리즘

문제 : https://www.acmicpc.net/problem/5639 문제 해결 아이디어 이진 검색 트리의 경우 왼쪽 서브 트리의 노드들은 루트의 값보다 키가 작고, 오른쪽 서브 트리의 노드들은 루트의 값보다 키가 크다 문제에서 입력은 전위 순회*로

노드의 개수 n과 (n - 1)개의 트리 상에 연결된 두 정점이 주어진다.트리의 루트를 1이라고 했을 때, 2번 노드부터 각 노드의 부모 노드 번호를 출력하는 문제이다.탐색 시작 노드를 큐에 넣고 방문처리한다.큐에서 노드를 꺼낸다.해당 노드의 인접 노드 중에서 방문하지

정점의 개수 v간선의 개수 e정점 a, 정점 b, 가중치 c가 주어질 때 주어진 그래프의 최소 스패닝 트리의 가중치를 구하시오.최소 신장 트리(MST, Minimum Spanning Tree)에 관한 문제이다.MST 문제를 푸는 방법에는 간선의 길이를 기준으로 최솟값부

문제 출처 : https://www.acmicpc.net/problem/6549 이 문제는 푸는 방법에는 여러방법이 있을 수 있지만 알아본 결과 대표적으로 3가지 방법이 있다. 풀이방법 1 : 각 직사각형의 인덱스를 이용한 분할 정복 인덱스를 기준으로 인덱스 왼쪽

"""문제 그래프의 정점의 집합을 둘로 분할각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있다.이런 그래프를 이분 그래프그래프가 입력으로 주어짐 이 그래프가 이분 그래프인가 아닌가?""""""입력k : 테스트 케이스 개수 ( 1 <= k <= 5

현재 구슬보다 큰 구슬의 개수가 (n+1)//2 개 이상이거나,작은 구슬의 개수가 (n+1)//2 개 이상이라면 그 구슬은 절대 중간값이 될 수 없다.현재 구슬보다 큰 구슬에 대한 연결 그래프와 현재 구슬보다 작은 구슬에 대한 연결 그래프를 각각 만든다.1번 구슬부터

1 ~ n까지의 도시와 m개의 단방향 도로는 1 이다.특정 도시 x부터 출발하여 도달할 수 있는 모든 도시 중에서,최단 거리가 정확히 k인 모든 도시들의 번호를 출려하는 프로그램 작성하는 문제이다.n : 도시의 개수 ( 2 <= n <= 300000 )m :

n개의 도시와 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다.도시의 번호는 1 ~ n까지일때, A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고한다.첫째 줄에 도시의 개수 n ( 1 <= n <= 1000 )둘째 줄에

n x n 바둑판 모양의 n^2개의 방이 있다방은 검은 방과 흰 방으로 구성되어 있다.검은방은 사면이 벽으로 싸여 있어 들어갈 수 없다서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다.왼줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고,아랫줄 맨 오른

암흑 군주 이민혁 마법 구술을 얻어 티떱 숲에 홍수를 일으킬 것이다.숲에는 고슴도치 한마리 살고 있다.고슴도치는 친구 비버의 굴로 가능한 빨리 도망가 홍수를 피하고자 한다.숲의 지도는 R행 C열이고비어있는 곳은 ' . '으로물이 차있는 곳은 ' \* '으로돌은 ' x

토마토를 보관하는 큰 창고가 있다.격자모양 상자의 칸에 하나씩 넣고, 상자들을 수직으로 쌓아 올려 보관한다.보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있다.보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은

n명의 학생들을 키 순서대로 줄 세운다각 학생의 키를 직접 잴 수 없어서두 학생의 키를 비교하는 방법 사용모든 학생들을 다 비교하지 못하고 일부 학생들의 키만을 비교일부 학생들의 키를 비교한 결과 주어지면, 줄 세우는 프로그램 작성n : 학생 수 ( 1 <= n

여러가지 부품을 조립하여 장난감을 만든다.장난감을 만드는데는 기본 부품가 그 기본 부품으로 만든 중간 부품이 사용된다.기본 부품은 더 이상 작은 부품들로 나눌 수 없는 최소 단위 부품이다.어떤 장난감 완제품과 그에 필요한 부품들 사이의 관계가 주어져 있을 때 하나의 장

n 개의 정점이 있는 그래프가 주어진다.모든 정점의 번호는 1보다 크거나 같고 n보다 작거나 같다.조건 :v1에서 v2로 연결된 간선이 있다면, v2의 번호는 v1보다 커야 한다.위 조건을 이용하여 그래프의 번호를 다시 매긴 후에, 1번 정점의 새로 고친 번호를 m1,

월드 나라는 모든 도로가 일방통행인 도로이고 싸이클이 없다.많은 사람들이 지도를 그리기 위해서 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로 탐색하고자 한다.지도를 그리는 사람들이 사이가 좋아서 지도를 그리고 도착 도시에서 모두 다 만나기로 하였다.

n x n 크기 시험관가 있다.시험관은 1 x 1 크기의 칸으로 나뉘어져있다.특정한 위치에는 바이러스가 존재할 수 있다.모든 바이러스는 1번부터 k번까지의 바이러스 종류 중 하나에 속한다.모든 바이러스는 1초마다 상하좌우의 방향으로 증식한다매초마다 낮은 종류의 바이러스

루트 노드가 유일한 이진 트리가 있다.모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다.자식이 없는 노드를 리프 노드라고 부른다.BT(이진 트리, Binary Tree)의 모든 노드를 탐색하는 방법은 전위 순회(preorder), 중위

순차 탐색의 시간복잡도가 크기 때문에 정렬되어 있는 리스트에서 탐색 범위를 좁혀가며 데이터를 탐색하는 방법이다.순차 탐색의 시간 복잡도를 $log$ 만큼 줄일 수 있다.n이 엄청 큰 경우, 시간복잡도를 $O(log N)$으로 처리해야겠다라고 생각이 드는 경우 시도해볼법

n 개의 섬으로 이루어진 나라가 있다.이들 중 몇 개의 섬 사이에는 다리 설치되어 있어 차들이 다닐 수 있다.두 개의 섬에 공장을 세워두고 물품 생산한다.물품을 생산하다 보면 공장에서 다른 공장으로 생상 중이던 물품을 수송해야 할 일이 있다.각각의 다리마다 중량 제한이

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물했다.이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일이다.어느날 짓궃은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낮장의 타일들을 붙여서 한 쌍으로 이루어진 00타일을 만들

우리나라 화페, 특히 동전의 단위로는 1원, 5원, 10원, 50원, 100원, 500원이 있다.이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다.(1원짜리 30개) 또는 (10원짜리 2개와 5원짜리 2개) 등의 방법이 가능하다.동전의

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때,모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.두 문자열이 주어진다. 두 문자열의 LCS의 길이를 출력하시오.동적 계획법의 문제들은 점화식을

기숙사에 살고 있는 준규는 한 개의 멀티탭 이용한다.준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품 사용하면서 어쩔 수 없이 각종 전기용품의 프러그를 뺐다 꽂았다 하는 불편함을 겪고 있다.준규는 생활 패턴을 분석하여 자기가

준규가 가지고 있는 동전은 총 N종류이다. 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다.이때 필요한 동전의 개수의 최솟값을 구하는 프로그램을 작성하시오K 원을 만드는데 필요한 동전 개수의 최솟값 출력N : 동전의 종류

한 개의 회의실이 있는데, 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들고자한다.각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.회의는 한번 시작하면 중간에 중

최고만을 지향하는 대기업 진영 주식회사의 신규 사원 채용은 1차 서류심사와 2차 면접시험으로 이루어진다.회사는 최고의 인재들만 사원으로 선발하고 싶다.그래서 진영 주식화사는 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다

세준이는 양수와 +, - 그리고 괄호를 가지고 식을 만들었다.그리고 나서 세준이는 괄호를 모두 지웠다.세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오식은 0 ~ 9, +, - 만으로

계단오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.각각의 계딴에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.규칙계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.연속으로 세 개의 계단을

효주는 포도주 시식회에 갔다. 그 곳에는 테이블 위에 다양한 포도주 잔이 일렬로 놓여 있다.효주는 포도주 시식을 하려고 하는데 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로

n개의 정수로 이루어진 임의의 수열이 주어진다.우리는 이 중 연속된 며 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.단 수는 한 개 이상 선택해야 한다.예를 들어10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어

RGB 거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는

연결리스트가 펠린드롬인지 판별하라.연결 리스트를 순회하여 리스트 / deque 으로 만들어서 첫 인덱스와 마지막 인덱스를 차례로 비교하여 같은지 틀린지를 판별한다.Runner 기법을 이용한 방법한번에 한 칸 이동하는 slow 포인터, 한번에 두 칸 이동하는 fast 포

문제 출처정렬되어 있는 두 연결 리스트가 있을 때, 두 연결 리스트를 합치시오두 연결 리스트가 이미 정렬되어있기 때문에 각각의 처음 인덱스부터 노드의 값을 하나씩 비교하여 더 작은 값을 새로운 연결리스트(current.next) 로 추가한다.두 연결 리스트 중 하나의

prices 배열이 주어진다.i번째 인덱스이 값은 i번째 날 주식의 가격이다.주식을 살 날과 주식을 팔 날을 하루씩만 선택하여 얻을 수 있는 이익 중 가장 큰 값을 반환하시오.만약 이익을 얻을 수 없는 경우 0을 출력하시오for loop을 통해 주식의 최솟값과 그 때까

원소가 정수이고 개수가 2의 배수인 배열이 주어진다.각 원소들을 두개씩 짝 지어 n개의 pair 를 만들고 각각의 pair에서 작은 값을 더했을 때 그 합이 가장 큰 수를 반환하시오.nums 리스트 오름차순 정렬한다문제 요구 조건이 2개씩 짝지은 각각의 pair에서 작

금지된 단어를 제외하고 가장 많이 사용된 단어를 출력하시오.모든 단어는 대소문자 구분이 없으며 소문자의 형태로 반환하시오.python의 regular expression과 lower() 메서드를 통해 소문자 알파벳이 아닌 character는 공백으로 바꾼다.단어의 빈도

아래 기준에 맞게 로그를 재정렬하기로그의 가장 앞 부분은 식별자이다.문자로 구성된 로그가 숫자 로그보다 앞에 온다.로그의 내용을 기준으로 정렬하고 내용이 동일할 경우, 식별자를 기준으로 정렬한다.숫자 로그는 입력받은 순서대로 한다.입력받은 로그를 문자열 split()을

주어진 배열에서 합을 0으로 만들 수 있는 3개의 원소를 출력하시오가장 쉽게 생각할 수 있는 방법은 3중 반복문을 통해 3개의 수의 합이 0이 되는 모든 경우의 수를 확인 하는 방법이다. 하지만 이 방법은 시간 초과가 난다.따라서 투포인터를 이용하여 반복문을 돌면서 조