코테

시간 복잡도 시간 복잡도란 알고리즘이 주어진 문제를 해결하기 위한 연산 횟수 시간 복잡도 유형 1.빅-오메가 Ω(n) : 최선일 때(best case)의 연산 횟수를 나타내는 표기법 가장 빠른 케이스, 어떤 식의 최고 차수 2.빅-세타 𝚯(n) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법, 빅-오, 빅-오메가를 만족한느 교집합 평균 실행시간 3.빅-오 O(n) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 가장 느린 케이스 상수는 무시 혹은 1로 통일 상한선을 기준으로 하여 모든 경우의 수를 포함 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋은 이유 프로그램은 다양한 테스트 케이스를 수행하여 모든 케이스를 만족할만한 케이스를 염두해 둬야 하는데 그 경우가..

문제 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째 방법은 11개의 ..

문제 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][..

문제 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이..

소수를 구하는 알고리즘 - 에라토스테네스의 체 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간..

문제 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다. 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요. 제한사항 word의 길이는 1 이상 5 이하입니다. word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다. 입출력 예 word result "AAAAE" 6 "AAAE" 10 "I" 1563 "EIO" 1189 입출력 예 설명 입출력 예 #1 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA..

DFS( Depth first Search) - 깊이 우선 탐색 그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 기능 특징 시간 복잡도(노드 수 : V, 에지 수 : E) 그래프 완전 탐색 재귀함수, Stack(LIFO) 사용 O(V+E) DFS 원리 시작할 노드를 정한 후 사용할 자료구조 초기화 Stack에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입 Stack 자료구조에 값이 없을 때까지 반복 DFS 구현 방법 두 가지 재귀 1 -> 2 -> 5 -> 6 -> 3 -> 4 -> 스택 1 -> 3 -> 4 -> 6 -> 2 -> 5 -> * 재귀의 ..

BFS (Breadth First Search ) - 너비 우선 탐색 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.(=최단 경로) 기능 특징 시간복잡도(노드 수 : V, 에지 수 : E) 완전 탐색 Queue, FIFO 사용 O(V+E) BFS 원리 시작점을 구한고 자료구조(인접행렬or 인접리스트)를 초기화 BFS 호출 (큐에서 노드를 꺼낸 후 노드의 인접 노드를 다시 큐에 삽입, 값이 없을 때까지 반복) 방문 여부 체크 코드 package com.java.coding; import java.util.LinkedList; import java.util.Queue; public class BFSExam { publi..