코딩 일지 코딩 일지

이진탐색이진탐색이란, 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 시작점, 끝점, 중간점을 배열의 인덱스로 정의하고, 찾고자하는 값과 중간점을 비교하여 탐색 범위를 반씩 줄인다. 이와 반대되는 개념으로 순차탐색이 있는데, 순차탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다. 이진탐색은 데이터가 정렬되어있어야 하고, 시간 복잡도는 O(log N)이다. 순차탐색의 시간복잡도는 O(N)이다. 이진탐색 코드 def binary_search(array, target, start, end): while start target: end = mid - 1 else: start = mid +..

문제0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.제한 사항- numbers의 길이는 1 이상 100,000 이하입니다.- numbers의 원소는 0 이상 1,000 이하입니다.- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.입출력 예해결 아이디어간단할 줄 알았는데, 생각보다 까다로운 ..

문제배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.3. 2에서 나온 배열의 3번째 숫자는 5입니다.배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.제한사항- array의 길이는 1 이상 100 이하입니다.- ..

정렬정렬이란, 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. 정렬 알고리즘의 종류는 많지만, 이번 포스팅에서는 강의에서 다루는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만을 소개하겠다. 선택 정렬 (Selection Sort)처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 알고리즘이다. 예를들어 아래와 같은 숫자들의 배열이 있다고 하자.1. 정렬되지 않은 전체 배열에서 최솟값 (0)을 찾고, 맨 앞의 데이터 (7)과 바꾼다.2. 정렬된 0을 제외하고 나머지 정렬되지 않은 배열에서 최솟값 (1)을 찾고, 맨 앞의 데이터 (5)와 바꾼다.위와 같은 방법을 반복하게되면, 전체 정렬된 배열은 다음과 같이 나온다.선택정렬 - 시간 복잡도선택 정렬은 N..

문제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][..

BFS( Breadth-First Search)BFS는 너비 우선 탐색 방식으로, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 특정 경로에서의 최단거리 문제를 풀 때 많이 쓰인다.DFS는 스택 자료구조를 사용했다면, BFS는 큐를 사용하고, 구체적인 작동 방식은 다음과 같다.탐색 시작 노드를 큐에 삽입하고 방문 처리큐에서 노드 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리더 이상 2번의 과정을 수행할 수 없을 때까지 반복함. 이 그래프를 이번엔 BFS 방식으로 노드들을 방문해보자. 1. 시작 노드인 '1'을 큐에 삽입하고 방문 처리 2. 큐에서 노드 '1'을 꺼내 방문하지 않은 인접 노드 '2','3','8'을 큐에 삽입하고 방문 처리 같은..

문제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 이하인 자연수입..