profile
42Seoul / 알고리즘 공부 중

2156 - DP

2579 계단오르기와 다르게, 0이 있으므로해서0을 취하는 경우 바로뒤에 큰 수가 오는 경우 이를 취하지 못한다.그렇다고 0을 입력받은 것에서 지우는 것은 안된다. 0이 있기 때문에 0바로 전의 max에서 0후의 값을 취할 수 있도록 되어 있기 때문.ㄴ> 따라서 미

2022년 7월 6일
·
0개의 댓글
·
post-thumbnail

그래프2 - 플로이드

플로이드 알고리즘모든 정점 쌍 사이의 최단거리를 구해주는 알고리즘(방향 / 무방향 상관없음)1번 노드를 반드시 거치는 것과 현재 테이블의 값과 비교 후 비용의 총합이 더 작은 것을 갱신2\. 1번 을 노드의 수만큼 반복

2022년 6월 29일
·
0개의 댓글
·
post-thumbnail

그래프

그래프의 표현 방식에는 2가지가 있다.인접행렬 방식인접 리스트 방식인접 행렬 방식의 경우두 정점 사이의 연결을 살필때 : O(1) 정점을 V개라한다면 모두 흝어도 O(V)공간은 V\*\*2만큼 필요함.받는 방식

2022년 6월 27일
·
0개의 댓글
·

13414 - 해시

해시가 스택이나 배열처럼 맨 뒤에 쌓이는 점은 이용하였다.삭제 연산이나 삽입 또한 O(1)이라 효율적일 것이라 판단하였음

2022년 5월 6일
·
0개의 댓글
·

프로그래머스 - 보석 쇼핑

보석 최대 갯수 중복없이 체크 일반적으로 하면 n^2이라 풀 수 없음처음에 DP를 생각함. 선이 계속 중복으로 그어지기 때문.정석풀이는 투포인터라고들 하는데 불현듯 해시가 떠올랐다.연결된 것을 따지는 거기 때문에 배열보다는 리스트 계열과 유사한 성질을 가질것으로 판단중

2022년 5월 4일
·
0개의 댓글
·

9663 - DFS

파이썬이 느려서 대각선 체크까지 구현해야함같은 대각선에 위치한 y,x가 같은 인덱스를 가지게 하려면 약간의 테크닉이 필요한데,기울기가 1인 대각선은usedy+x로 놓으면 같은 대각선을 공유한다.기울기가 -1인 대각선은used2n-1+y-x로 놓으면 동일 대각선을 공유하

2022년 5월 2일
·
0개의 댓글
·

6198 - Stack

처음에 DP 생각했으나 아무리해도 n^2이라 스택으로 생각을 바꾸었음스택에 있는 값을 뺄 때, 그 값이 바라보는 것의 갯수로 생각하면 이것도 n^2발상 전환 필요했음스택의 값을 뺄 때, top 이 바라보는 것의 갯수가 아닌, top을 바라보는 건물들의 갯수 == sta

2022년 5월 2일
·
0개의 댓글
·

11559 - BFS, 시뮬

최초에는 deep copy를 사용했다.BFS는 기본적으로 방문체크를 하고 방문했으면 continue를 해야 연산이 O(n)인데,4개이상의 젤리가 만나는지 확인하려면 결국 방문처리로 확인해나가야한다.방문처리로 값을 바꾸면서 나아가다가 4개 미만이면 원본을 유지해야 하기

2022년 4월 14일
·
0개의 댓글
·

11967 - BFS, 시뮬

챌린징 포인트:1\. 큐에 무엇을 담을지 정해야함 >> 방문한 것만 담기2\. 1에 따른 큐에 담을 조건을 설정(how)상태설정0 : 미방문1 : 미방문 && 불은 켠 상태2 : 방문 (불을 켜야만 방문 가능하므로 불도 on)root(1,1과 연결되었는 그룹) 명명.\

2022년 4월 14일
·
0개의 댓글
·

6064 - 수학(GCD, LCM)

챌린징 포인트1\. lcm 단순히 약수에서 중복제거하는 방식으로 구현. N^2 나올 수 밖에 없음x\*y // gcd(x,y)로 처리 가능\*gcd연산은 PS_LIB에 저장해둔것 활용 혹은 gcd 임포트해서 써도 된다.2\. 하나씩 연산하면 16억 가량에대해 계속 ++

2022년 4월 11일
·
0개의 댓글
·

15686 - 시뮬

조합을 먼저 구하고 BFS를 생각함.결과는 시간초과인데, 이유는 find_C에서 일단 시간이 걸리는게deep copy를 사용함. 2500연산에 깊이가 13Ck로 13\*12\*11정도의 깊이로 1700정도로 들어감조합의 수 최대 1700가량 \* 2500BFS >>>

2022년 4월 11일
·
0개의 댓글
·

11000 - (그리디, 우선순위 큐)

초기 접근우선순위 큐 예상은 했으나각각의 범위가 Xn-Yn 일때가장 긴 스케쥴을 잡는 방법인, Yn의 최저에 가장 많이 붙히는 식으로 생각함ㄴ> 다른 알고리즘임초기 접근으로하면 한개의 스케쥴에 대해 DFS처럼 접근하게 되므로 아무리 줄이려고 해도 연산은O(N^2)에 비

2022년 4월 6일
·
0개의 댓글
·

9466 - 그룹찾기 (DFS,Stack)

초기 설계1\. for(x)문에서 케이스 배열을 순환하며 x를 start로 기억해서 이것과 같은 경우만 같은 그룹으로 생각하여 설계2\. n퀸 처럼 판단을 먼저 한 뒤에 값을 변경하고 싶었다.ㄴ> 다만 이렇게 하면 같은 그룹에 속해있는지를 분간할 방법이 없음초기설계에

2022년 4월 6일
·
0개의 댓글
·

2146 - BFS

BFS는 개념적으로 이해할 땐 쉽게 느껴지지만마음먹고 어렵게 내면 어려운 알고리즘이다.범위를 벗어나면 Continue (기본)큐에 넣어야 하는 것들을 명확히 해야한다.종결 조건에 대해 명확해야함. 특히 큐의 시작점이 여러개라면대체로 while(q)문이 다 돌고 나서

2022년 3월 31일
·
0개의 댓글
·

18808 - 시뮬

접근 : 배열을 돌리는 함수, 집어 넣을 수 있는지 확인 후 집어 넣는 함수를 구현해서 조건에 맞게 처리챌린징 : 시간 초과원인 : deepcopy를 너무 함부로 사용했다비어있지 않은 공간이어도 스티커 전체를 기준으로 하면 안겹칠 수 있으니0,0 ~ n,m까지 따지는

2022년 3월 31일
·
0개의 댓글
·

15683 - 시뮬/DFS

import sysimport copyfrom collections import dequen,m = input().split()n=int(n)m=int(m)origin = \[]for \_ in range(n): origin.append(list(map(int,sys.

2022년 3월 29일
·
0개의 댓글
·

7570 - 그리디 & DP

접근 : 현 상태에서 최대한 덜 바꿔야 하기 때문에 그리디만 생각하였음.5 2 4 1 3 이라면 숫자 하나만 차이나는게 뒤에 있는 것의 최대 갯수는 2(2->3)이다.이 것을 유지하면서 다른 값을 바꿔주면 최소가 된다.1\. 건드리지 말아야 할 수의 최솟값인 2보다 작

2022년 3월 28일
·
0개의 댓글
·

13975 - 파일 합치기

처음에는 작은 값이 산개해야 하는 것으로 보였으나,13537 같은 예시를 통해 아닌 것을 알았음더하는게 중복되는 구조가 아니면 되는 것 같아 완전이진트리의 형식으로 생각하다 힙을 생각했고그에 따라 우선순위큐를 생각했다.처음에는 그냥 무지성으로 팝2번씩만 해서 노드의 갯

2022년 3월 24일
·
0개의 댓글
·

PS-수학

소수정의 : 1과 자기자신만을 약수로 가지는 수\*1은 소수가 아니다.소수찾기 > O(n)하지만 소수찾기의 연산을 O(루트n)으로 줄일 수 있다.이유 : 합성수 n에서 1일 제외한 가장 작은 약수는 루트n이하 이다.증명 : 1\. 1을 제외한 가장 작은 약수를 x라고

2022년 2월 28일
·
0개의 댓글
·
post-thumbnail

백준 골드 달성

DP/그리디/D,BFS 유형 랜덤 풀기로BFS 문제 깔끔히 풀어낸 후 골드달성.아직 유형 파악 덜 되고 있음의외로 그리디가 가장 어려움...

2022년 2월 11일
·
0개의 댓글
·