목록알고리즘 (129)

이숭간 공부기록

[백준] 14500번 파이썬 _ 테트로미노

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제유형 : 구현, 완탐 (dfs) 문제풀이 : 문제의 키포인트 ㅗ모양은 그냥 일반적으로 count가 4가되면 리턴하는 dfs로는 해결할 수 없음. 따로 처리를 해줘야함 나는 외부에서 따로 처리를 했는데 dfs수행에서 블록개수가 2인 시점에서 다시 자기자신을 시작점으로하는 dfs를 호출하면 된다.. (다른분 풀이 아래참고) dfs를 수행할때 겹치는 모양이 계속해서 나오게되는데 이것을 어떻게 조기종..
알고리즘/백준 2021. 8. 12. 03:04
[백준] 11657번 파이썬 _ 타임머신

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제유형 : 벨만포드 문제풀이 : 음수간선이 존재하는 최단경로를 구하는 문제 벨만포드 알고리즘 그대로 구현하는 문제 벨만포드 알고리즘 설명 - https://esoongan.tistory.com/185?category=915633 정답코드 : # 노드개수, 간선개수 n,m = map(int, input().split()) # 간선정보를 ..
알고리즘/백준 2021. 8. 11. 23:43
[알고리즘] 벨만-포드 알고리즘

벨만포드 알고리즘 최단경로라는것은 같은정점을 두번 지날일이 없기때문에 최단 경로의 간선개수는 최대 V-1개이다. 따라서 루프를 V-1번 (V는 노드의수) 돌리는데(최악의 경우까지 모두 커버가 가능), k번째 루프에서는 시작점으로부터 각 정점으로 k개의 간선을 거쳐서 도달할 수 있는 최단경로를 다 갱신해주자는 게 기본 아이디어 ( 이렇기 때문에 음의순환을 찾을때 한번더 수행하는것 ) 음수간선이 포함된 상황에서 최단거리 찾기 모든간선이 양수일때는 다익스트라를 사용하면 된다. 음수 간선의 순환이 발생하는 경우, 최단거리가 음의 무한인 노드가 발생한다. (계속해서 줄일수있으니까 무한대로 순환) 간선에 관하여 최단 경로문제는 다음과 같이 분류된다. 모든 간선이 양수인 경우 ( 다익스트라, 플로이드 와샬) 음수 간..
알고리즘/알고리즘 기초공부 2021. 8. 11. 23:22
[프로그래머스] SQL고득점킷 _ GROUP BY

1. -- 코드를 입력하세요 SELECT ANIMAL_TYPE, COUNT(*) AS count FROM ANIMAL_INS GROUP BY ANIMAL_TYPE ORDER BY ANIMAL_TYPE ASC; 2. -- 코드를 입력하세요 SELECT NAME, COUNT(*) AS COUNT FROM ANIMAL_INS GROUP BY NAME HAVING COUNT(*) >= 2 AND NAME IS NOT NULL ORDER BY NAME; 3. -- 코드를 입력하세요 SELECT HOUR(DATETIME) AS HOUR, COUNT(*) AS COUNT FROM ANIMAL_OUTS GROUP BY HOUR HAVING HOUR >= 9 AND HOUR
알고리즘/프로그래머스 2021. 8. 11. 18:37
[프로그래머스] SQL고득점킷 _ SUM, MAX, MIN

1. -- 코드를 입력하세요 SELECT DATETIME FROM ANIMAL_INS ORDER BY DATETIME DESC LIMIT 1 2. -- 코드를 입력하세요 SELECT DATETIME FROM ANIMAL_INS ORDER BY DATETIME ASC LIMIT 1 3. -- 코드를 입력하세요 SELECT COUNT(*) FROM ANIMAL_INS 4. SELECT COUNT(DISTINCT NAME) FROM ANIMAL_INS WHERE NAME IS NOT NULL -- 코드를 입력하세요 SELECT COUNT(p.name) FROM (SELECT DISTINCT NAME FROM ANIMAL_INS) p
알고리즘/프로그래머스 2021. 8. 10. 17:04
[프로그래머스] 파이썬 _ 디스크컨트롤러

https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제유형 : 최소힙 문제풀이 : SJF (Shortest Job First) 방식이다. 현재 시점에 수행가능한 job을 걸러낸다. 걸러낸 job중 가장짧은 수행시간을 갖는 job부터 수행한다. 현재시간갱신하기 ( 현재시간 += 현재작업의 수행시간 ) 총 걸린시간 갱신하기 ( 총걸린시간 += 현재시간 - 현재작업의 도착시간 ) 현재 시점에 수행가능한 job이..
알고리즘/프로그래머스 2021. 8. 10. 16:48
이전 Prev 1 2 3 4 5 6 ··· 22 Next 다음