알고리즘
-
[Python] 백준 14567 선수과목알고리즘/문제풀이 2021. 12. 15. 17:31
1. 문제 링크 https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 2. 문제 요약 1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지 출력한다. 3. 아이디어 정리 위상 정렬 진입 차수가 0인 모든 노드에 큐 넣기 큐가 빌 때까지 반복 큐에서 원소를 꺼내 나가는 간선 제거 새롭게 진입차수가 0이 된 노드에 큐 넣기 & 결과 넣기(최소 이수 학기, 현재 노드 결과 + 1) 4. 문제 풀이 4-1. 내풀이 import sys from collections ..
-
[Python] 백준 14888 연산자 끼워넣기알고리즘/삼성 역량 문제 2021. 12. 15. 17:18
1. 문제 링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 2. 문제 요약 N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것 구하기 3. 아이디어 정리 백트래킹으로 진행 Base condition(종료 조건): 모든 연산자를 넣은 경우 재귀: 사칙연산을 4개를 돌려 계산을 하고 백트래킹 진행 4. 문제 풀이 4-1. 내 풀이 """ 1. ..
-
위상정렬(Topological Sorting)알고리즘/알고리즘 공부 정리 2021. 12. 14. 23:46
이번 시간에는 위상 정렬에 대한 개념과 동작 과정을 알아본다. 이후 위상 정렬을 Python으로 구현해 본다. 1. 위상 정렬(Topological Sorting) 💡 정렬 알고리즘의 일종으로, 순서가 정해진 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다. ⇒ 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 1-1. 예시 - 선수과목을 고려한 학습 순서 설정 그림과 같이 총 3개의 과목이 있다고 가정하자. 세 과목을 모두 듣기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 순서로 과목을 들어야 한다. 만약 알고리즘 -> 자료구조 -> 고급 알고리즘 (X) 순서로 과목을 듣는다고 가정하자. 해당 순서는 올바른 학습 순서가 아니다..
-
[Python] programmers 여행 경로알고리즘/문제풀이 2021. 12. 12. 12:49
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 2. 문제 요약 방문하는 공항 경로를 배열에 담아 return 3. 아이디어 정리 백트래킹으로 진행합니다. 처음 ICN를 배열에 담아 넘겨줍니다. 티켓들 중 마지막으로 탐색한 값과 시작값이 같은 티켓 & 방문 안한 경우 재귀를 진행합니다. 4. 문제 풀이 4-1. 내 풀이 """ 항상 ICN 공항에서 출발 [a,..
-
[Python] 백준 2580 스도쿠알고리즘/문제풀이 2021. 12. 12. 12:47
1. 문제 링크 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 2. 문제 요약 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 3. 아이디어 정리 백트래킹으로 진행 0으로 된 부분 모두 수를 채운 경우 그만 0으로 된 좌표에 어떤 값이 가능한지 모두 백트래킹 진행 4. 문제 풀이 4-1. 내 풀이 import sys..
-
[Python] 백준 15656 N과 M (7)알고리즘/문제풀이 2021. 12. 12. 12:43
1. 문제 링크 https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 2. 문제 요약 N개의 자연수 중 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 3. 아이디어 정리 증가하는 순서 출력이므로 정렬을 진행한다. 백트래킹으로 M개를 선택할 때 출력하게 한다. ⇒ 종료 조건 같은 수 여러 개 가능하기 때문에 for 문에 조건을 없이 넣는다. 4. 문제 풀이 4-1. 내 풀이 import sys def dfs(list_): if len(l..
-
[Python] programmers 뉴스 클러스터링알고리즘/문제풀이 2021. 12. 4. 23:36
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 2. 문제 요약 두 문자열의 자카드 유사도를 출력 자카드 유사도: 교집합 크기 / 합집합 크기 3. 아이디어 정리 문자열 2개씩 끊기 교집합, 합집합 구하기 다중집합 구하기 교집합: 두 교집합에서 갯수 최소값 합집합: 두 교집합에서 갯수 최대값 4. 문제 풀이 4-1. 내 풀이 import math def get_set(s)..
-
[Python] programmers 입국심사알고리즘/문제풀이 2021. 12. 4. 23:34
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 2. 문제 요약 모든 사람이 심사를 받는데 걸리는 시간 최솟값 구하기 3. 아이디어 정리 이분 탐색을 통해 걸리는 예측 시간을 구한다. 해당 예측 시간으로 몇 명이 허용되는지 확인 허용 가능한 인원으로 left, right 값을 조절 4. 문제 풀이 4-1. 내 풀이 def solution(n, times): answer = 0 left = 0 r..