본문 바로가기

분류 전체보기

(102)
위상정렬 5594 https://www.acmicpc.net/problem/5594 위상정렬이란 ? "순서가 있는 작업" 문제를 푸는 알고리즘.즉, 선행 관계가 있는 일들을 올바른 순서로 나열할 떄 사용한다. 핵심 개념- 그래프 종류 : 방향 그래프 (사이클이 없는 그래프)- 목적 : 모든 노드를 "선행 관계를 지키면서" 나열하기 - 예시 : (1) 선수 과목이 있는 과목 순서 정하기 (2) 작업 간 선행 조건이 있는 공정 순서 (3) 빌드 의존성(어떤 파일을 먼저 컴파일해야 하는가) 동작 원리1. 진입차수 (indegree) : 각 노드로 들어오는 간선의 개수를 계산한다.2. 진입차수가 0인 노드(선행 조건이 없는 작업)부터 처리한다.3. 해당 노드와 연결된 간선을 제거하면서, 새로운 진입차수가 0이 된 노드를 큐에 ..
(복습 꼭) 다익스트라 32388 https://www.acmicpc.net/problem/32388 다익스트라 문제를 보면 좌표에서 점들간 "최단거리"를 구하는 문제이다.음수의 가중치가 없는 최단거리란 뭐다 ? "다익스트라" 다 !!! 아래 코드를 여러 번 보면서 다익스트라를 마스터 해보쟈.문제가 어려워도 알고리즘을 정확하게 알고 있으면 풀 수 있다. // 최단거리 -> 다익스트라 !! import java.io.*;import java.util.*;public class Main{ static int a, b; static int n; static int[][] nxny; static ArrayList[] graph; public static void main(String[] arge)thr..
[Programmers] 미로 탈출 명령어 (미완) https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 # (x, y)에서 (r, c)로 이동해 탈출해야 함 # 미로 탈출 조건 # 격자 밖으로 못나감 # 이동거리 총 k # 같은 격자 두 번 이상 방문 가능 # 문자열이 사전 순으로 가장 빠른 경로로 탈출 # dfs (최단거리 아니라 k거리) def solution(n, m, x, y, r, c, k): answer = [] # r, l, d, u 동서남북 dx = [0, 0, 1, -1]..
[Progrmmers] 후보키 https://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 # 후보키의 갯수 찾기 from itertools import product def solution(relation): answer = 0 relations = [1, 0] uniques = [] # 유일성 만족하는 값 찾기 for case in product(relations, repeat=len(relation[0])): case = list(case) tuples = set() fo..
[Programmers] 전력망을 둘로 나누기 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 from collections import deque def bfs(start, visited, connected): queue = deque() queue.append(start) visited[0] = True cnt = 1 while queue: node = queue.popleft() for w in connected[node]: if not visited[w]: visited[w] ..
[Programmers] 이중우선순위큐 https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 from heapq import heapify, heappop, heappush def solution(operations): answer = [] queue = [] heapify(queue) for operation in operations: left, right = operation.split(" ") if left == 'I': # 큐에 주어진 숫자 삽입 heappush(queue, ..
[Programmers] https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr https://school.programmers.co.kr/learn/courses/..
[Programmers] SQL 문제들 https://school.programmers.co.kr/learn/courses/30/lessons/164670 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr코드# 중고 거래 게시물을 3건 이상 등록한 사용자# 회원 ID 기준으로 내림차순 정렬SELECT USER_ID, NICKNAME, CONCAT(CITY, ' ', STREET_ADDRESS1, ' ', STREET_ADDRESS2) AS 전체주소, CONCAT(LEFT(TLNO, 3), '-', MID(TLNO, 4, 4), '-', RIGHT(TLNO, 4)) AS 전화번호FROM U..