반응형

1. DFS(Depth First Search; 깊이 우선 탐색)의 개념

■ 루트 노드[또는 임의의 노드]에서 시작하여 형제 (sibling) 노드로 넘어가기 전에 시작한 분기의 마지막 노드까지 깊게 탐색하는 방법

■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법

■ 스택 또는 재귀함수를 이용하여 구현

 

2. DFS 노드 방문 순서

■ 결과 : 1 → 2 → 4 → 5 → 6 → 3 → 7 → 10 → 8 → 9

    - step1) 도달 가능한 마지막 노드(막다른 길)까지 이동한다.

    - step2) 지나처 온 최근 갈림길(형제노드)로 되돌아 간다.

    - step3) 모든 노드를 탐색할 때까지 step1과 step2를 반복한다.

 

3. 그래프 표현

■ 그래프는 인접 리스트로 보기 쉽게 표현할 수 있다.

1 2, 3
2 1, 4
3 1, 7, 8, 9
4 2, 5, 6
5 4
6 4
7 3, 10
8 3
9 3
10  

 

■ 인접리스트는 2차원 배열[리스트] 또는 테이블[dictionary] 자료구조로 정의할 수 있다.

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def dfs(graph, start, visited = []):
    visited.append(start)
 
    for node in graph[start]:
        if node not in visited:
            dfs(graph, node, visited)
 
    return visited
 
 
if __name__ == '__main__':
    graph = dict() 
    graph['1'] = ['2', '3']
    graph['2'] = ['1', '4']
    graph['3'] = ['1', '7', '8', '9']
    graph['4'] = ['2', '5', '6']
    graph['5'] = ['4']
    graph['6'] = ['4']
    graph['7'] = ['3', '10']
    graph['8'] = ['3']
    graph['9'] = ['3']
    graph['10'] = ['7']
 
    result = dfs(graph, '1')
    print(result)
 cs

 

5. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function dfs(graph, v, visited = []) {
    
    visited[v] = true;
    console.log(v);
  
    for (let node of graph[v]) {
      if (!visited[node]) {
        dfs(graph, node, visited);
      }
    }
  }
 
 
graph = []
graph['1'] = ['2', '3']
graph['2'] = ['1', '4']
graph['3'] = ['1', '7', '8', '9']
graph['4'] = ['2', '5', '6']
graph['5'] = ['4']
graph['6'] = ['4']
graph['7'] = ['3', '10']
graph['8'] = ['3']
graph['9'] = ['3']
graph['10'] = ['7']
 
result = dfs(graph, '1')
console.log(result)
 cs

 

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04
[백준] 읽어버린 괄호  (0) 2024.10.04
[백준] ATM  (1) 2024.10.03
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/13305

 

2. 핵심요약

■ 문제유형 : 탐욕(Greedy) 알고리즘

■ 1번째 Row: 도시의 개수를 나타내는 정수 

■ 2번째 Row: 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 구성

■ 3번째 Row: 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 구성

 

3. 문제풀이 접근

■ 첫번째 도시에서는 가격에 상관없이 주유를 할 수밖에 없다.

■ 두번째 도시부터는 다음(오른쪽) 도시들의 가격과 비교하여 미리 주유 여부를 결정한다.

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
isTest = True
if isTest:
    f = open("./13305.txt", 'r')
    city_cnt = int(f.readline())
    distArr = list(map(int, f.readline().split(' ')))
    priceArr = list(map(int, f.readline().split(' ')))
else:
    city_cnt = int(input())
    distArr = list(map(int, input().split(' ')))
    priceArr = list(map(int, input().split(' ')))
 
sum = 0
minPrice = priceArr[0]
for i in range(len(priceArr) - 1):
  if minPrice > priceArr[i]:
    minPrice = priceArr[i]
 
  sum += minPrice * distArr[i]
 
print(sum)
 cs

 

5. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./13305.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
city_count = parseInt(input[0]);
distArr = input[1].split(' ').map(Number);
priceArr = input[2].split(' ').map(Number).slice(0, city_count - 1);
 
let sum = BigInt(0);
let minPrice = priceArr[0];
for (let i = 0; i < priceArr.length; i++) {
  if (minPrice > priceArr[i]) {
    minPrice = priceArr[i];
  }
  sum += BigInt(minPrice) * BigInt(distArr[i]);
}
 
console.log(String(sum));
 
 cs

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

DFS(Depth First Search; 깊이 우선 탐색) 파이썬 / 자바스크립트 구현  (1) 2024.11.12
[백준] 수들의 합  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04
[백준] 읽어버린 괄호  (0) 2024.10.04
[백준] ATM  (1) 2024.10.03
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/1789

 

2. 핵심요약

■ 문제유형 : 탐욕(Greedy) 알고리즘

■ S: 자연수의 합 (문제의 Input)

■ N: 합계 S가 성립하는 자연수들의 최대 갯수

 

3. 문제풀이 접근

■ 최대한 많은 숫자를 이용하여 합계 S를 만들기 위해서는 가장 작은값(1)부터 차례대로 더해 나가야 한다.

■ 그 다음 더해지는 숫자를 고려하여 더해지는 값이 S 보다 더 크게 될때까지 카운트한다.

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
isTest = True
if isTest:
    f = open("./1789.txt", 'r')
    s = int(f.readline())
else:
    s = int(input())
 
current = 0
cnt = 0
 
adder = 1
 
while (s >= current):
    current += adder
 
    adder += 1
    cnt += 1
 
    if adder > s - current:
        break
 
print(cnt)
 cs

 

 

5. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./1789.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
s = parseInt(input[0]);
 
current = 0
cnt = 0;
 
adder = 1;
 
while (s >= current) {
    current += adder;
    console.log(current);
 
    adder++;
    cnt++;
 
    if (adder > s - current) {
        break;
    }
}
 
console.log(cnt);
 cs

 

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

DFS(Depth First Search; 깊이 우선 탐색) 파이썬 / 자바스크립트 구현  (1) 2024.11.12
[백준] 주유소  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04
[백준] 읽어버린 괄호  (0) 2024.10.04
[백준] ATM  (1) 2024.10.03
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/2839

 

2. 핵심요약

■ 문제유형 : 탐욕(Greedy) 알고리즘

 

3. 문제풀이 접근

■ 먼저 큰 봉지(5kg)를 이용하여 설탕을 담는다.

■ 남은 분량을 작은 봉지(3kg) 단위로 배분하여 정확히 떨어지는지(나머지가 0) 여부를 확인한다.

■ 작은 봉지(3kg) 단위로 배분하여 떨어지지 않으면(나머지가 0 아님) 큰 봉지(5kg)의 갯수를 하나씩 줄인다.

■ 남은 분량이 작은 봉지(3kg) 단위로 배분하여 정확히 떨어지는면(나머지가 0) 봉지의 합이 최소값이 된다.

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
isTest = True
if isTest:
    f = open("./2839.txt", 'r')
    N = int(f.readline())
else:
    N = int(input())
 
answer = -1
for i in range(int(N / 5), -1, -1):
    remains = N - i * 5
 
    if remains % 3 == 0:
        answer = i + int(remains / 3)
        break
 
print(answer)
 cs

 

 

5. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./2839.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
let N = input[0];
 
let answer = -1;
for(let i = parseInt(N / 5); i >= 0; i--) {
    let remains = N - i * 5;
 
    if (remains % 3 === 0) {
        answer = i + parseInt(remains / 3);
        break;
    }
}
 
 
console.log(answer);
 cs

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 읽어버린 괄호  (0) 2024.10.04
[백준] ATM  (1) 2024.10.03
[백준] 동전 0  (0) 2024.10.03
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/1541

 

2. 핵심요약

■ 첫째 줄에 식이 주어진다.

■ 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있다.

■ 가장 처음과 마지막 문자는 숫자이다. → 식의 가장 첫 부분은 양수로 시작한다.

■ 연속해서 두 개 이상의 연산자가 나타나지 않는다.

 

3. 문제풀이 접근

■ 문제의 내용을 종합하면 아래와 같은 형태를 만들어야만 식의 결과가 최소값으로 나타난다.

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
isTest = True
if isTest:
    f = open("./1541.txt", 'r')
    input = f.readline()
else:
    input = input()
 
q_tkn_arr = input.split('-')
 
answer = 0
for i in range(len(q_tkn_arr)):
    sub_sum = 0
    s_tkn_arr = map(int, q_tkn_arr[i].split('+'))
    for s_tkn in s_tkn_arr:
        sub_sum += s_tkn
 
    if len(q_tkn_arr) == 1 or i == 0:
        answer = sub_sum
    else:
        answer -= sub_sum
 
print(answer)
 cs

 

5. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./1541.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
let q = input[0];
q_tkn_arr = q.split('-')
 
answer = 0
for (let i = 0; i < q_tkn_arr.length; i++) {
    let sub_sum = 0;
    s_tkn_arr = q_tkn_arr[i].split('+').map(Number)
    for (let j = 0; j < s_tkn_arr.length; j++) {
        sub_sum += s_tkn_arr[j];
    }
 
    if (q_tkn_arr.length === 1 || i === 0) {
        answer = sub_sum;
    } else {
        answer -= sub_sum;
    }
}
 
console.log(answer);
 cs

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04
[백준] ATM  (1) 2024.10.03
[백준] 동전 0  (0) 2024.10.03
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/11399

 

2. 핵심요약

■ 1번째 Row : 사람의 수 N(1 ≤ N ≤ 1,000)

■ 2번째 Row : 각 사람이 돈을 인출하는데 걸리는 시간

1
2
5
3 1 4 3 2
 cs

 

3. 문제풀이 접근

■ 문제유형 : 탐욕(Greedy) 알고리즘

■ 최소 시간의 합을 구하기 위해서 점유시간이 낮은 사람부터 먼저 처리 되어야 한다.

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
isTest = True
if isTest:
    f = open("./11399.txt", 'r')
    cnt = int(f.readline())
    occupy = list(map(int, f.readline().split()))
else:
    cnt = int(input())
    occupy = list(map(int, input().split()))
 
# 배열을 오름차순으로 정렬
occupy.sort()
 
sum = 0
answer = 0
for x in occupy:
    sum += x            # 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)
    answer += sum       # 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)의 누적합
 
print(answer)
 cs

 

5. JavaScript 코딩

■ 배열.sort()와 배열.sort((a, b) => a - b)의 정렬 방식 차이점

    - 배열.sort() : ['3', '12', '215']인 경우, ['12', '215', '3']으로 정렬된다.

    - 배열.sort((a, b) => a - b) : ['3', '12', '215']인 경우, ['3', '12', '215']으로 정렬된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./11399.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
let cnt = Number(input[0]);         // 사람 수
let occupy = [];                    // 각 사람이 돈을 인출하는데 걸리는 시간
for (let i = 0; i < cnt; i++) {
    occupy.push(Number(input[1].split(' ')[i]));
}
 
// 배열을 오름차순으로 정렬
occupy.sort((a, b) => a - b);
//occupy.sort()   // 위의 것과 차이점 중요
 
let sum = 0;
let answer = 0;
for (let i = 0; i < occupy.length; i++) {
    sum += occupy[i];       // 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)
    answer += sum;          // 각 사람이 (대기한 시간 + 돈을 인출하는데 걸리는 시간)의 누적합
}
 
console.log(answer);
 cs

 

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04
[백준] 읽어버린 괄호  (0) 2024.10.04
[백준] 동전 0  (0) 2024.10.03
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/11047

 

2. 핵심요약

■ 1번째 Row, 1번째 Col : 동전의 갯수

■ 1번째 Row, 2번째 Col : 주어진 동전 가격의 합으로 만들어야할 합계 가격

■ 2번째 Row 부터 : 각 동전의 가격

1
2
3
4
5
6
7
8
9
10
11
10 4790
1
5
10
50
100
500
1000
5000
10000
50000
 cs

 

 

3. 문제풀이 접근

■ 문제유형 : 탐욕(Greedy) 알고리즘

■ 최소한의 동전 갯수만 사용하기 위해 동전 단가가 큰 것부터 써야 한다.

■ 몫 연산자와 나머지 연산자 문법을 알고 주어진 합계 가격으로부터 필요한 동전의 갯수(최소값)을 구한다.

    - 파이썬 연산자 문법 : 나눗셈의 몫(//), 나눗셈의 나머지(%)

    - 자바스크립트 연산자 문법 : 나눗셈의 몫(/), 나눗셈의 나머지(%)

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
isTest = True
if isTest:
    f = open("./11047.txt", 'r')
    cnt, target = map(int, f.readline().split(' '))
else:
    cnt, target = map(int, input().split(' '))
 
arr = []
for i in range(1, cnt+1):
    if isTest:
        arr.append(int(f.readline()))
    else:
        arr.append(int(input()))
 
answer = 0
arr.reverse()
for item in arr:
    answer += target // item
    target = target % item
 
    if target == 0:
        break
 
print(answer)
 
 cs

 

5. JavaScript 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./11047.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
let cnt = Number(input[0].split(' ')[0]);       // 동전의 갯수
let target = Number(input[0].split(' ')[1]);    // 목표값
 
arr = [];
for(let i = 1; i < cnt + 1; i++) {
    arr.push(Number(input[i]));
}
 
// 문제에서 동전의 가치는 이미 오름차순으로 주어짐.
answer = 0;
for(let i = arr.length - 1; i >= 0; i--) {
    answer += parseInt(target / arr[i]);
    target = target % arr[i];
 
    if (target === 0) {
        console.log(answer);
        return answer;
    }
}
 cs

 

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04
[백준] 읽어버린 괄호  (0) 2024.10.04
[백준] ATM  (1) 2024.10.03
반응형

1. Coding Assistants

    ① copilot

        - URL : https://github.com/features/copilot

        - 주요 서비스 : 코드 자동 완성, 코드 추천, 다양한 언어 지원.

        - 요금: 월 $10 또는 연간 $100 (개인 사용자 기준).

 

    ② Amazon Q Developer

        - URL : https://aws.amazon.com/ko/q/

 

생성형 AI 기반 도우미 - Amazon Q - AWS

Amazon Q는 Wiki, 인트라넷, Atlassian, Gmail, Microsoft Exchange, Salesforce, ServiceNow, Slack, Amazon Simple Storage Service(S3) 등 일반적으로 사용되는 40개 이상의 비즈니스 도구에 쉽고 안전하게 연결됩니다. 엔터프라

aws.amazon.com

 

        - 주요 서비스 : 자연어 기반 코드 작성, AWS 서비스와 통합

        - 요금: 사용량 기반 요금, 세부 사항은 AWS 가격 페이지 참조

 

    ③ codeium

        - URL : https://codeium.com/

 

Codeium · Free AI Code Completion & Chat

Codeium offers best in class AI code completion, search, and chat — all for free. It supports over 70+ languages and integrates with your favorite IDEs, with lightning fast speeds and state-of-the-art suggestion quality.

codeium.com

 

        - 주요 서비스 : 코드 완성, 코드 설명, 여러 언어 지원

        - 요금: https://codeium.com/pricing

2. Code Generation

    ① Claude

        - URL : https://claude.ai/login?returnTo=%2F%3F

 

Claude

Talk with Claude, an AI assistant from Anthropic

claude.ai

 

        - 주요 서비스 : 자연어 처리 기반 코드 생성, 다양한 언어 지원.

 

    ② Sourcegraph

        - URL : https://sourcegraph.com/

 

Sourcegraph | Code Intelligence Platform

Sourcegraph’s code intelligence platform makes it easy for devs to write, fix, and maintain code with Cody, the AI coding assistant, and Code Search.

sourcegraph.com

 

        - 주요 서비스 : 코드 검색, 코드 탐색 및 분석 도구

        - 요금: https://sourcegraph.com/pricing

 

Sourcegraph | Pricing

Pricing and plans for Sourcegraph Cody and Code Search. Get started with a free trial today.

sourcegraph.com

 

3. Image to Code 변환

    ① Builder.io

        - URL : https://www.builder.io/

 

Builder.io: Drag & Drop Headless CMS

Drag and drop with your components, right within your existing site or app. Build and optimize digital experiences for any tech stack, visually..

www.builder.io

 

        - 주요 서비스 : 시각적 사이트 빌더, 코드 변환 기능

        - 요금: https://www.builder.io/m/pricing

 

Pricing - Builder.io

Build, preview, and go live for free today. And as you expand, choose one of our scalable pricing plans to move faster and fuel sustainable growth

www.builder.io

 

 

    ② snyk

        - URL : https://snyk.io/

 

Developer security | Snyk

Enable developers to build securely from the start while giving security teams complete visibility and comprehensive controls.

snyk.io

 

        - 주요 서비스 : 보안 취약점 탐지 및 코드 변환.

        - 요금: https://snyk.io/plans/

 

Plans and pricing | For teams of all sizes | Snyk

Developer security solution from Snyk. Simple, flexible pricing for teams of all sizes. Start a free trial today.

snyk.io

 

    ③ pieces.app

        - URL : https://pieces.app/

 

Pieces for Developers - Your Workflow Copilot

Integrate your toolchain, efficiently capture, enrich, and reuse materials. Enhance collaboration with the assistance of an on-device copilot.

pieces.app

 

        - 주요 서비스 : 코드 스니펫 저장 및 공유, 이미지에서 코드 변환.

 

    ④ otter.ai

        - URL : https://otter.ai/

 

Otter.ai - AI Meeting Note Taker & Real-time AI Transcription

Otter.ai uses an AI Meeting Assistant to transcribe meetings in real time, record audio, capture slides, extract action items, and generate an AI meeting summary.

otter.ai

 

        - 주요 서비스 : 음성 텍스트 변환, 회의록 작성, 이미지에서 코드 생성.

        - 요금: 기본 무료, 프로 플랜 월 $8.33.

 

4. IDE Plugin

    ① cursor

        - URL : https://www.cursor.com/

 

Cursor

The AI Code Editor

www.cursor.com

 

        - 주요 서비스 : AI 기반 코드 작성 및 자동 완성.

        - 요금: https://www.cursor.com/pricing

 

Pricing | Cursor - The AI-first Code Editor

500 fast premium requests per month Unlimited slow premium requests

www.cursor.com

 

 

 

반응형
저작자표시

'AI' 카테고리의 다른 글

LangChain(랭체인) with 파이썬  (0) 2024.05.25
음성 활용 AI 서비스 사이트 종류 및 특징  (0) 2024.05.25
AI 기반 영상/비디오 생성 서비스 종류  (0) 2024.05.25
Google Gemini 앱 개발을 위한 API 키 발급  (0) 2024.03.15
ChatGPT 앱 개발을 위한 API 키 발급 및 연동 테스트  (0) 2024.03.15

+ Recent posts

티스토리툴바