알고리즘9

• 

  [Algorithm] BAEKJOON 10026번. 적록색약 (python) [ 백준 10026번. 적록색약 ] 문제명 : 적록색약 사용 언어 : python3 알고리즘 : BFS(너비 우선 탐색) 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 알고리즘 및 코드 : 적록색약이 아닌 사람의 경우를 먼저 체크하고, 적록색약인 사람은 'R'을 'G'로 바꿔주고 G/B.. Algorithm 2024. 1. 26.

• 

  [Algorithm] Softeer 장애물 인식 프로그램 (Python) [ Softeer 연습문제 - 장애물 인식 프로그램 ] Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 문제명 : 장애물 인식 프로그램 사용언어 : Python 알고리즘 : DFS/BFS -> 필자는 BFS 사용으로 풀이. 문제 알고리즘 및 풀이 이 문제는 이진 행렬에서 그룹의 개수와 각 그룹의 크기를 찾는 문제이다. 필자는 BFS(너비 우선 탐색) 알고리즘을 활용했다. 큐를 활용하여 한 정점에서 시작하여 인접한 정점을 탐색하는 방법으로 접근하였다. (x, y) 좌표를 순회하면서 "1"인 곳을 발견하면 해당 좌표에서 BFS를 시작하고 발견된 좌표는 방문 처리를 위해 "0"으로 바꿔준다. 이는 그룹의 크기를 측정하는 중복 방문을 방지한다. - 전역 변수 활용 : 'cnt' 변수는 그룹.. Algorithm 2024. 1. 24.

• 

  [Algorithm] Softeer 조립라인 - Lv.3 (Python) [ Softeer 연습문제 - 조립라인 ] Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 문제명 : 조립라인 (Level.3) 사용언어 : Python 사용 알고리즘 : DP (Dynamic Programming) 문제 동일한 자동차를 생산하는 2개의 조립 라인 A와 B가 있다. 두 조립라인에는 각각 N개의 작업장이 있다. 각각의 작업장을 Ai (1 ≤ i ≤ N)와 Bi (1 ≤ i ≤ N)로 표시하자. Ai 작업장과 Bi 작업장은 동일한 작업을 수행하지만 작업시간은 다를 수 있다. A 조립 라인의 경우 A1 작업장에서 최초 조립이 시작되고, Ai 작업장에서 작업이 종료되면 바로 Ai+1 작업장에서 작업을 시작할 수 있다. B 조립 라인도 동일한 방식으로 조립을 진행한다. Ai .. Algorithm 2024. 1. 23.

• 

  [Algorithm] Softeer 금고털이 - Lv.2 (Python) [ Softeer 연습문제 - 금고털이 ] Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 문제명 : 금고털이 사용언어 : Python 사용 알고리즘 : 그리디 알고리즘 문제 설명 루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다. 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가? 루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다. ▼ 실행 코드 ▼ import sys input = sys.stdin.readline W, N = map(int, input().split()) jewelry = [l.. Algorithm 2024. 1. 19.

• 

  [Algorithm] BAEKJOON 12789번. 도키도키 간식드리미 (Python) [ 백준 12789번. 도키도키 간식드리미 ] 문제명 : 도키도키 간식드리미 사용 언어 : Python3 자료구조, STACK(스택) 문제 설명 입력 입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다. 다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다. 출력 승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않으면 "Sad"를 출력한다. ▼ 실행코드▼ from collections import deque N = int(input()) stu_queue = deque(map(int, input().split())) stack = deque() i = 1.. Algorithm 2024. 1. 18.

• 

  [Algorithm] BAEKJOON 2504번. 괄호의 값 (Python) [ 백준 2504번. 괄호의 값 ] 문제명 : 괄호의 값 사용 언어 : Python3 주요 알고리즘 : stack(스택) 문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 .. Algorithm 2024. 1. 17.

• 

  [Algorithm] 주차 요금 계산 - 2022 KAKAO BLIND RECRUITMENT [ 코딩테스트 연습 - 프로그래머스 Lv.2 ] 문제명 : 주차 요금 계산 [ 2022 KAKAO BLIND RECRUITMENT ] 사용 언어 : Python3 주요 사용 핵심 : dictionary를 사용하여 문제 해결. 문제 설명 주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주합니다. 0000번 차량은 18:59에 입차된 이후, 출차된 내역이 없습니다. 따라서, 23:59에 출차된 것으로 간주합니다. 00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산합니다. 누적 주차 시간이 기본 시간이하라면, .. Algorithm 2024. 1. 16.

• 

  [Algorithm] 타겟 넘버 - 프로그래머스 Lv.2 [ 코딩테스트 연습 - 프로그래머스 Lv.2 ] 문제명 : 타겟 넘버 [깊이/너비 우선탐색(DFS/BFS)] 사용 언어 : Python3 사용 알고리즘 : DFS (깊이 우선 탐색) 이 문제는 가능한 모든 경우의 수를 탐색해야 하므로, DFS(깊이 우선 탐색)을 사용하는 것이 적절하다. DFS를 통해 가능한 모든 순열을 생성하고, 각 순열에 대해 주어진 규칙에 따라 타겟 넘버를 만들 수 있는지 확인하는 방식으로 접근할 수 있다. DFS는 모든 경우의 수를 확인하는데에 유용하며, 이 문제에서도 모든 가능한 더하고 빼는 경우를 탐색할 수 있다. 문제 설명 ▽ 문제 해결방법 설계 및 코드작성. : DFS를 사용하여 가능한 모든 경우를 탐색하는 방법을 선택. : 재귀 함수를 통해 모든 순열을 생성하면서 각각의 .. Algorithm 2024. 1. 12.

• 

  [Algorithm] 깊이/너비 우선 탐색 (DFS/BFS) DFS (Depth First Search) : 깊이 우선 탐색 ▽ DFS 알고리즘 (코드블럭을 한글로 표현) 시작 노드를 옅은 회색 표시 후, 스택에 넣음 스택에 아무 노드가 없을 때까지: 스택 가장 위 노드를 꺼낸다 노드를 방문 (진한 회색) 표시한다 인접한 노드들을 모두 보면서: 처음 방문하거나 스택에 없는 노드면: 옅은 회색 표시를 해준다 스택에 넣어준다 ▽ DFS로 연결된 역 찾기 from collections import deque def dfs(graph, start_node): """dfs 함수""" stack = deque() # 빈 스택 생성 # 모든 노드를 처음 보는 노드로 초기화 for station_node in graph.values(): station_node.visited =.. Algorithm 2024. 1. 12.