알고리즘

BFS든 DFS든 사용해서 시작점과 연결된 노드 개수 찾기DFS 사용할 예정혼자 했다!

Depth-first search 깊이 우선 탐색풀이 과정 1\. graph, 시작위치 v, visited 를 입력 받음. 2\. visitedv에 방문 표시를 함 3\. graphv 리스트의 항목에 대해 방문한 적 없으면 dfs 재귀적으로 실행백준 24479,

DFS와 BFS 풀이 계획 DFS, BFS 둘 다 구현해서 각자 결과 출력하기

단지번호붙이기전체 배열에 대해 BFS 진행하면서 개수 세기 (DFS, BFS 상관 없어보임)단지 총 개수와, 각 단지 별 세대 수 세야 함.입력 받은 자료 자체를 변경하는 것은 위험하다고 들었음.나중에 필요할 때는 따로 visited 배열을 만들어야 할 듯.

유기농 배추BFS든 DFS든 써서 인접한 배추 무더기 개수 구하기DFS 쓸 것임방문한 곳은 0으로 변경하기sys.setrecursionlimit 해주기!

미로탐색BFS. 큐 사용

숨바꼭질BFS로 풀어야 할 것 같았음.BFS로 풀어야 할 것 같아서 풀다가 아닌가 해서 DFS로 풀다가 진짜 아닌거 같아서 BFS로 풀게 됨횟수 표현하는게 더 좋은 방법이 있을 것 같은데..무작정 BFS 했더니 계속 메모리 초과가 떠서 최대한 계산을 줄이기로 머리를 씀

나이트의 이동BFS숨바꼭질 문제처럼 이미 간 곳은 큐에 포함 안하도록 할 것nameerror가 뜨길래 뭔가했더니 import sys를 자꾸 빼먹음

토마토BFS전체 리스트 순회하며 최외각 토마토만 큐에 저장날짜++ 하며 list의 값 변경days를 while 전에 초기화 안해서 에러가 생김. UnboundLocalError, NameError그리고 days 리턴을 이상한데서 해서 틀림

토마토3차원 BFS입력 주의해서 받기이전 토마토 문제랑 똑같이 풀어야지BFS 모두 한 후에 마지막에 0 있으면 -1 출력하기2차원 토마토 풀 때랑 똑같이 풀었다.자꾸 bfs 구현할 때 큐에 넣어주는 것을 깜박한다...

균형잡힌 세상스택(, 는 각각 , ) 대칭이 맞아야 함.마지막은 .이어야 함

주유소주유소를 보면서 거리를 누적함. 이전 주유소보다 가격이 싸지면, 누적된 거리만큼 이전 주유소 값으로 계산하여 저장, 거리 초기화.

회의실 배정감이 안잡힌다. 다른 사람 풀이에서 힌트 얻음.끝나는 시간에 따라 정렬.정렬된 리스트 순회하며, 시간표에서 가장 나중 회의의 끝나는 시간 이후에 시작하는 회의를 고름!2차원 배열에서 특정 인덱스를 기준으로 sort할 수 있다.meetings.sort(key=

출력시 리스트를 띄어쓰기로 출력하려면 print(\*list)만 해도 됨!큐의 최대 길이를 제한해야해서 deque의 maxlen을 설정해줬다. 이렇게 하면 50점이 나오고, 위 코드처럼 일일히 확인하면 100점이 나온다. 무슨차이지...

동적 계획법은 점화식을 세워야 한다고 합니다.i번째 (i길이)의 가능한 가짓수는 i-1길이 가짓수 + i-2 가짓수x(i) = x(i-1) + x(i-2)i가 짝수면, i-2에서 i로 가는 가능성은 00을 추가하는 방법 밖에 없고, i-1에서 i로 가는 가능성은 1을

i번째 삼각형 한 변의 길이는 i-1, i-5번째 삼각형 변 길이 합이랑 같게 됨.삼각형이 회전하는 모습임. 한 바퀴 돌아서 변이 연결되는 삼각형이랑은 360도 차이가 나게 됨. 정삼각형의 꼭지점 각도는 60도니까, 360 / 6이니 6 step으로 규칙이 발생함.5번

시작점을 둘러싼 원의 개수와 끝점을 둘러싼 원을 세기시작점과 끝점을 모두 둘러싼 원은 세지 않기

구현map_lst를 만듦. 일반은 0, 사과 있으면 1방향을 0, 1, 2, 3으로 두고, dx, dy로 이동 계산뱀 길이는 queue로 처리사과 먹으면 먹은 자리는 0으로 바꾸고, 뱀은 append, popleft 함사과 없으면 이동꼬리가 줄어들기 전에 머리가 이동해

재귀결과에서부터 입력 도출하기끝이 A면 빼고, B면 빼고 좌우 대칭길이가 입력보다 작아지면 false 반환입력과 같아지면 true 반환재귀라 sys.setrecursionlimit(10\*\*8) 해줬다.문자열 슬라이싱 주의하기

이진 탐색으로 공통 원소 찾고, 두 집합 원소 합 - 공통 원소 개수 \* 2파이썬의 set은 차집합 기능이 있음~두 방식 채점 결과의 메모리, 시간 차이위가 set 차집합 사용, 밑이 이진 탐색 구현

이진 탐색다른 사람들 코드 중, set 사용해서 & 연산하는 경우가 있었음.

이진탐색으로 코드를 짜니 시간초과가 나온다.약간 꼼수 쓴 느낌으로.. 딕셔너리를 사용했다.

유클리드 호제법 공부하기x%y 를 r이라고 할 때, x와 y의 최대공약수는 y와 r의 최대공약수와 같음r이 0이 될 때까지 x = y, y = r을 반복. r이 0이면 그 때의 y가 최대공약수최소공배수는 x \* y // r공통 약수는 한 번씩 곱해주고, 공통이 아닌

계획 주어진 수보다 작은 소수를 모두 찾아 리스트에 넣고, 리스트 순회하면서 (주어진 수 - 값)이 리스트에 있는지 확인 에라토스테네스 체 구현해보기

골드바흐 문제를 계속 풀다보니 기존에 문제 풀던 방식 그대로소수를 먼저 찾고 그 다음에 인수 분해를 하게 됐더니 시간 초과가 났다.2부터 주어진 숫자 N까지 차례대로 N을 나눈다. 나눈 나머지가 0이 아닐 때까지 계속 나누고 N은 나눈 몫으로 업데이트 해준다.만일 8의

각 인수마다 최대공약수를 찾아서 답에 계속 곱해주는 방식을 생각함.2, 4 처럼 공통된 인수는 중복으로 반영됨\-> 구한 값으로 해당 인수를 나눠줘야 함.divide 함수는 최대공약수를 구하는 함수.x와 y의 최대공약수는 y와 x%y (x를 y로 나눈 나머지)의 최대

과정 모든 부분 집합을 구하기

계획 주어지는 수를 나눈 나머지 값을 해당 인덱스에 저장한다. 6인 경우, [0, 0, 0, 0, 2, 1, 0] 인수는 먼저 0으로 지정, 뒤에서부터 index 2까지 순회하며 0이 나올 때까지 1씩 추가된 값을 입력 모든 수에 대해서 위 반복 가장 최근 값의

https://www.acmicpc.net/problem/14719힌트 참고했습니다.높이마다 순회너비마다 순회블록의 높이가 너비보다 높거나 같으면, 시작점부터 해당 위치까지 빗물양(위치 차이) 합침. 해당 위치를 시작점으로 업데이트.ex) 높이가 1이고, 블록

브루트포스. 모든 경우를 비교할 것.최대공약수 구하는 함수 만들기.모든 경우를 비교해야 하기에 조합의 가짓수를 계산해야할지 고민했다.최대공약수 구하는 데에는 두 수의 조합만이 필요하므로 이중 반복문으로 해결 가능하다.간단하게 생각하는 연습이 필요할 것 같다.

후위 표기식을 계산하는 문제스택문자와 숫자를 연결하는 딕셔너리 만들기숫자 스택과 기호 스택을 따로 만들기입력받는 문자열을 앞에서부터 순서대로 순회숫자면 숫자 스택에 입력기호면 숫자 스택의 맨 뒤 두 숫자를 연산, 연산 결과를 push소수점 둘째 자리까지 출력f-stri

백트래킹 공부하기1부터 N까지 값을 리스트로 만들어놓음.result라는 빈 리스트에 숫자를 하나씩 추가함.숫자를 추가하는 경우와 숫자를 추가하지 않는 경우를 가지처럼 만들어 나감.함수의 반복문 안에서 추가한 경우와 추가하지 않는 경우가 갈림.

백트래킹N과 M(3) 문제는 수열에서 순서를 고려했지만, 이번 문제는 수열의 순서를 고려하지 않는다.112, 121은 N과 M(3)에선 다른 수열이었지만, N과 M(4)에선 같은 수열이다함수를 재귀로 실행할 때, 현재 인덱스 이후부터 고려하도록 한다.

백트래킹 + 브루트포스백트래킹으로 부분 수열 구하기 (팀 나누기)팀은 두 개로 나뉨0이 있는 모든 팀의 경우를 구하고 해당 팀에 속하지 않는 인원을 한 팀으로 묶는 방식 사용.부분 수열 구하는 연산을 반으로 줄일 수 있음.result 리스트에 0을 기본으로 넣고, 시작

목적 B부터 시작.B가 2로 나누어떨어지면 B = B//2B를 10으로 나누었을때 나머지가 1이면 (마지막 숫자가 1) 맨 뒤 숫자 떼기함수 중지 조건B가 A 보다 작아지면 -1 출력B가 2로 나누어떨어지지 않거나, 10으로 나눈 나머지가 1이 아니면 -1 출력A ==

정사각형의 0, 1, -1 개수 세어보고 하나만 0이 아닌 경우면 종이에 모두 같은 수라고 생각하나만 0이 아닌 경우가 아니면 수가 섞여있음. 9등분해서 0, 1, -1 개수 세어봄Python 3으로는 시간초과가 발생하고, PyPy3으로는 통과되지만, 메모리가 많이 필

다이나믹 프로그래밍문제를 수행하며 중간 값을 계속 업데이트하며 풀어나가는 방식앞 줄과 색이 겹치지만 않도록 색을 칠하기각 집의 숫자를 (위 줄에서 가능한 최소값 + 집의 숫자) 로 업데이트위 줄에서 발생하는 최소 값만을 반영하여 값을 계속 업데이트 한다.동적 계획법은

공기청정기 위치 파악하기미세먼지 확산 시키기사방으로 퍼뜨림퍼진 미세먼지를 해당 위치의 기존 미세먼지에 합하는 방식으로 진행했더니, 퍼진 미세먼지를 중복으로 퍼뜨리는 경우가 생김빈 리스트를 만들어서 퍼진 미세먼지만 저장, 이후에 기존 리스트에 값을 더하는 방식으로 진행.

재귀로 피보나치를 구하는 코드가 있어서 그대로 실행했더니 시간초과가 나온다.동적 프로그래밍을 연습한다.40까지 모든 피보나치 연산을 한다. 각 과정의 연산값은 리스트에 저장하고, 다음 연산에서 사용한다.0, 1을 호출하는 횟수이므로 초기화를 주의해서 한다.dp_0 =

전체 모든 값을 넣을 스택과, 레이저를 제외하고 쇠막대기 개수를 넣을 변수를 만듦입력을 받을 때, 입력 받을 값과 스택의 마지막 값을 비교입력이 ( 이면 스택에 추가하고 쇠막대기 개수에 +1입력이 ) 이면레이저의 끝인 경우 ( 스택 마지막 값이 (임 ) 현재 쇠막대기

비슷한 문제: 17298 오큰수스택 사용하기입력 받은 리스트를 처음부터 순서대로 스택에 추가스택의 마지막에 있는 것보다 새로 들어올 값이 크면, 스택에서 큰 값이 나올 때까지 pop ( 스택의 길이는 1보다 크도록 유지 )스택의 마지막에 있는 것보다 새로 들어올 값이

R, G, B를 구분해서 영역 개수 구하기 & RG, B를 구분해서 영역 개수 구하기BFS로 풀 것이다.정상인이 보는 답을 계산한 후, 2차원 리스트에서 G를 모두 R로 바꾼 후 적록색맹이 보는 답을 계산한다.정상인 계산 후, 적록색맹 계산하기 전, visited 리스

다이나믹 프로그래밍n은 11보다 작은 수가 들어온다고 하니 10까지 값을 전부 계산한다.점화식 세우기i번째 값은 i-1, i-2, i-3 을 더한 값과 같음.

도감 번호로 들어오면 포켓몬 이름을, 포켓몬 이름이 들어오면 도감 번호를 출력해야 한다.도감 번호가 인덱스인 리스트를 만들고, 포켓몬 이름의 첫 글자가 key 인 딕셔너리를 만들었다.python 시간 초과, pypy 시간 초과는 아니지만 메모리와 시간이 많이 들음도감

heapq와 PriorityQueue를 사용하여 해결할 수 있다.queue 라이브러리의 PriorityQueue를 사용했다.maxsize를 설정하면 최대 크기가 설정된다.우선순위 큐는 qsize(길이), put(추가), get(값 반환)의 기능이 있다.put을 통해 넣

2차원 배열에서 K개의 직사각형 영역을 visited 처리하기bfs로 영역의 개수와 각 영역의 너비 구하기

2xn 타일링 문제와 다르게, 2x2 타일이 추가되었다.다이나믹 프로그래밍점화식 세우기dpi = dpi-1 + 2 \* dpi-2추가되는 타일은 왼쪽에 붙는다고 생각해보면, dpi-1에서 1 길어지는 경우 (빨강), dpi-2에서 2 길어지는 경우 (파랑)을 고려하면

구현6과 9는 공통으로 쓸 수 있다는 점에 주의.1부터 9까지 최대로 나타나는 수 만큼 세트가 필요.

연속된 수를 합쳐서 목표로 하는 수를 만들기하나씩 더해나가면서 값이 목표 값보다 크면 맨 앞에 수를 빼고, 작으면 추가로 더하기start 위치와 end 위치를 지정했습니다. (start 부터 end 사이에 있는 수를 더하는 방식)end 값을 +1 하고, 인덱스 범위를

위에 있는 왼쪽, 오른쪽 수 중 큰 수를 밑에 더해가면서 리스트를 업데이트 한다.맨 앞의 항목은 오른쪽의 값만, 맨 뒤의 항목은 왼쪽의 값만 더해나간다.

dp대각선, 한칸 이전 대각선 중 큰 값을 더해 나가는 방식원래 dp문제는 1인 경우 예외처리를 하고 exit() 을 사용했었다.하지만 이번 문제에서는 계속 에러가 발생했다. 테스트케이스 여러 번을 돌려야 했기 때문이었다. ㅜㅜ예외 처리를 따로 해주지 않고, 반복문 안

원을 일정 간격으로 돌리면서 사람을 하나씩 빼야한다.큐를 사용해서 일정 간격만큼 pop, append를 진행하고, pop을 해주는 방식으로 진행한다.큐의 길이가 0이 되면 반복을 중단한다.출력에 주의하기

스택에 인덱스를 저장하기리스트 전체를 순회하며 스택 마지막 값이 크면 그냥 추가, 스택 마지막 값이 작으면 큰 값이 나올 때까지 뺀 후, 추가.맨 앞자리부터 하나씩 수를 구하기리스트 구간을 바꿔가며 해당 구간에서 스택을 만들고, 가능한 수를 앞부터 하나씩 구해간다.시간

deque에서 popleft, pop을 사용하기R의 개수를 센다.D가 들어오면 R % 2가 0이면 popleft를, 1이면 pop을 시행한다.deque 길이가 0이면 error를 출력한다.출력시 R % 2가 0이면 그냥 출력, 1이면 거꾸로 출력한다.deque가 비어있

최대공약수 구하는 방법x, y의 공약수는 y 와 x%y 의 공약수임.x = y, y = x, r = x%y 를 반복해서 최소의 공약수 찾기.최소공배수 구하는 방법x \* y를 최대공약수로 나누기.모든 약수 구하기int( 숫자 \*\* 0.5 ) 까지 1부터 모든 수로

콤비네이션 연산 하기문제를 잘 읽지 않고 순열 구하는건 줄 알았다.. 문제 잘 읽기

수열로 사용할 로프 구하기.. 전체 더하고 제일 작은 로프로 나누기... 등 해보았다.다른 사람의 풀이를 참고했다.최대 하중은 최소 로프 값 \* 사용하는 로프 개수 이다.알고보면 매우 단순한 원리인데, 생각하지 못하면 계속 생각 못할 것 같다.풀이 능력을 키우고, 정

DP. 비슷한 문제: 2156 포도주 시식현재 위치를 밟은 경우의 최대값을 DP에 저장하기i번째를 밟는다고 했을 때 가능한 경우는 i-2, i를 밟기, i-3, i-1, i를 밟기dpi-2 + lsti, dpi-3 + lsti-1 + lsti 중 최대값 저장영향을 받는

DP. 비슷한 문제: 2579 계단 오르기연속으로 3잔을 마시지 않는 조건에서 최대한 많이 마시기현재 위치까지 따져보았을 때 최대값을 DP에 저장하기.i 위치라고 했을 때 가능한 경우는i를 먹고, i-1를 먹고, i-3까지의 최댓값 더하기i를 먹고, i-2까지의 최댓값

DP. 초기 4 단계까지 구해보면1 - 10 - 100, 101 - 1000, 1001, 1010 - 10000, 10001, 10010, 10100, 10101이친수는 10으로 시작해야한다.길이가 i인 이친수는 3째자리부터 마지막자리까지 값을 i-1과 i-2에서 구할

https://ssinee.tistory.com/entry/%EB%B0%B1%EC%A4%80-10844%EB%B2%88-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8-%EC%88%98-CDP 이 블로그 글을 참고하였다.2차원 DP 문제.행

잘 이해되지 않으면 10844 쉬운 계단 수 를 먼저 이해하고 오자.2차원 DP. 행 인덱스를 숫자 길이, 열 인덱스를 끝나는 수로 생각하자.i 길이이고, j로 끝나는 수 중 오르막 수의 개수는 i-1 길이이고, j보다 작거나 같은 수로 끝나는 수의 개수이다.

정수 N 길이의 리스트를 만듦.각 인덱스에 해당하는 값이 1이 될 때까지 몇 번의 연산을 거치는지를 저장.i를 6, 3, 2로 나누어 떨어지는 경우와 그렇지 않은 경우로 나눔.6으로 나누어 떨어지는 수는 i//2, i//3, i-1 의 위치에 있는 값 중 최소값에 +1

1차원 그래프의 DFS 사용했습니다.왕복하는 항목이 있을 수 있으므로, U, V 양 쪽에 대해 간선을 고려해줬습니다.재귀적으로 DFS를 진행했습니다.다음은 처음 짠 코드입니다.다른 사람의 코드를 보고 수정한 코드입니다.재귀적으로 DFS를 실행할 때, DFS를 실행한 후

1차원 DFS를 사용했습니다.리스트로 입력 받아서, 인덱스에 맞게 그래프로 옮기는 작업을 했습니다. 이 때 인풋은 1부터 시작하지만, 인덱스는 0부터 시작한다는 점에 주의해서 입력 받습니다.

피보나치 수를 DP로 구해본다.점화식도 알고 있으니 쉽게 구할 수 있다!

행과 열에 맞게 1로 가득 찬 2차원 배열을 만든다.꼭 지나야하는 값의 좌표를 구한다. 열의 수로 나눈 값의 몫과 나머지가 y, x 좌표가 된다.2차원 dp로 해당 위치까지 가능한 이동 경로 수를 더해나간다.위 칸의 값과 왼쪽 칸의 값을 합한 값이다.1 1 1답: 15

모든 2차원 배열의 값에 대해 0,0 부터 해당 위치까지 모든 수를 구한 값을 dp에 넣는다.합을 구하려는 우측하단 위치의 값에서 좌측상단 위치의 값을 뺀다.(x2,y2) - (x1,y2) - (x2,y1) + (x1,y1)이 때에 인덱스 값에 주의한다.제외하려는 사각

두 분수의 합을 기약분수 형태로 나타내기첫 번째 분수의 분자, 분모를 a1, b1, 두 번째 분수의 분자, 분모를 a2, b2라고 할 때, 분수 합의 분자는 a1 b2 + a2 b1, 분모는 b1 \* b2이다.기약분수 형태로 나타내라고 하였으니 분자와 분모의 최대

스택을 두 개 만든다.하나의 스택에는 커서 기준 앞의 내용을 담고, 다른 스택에는 커서 기준 뒤의 내용을 담는다.출력 시, 커서 뒤의 내용을 앞에 더해서 출력한다.입력 속도 향상을 위해 sys.stdin.readline을 사용한다.

덱에서 찾으려는 값의 인덱스를 구한다.해당 인덱스를 전체 길이 // 2와 비교해서 앞에 있으면 앞으로 돌리고, 뒤에 있으면 뒤로 돌린다.맨 앞에 찾으려는 값이 있으면 멈추고 popleft큐를 돌린만큼을 계속 계산해서 다음 들어올 수가 어느 위치에 있을지 계산하는 방식을

1부터 해당 수까지 계속 더해나간다.더한 값이 해당 수면, 그 때까지 더한 수 개수를 출력더한 값보다 커지면, 그 때까지 더한 수 개수 -1 을 출력만일 13이 N으로 주어진다면, 1, 2, 3, 4 까지 더하고, 5를 더하는 순간 15가 되어 13보다 커진다. 이러한

과정 재귀함수 사용하기 반복하는 조건과, 반복하는 부분, 끝마치는 부분을 잘 분기해서 구현하기.

정렬하려는 기준에 맞게 리스트에 추가해서 sort로 정렬했다.sys.stdin.readline 사용한 것과 사용하지 않은 것의 시간차sort를 사용하지 않고 정렬하는 방법을 공부해야겠다.

재귀 사용하기4등분 한 종이에서 색이 전부 같지 않으면, 다시 4등분해서 색을 확인한다.색이 전부 같으면 색깔 추가해준다.개수만 확인하면 되니 전역 변수에 카운트 하고 return을 따로 주지 않았다.

색종이 만들기와 비슷한 재귀 문제색이 같으면 출력, 다르면 4등분하기괄호와 같이 출력해야하므로 출력 형식에 주의하기.https://tmdrl5779.tistory.com/102참고해서 풀었습니다.

https://cotak.tistory.com/38 참고길이를 함수에 매개변수로 넣음길이로 1을 입력받으면 "\*" 리턴그 외에는 길이//3 를 재귀로 받고,재귀로 받은 배열에 대해서3번 반복 입력입력, 띄고, 입력3번 반복 입력을 리스트에 추가

골을 넣은 팀과 골이 들어간 시간이 입력으로 주어진다.전체 경기 시간 중, 각 팀이 이기고 있던 시간을 출력한다.입력이 들어오면, 그 순간의 점수를 확인한다.그 때까지 걸린 시간을 이기고 있는 팀에 추가현재 시각 - 시작 시간을 더함시작 시간 초기화시각은 초 단위로 계

과정 https://velog.io/@younghoondoodoom/%EB%B0%B1%EC%A4%80-11729-%ED%95%98%EB%85%B8%EC%9D%B4-%ED%83%91-%EC%9D%B4%EB%8F%99-%EC%88%9C%EC%84%9C 참고했습니다. 1번

문제를 잘 읽기꼭지점에 쓰여있는 수가 가장 큰정사각형을 찾고해당 정사각형의 너비 반환하기문제를 대충 읽어서 고생했다..

입력 받은 문자열을 처음부터 순회한다.X가 들어오는 경우X 개수를 추가한다.. 개수가 0보다 크면. 개수만큼 답에 .를 추가한다.. 개수를 0으로 초기화 한다..가 들어오는 경우. 개수를 추가한다.X 개수가 0보다 크면X 개수만큼 처리한다.X 개수를 0으로 초기화한다.

백트래킹 사용입력 받은 수를 큰 수부터 정렬하고각 자리 수를 한 번씩 사용해서입력 받은 수보다 큰 경우의 숫자를 저장큰 수부터 정렬했기 때문에 가장 마지막에 나온 수는 입력 받은 수보다 큰 수 중 가장 작은 수다.

입력 받은 수를 정렬해서 딕셔너리에 인덱스 값을 저장하고다시 입력 받은 배열을 순회하며 딕셔너리를 참고하여 위치 값을 출력한다.원래 딕셔너리에 있는지 확인해서 없으면 인덱스를 넣고, 있으면 출력하는 방식으로 했는데, 이는 있는지 확인하는 과정에서 의미없는 순회를 하고

백트래킹모음의 개수와 자음의 개수를 따로 세면서 재귀를 돌린다.자음과 모음 개수를 더한 후, 백트래킹을 하기 전에 다시 빼주지 않아서 자주 틀렸었다.기존 백트래킹을 사용할 때는 지금 코드의 level + 1 처럼 변수로 남기지 않아서 맞았던 것이었다.

sort를 사용했는데, 메모리 초과가 발생했다.입력 값을 보면, 수의 개수는 1 ~ 10,000,000 개가 들어오는데, 수의 크기는 10,000보다 작거나 같은 수라고 한다.이 말은 중복이 최소 1,000 번 발생한다는 것이다.차라리 수의 크기 크기의 배열을 만들고,

문제를 잘 읽자!정수가 주어진다고 하니 음수, 0 이 들어올 가능성을 생각해야 한다.리스트를 두 개 만들어서 음수와 0, 양수를 개수를 각각 저장했다.

주어진 수도코드를 그대로 작성하면 되는 문제였다.재귀 사이에 dp를 넣는 느낌참고https://jainn.tistory.com/82

백트래킹을 통해 기호들로 만들어진 배열을 만든다.순서와 반복 여부는 따지지 않는다.전체 배열을 만든 후에 값을 계산한다.인덱스에 주의해서 계산한다.인 경우는 그냥 값을 더하고, - 인 경우는 그냥 값을 빼면 된다.띄어쓰기가 들어온 경우가 힘들었다.이전의 기호가 + 면,

1\. 빙산이 녹음 (단순 구현) \- 기존 2차원 배열에 반영하면, 옆 칸 결과에 영향 받을 수 있으므로 새로운 2차원 배열을 만들어서 녹은 결과를 저장.2\. 그 때 빙산 덩어리 개수 구함 (BFS 또는 DFS) \- 빙산 덩어리 개수가 2 이상이 되면

불 켜는 곳 딕셔너리로 입력 받기bfs 로 가능한 곳 전부 순회하기불켜진 곳과 방문한 곳 2차원 리스트를 따로 만들기딕셔너리에서 찾아서 불을 켤 때, 불 켜지는 곳 사방 중 방문한 곳을 재검하기 위해 queue에 넣는다.현재 위치에서 사방을 보며 불 켜지고 방문 안한

BFS모든 컴퓨터에 대해서 bfs로 해킹할 수 있는 모든 컴퓨터 수를 구하기.구한 수는 배열에 저장했다.일반적인 bfs 문제였지만, 시간초과를 해결하기가 쉽지 않았다. 좀 오래걸리는 문제.Pypy로는 정답이 뜨지만, Python 으로는 시간초과가 난다는 듯 하다.

누적 합 문제다.2차원 배열을 입력 받고, 0,0 위치부터 해당 위치까지의 합을 저장해놓는다.우측 하단까지의 합 - 좌측 상단까지의 합이 두 위치 사이 값의 합이 된다.

입력 받은 값의 길이가 8인지, 8이하인지를 확인8이면 각 항목에 대해 길이가 4가 되도록 앞에 0을 붙임8이 아니면, 생략된 부분에 빈 문자열을 삽입하고, 각 항목에 대해 길이가 4가 되도록 앞에 0을 붙임

빗물의 높이 별로 안전 영역의 개수를 구하기bfs로 안전 영역 덩어리를 구했다.안전 영역의 개수 최대인 경우를 저장해서 출력하기.빗물의 높이는 최대 100이다 -> 입력 잘 확인하기bfs에서 queue에 append를 x, y 해줘서 한참 헤매고 있었다. 익숙하다고 방

과정 dp문제 입력받은 배열을 순회하면서 현재 위치까지 가능한 경우의 수를 dp에 저장하기 예외, 반례를 많이 생각해야하는 문제 암호가 되지 않는 경우는 0을 출력해야한다. 한 자리 암호가 있을 수 있고, 10~26은 두 자리 암호가 될 수 있다.

구간합 구하는 문제.배열을 순회하면서 처음부터 해당 위치까지 더한 값을 저장구간 입력이 들어오면, 뒤에 있는 수 - 앞에 있는 수를 하면 된다.시간 초과 해결하기 위해서 sys 모듈을 import 해왔다.

백트래킹을 사용해서 감소하는 수를 만든다.수의 길이가 1인 경우는 따로 예외 처리를 했다.N 번째 감소하는 수가 나올 때까지 백트래킹을 시행하고, 값이 나오지 않는 경우는 -1을 출력한다.자리마다 최소 1씩 감소해야하기 때문에 감소하는 수 중 제일 큰 수는 987654

사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것.진입차수 Indegree : 특정한 노드로 들어오는 간선의 개수진출차수 Outdegree : 특정한 노드에서 나가는 간선의 개수큐 이용진입차수가 0인 모든 노드를 큐에 넣음큐가 빌

위상정렬https://velog.io/@minyule/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC반드시 a 뒤쪽에 b가 위치해야 한다.a, b 의 관계를 그래프로 입력받고, 배열에 진입차수를 추가해나간다.큐에 진입차수가 0인 값을 모두 추

단순 구현세로와 가로에서 . 이 연속으로 있는 구간을 찾기세로, 가로에 대해 2중 반복문을 돌리면서, . 이 2개 이상 붙어있으면 cnt를 추가하는 방식으로 했다.반복되는 코드를 함수로 만들면 좋을 것 같다고 생각.

BFS, 구현같은 색 확인 할 BFS 함수터지면 밑으로 내려올 함수내려온 상태에서 더 이상 터지지 않으면 횟수 세지 않기반례 - 답은 2....Y.....R.....Y.....R.....R.....Y.....Y.....Y.....RR...YRR..GGYY..GGYY

0, 0 에 말이 놓여 있음지금까지 지난 알파벳이 아니어야 이동할 수 있음최대 몇 칸을 지날 수 있는지DFS를 사용하고자 했다.지나간 알파벳을 기억해야하서 백트래킹을 사용했다.최대 길이를 구해야했기에 전역 변수를 사용했다.원래 지난 알파벳을 기억하는 용도로 딕셔너리를

N개의 36진법 문자를 입력받음K개의 특정 문자를 Z로 바꿨을 때, 입력 받은 모든 숫자의 합으로 최대가 될 수 있는 값을 36진수의 수로 출력0부터 Z까지 값을 저장할 리스트를 만듦단어를 입력 받으며, 각 문자마다 Z로 변환했을 때, 생길 이익을 리스트에 저장동시에

하나의 시작점에서 여러 도착점까지 최단거리를 찾기초기화graph에 (노드, 거리) 형식으로 연결 정보 저장distance에 각 노드까지 최소 거리 저장 (리스트)다익스트라heapq 사용초기화시작점을 q에 heapq.heappush로 넣음heapq.heappush(q,

다익스트라한 점에서 다른 곳으로 가는 최단 거리를 구하기

다익스트라1 - v1 - v2 - N 또는 1 - v2 - v1 - N 의 순서로 이동하는 최단 경로 중, 작은 수를 출력한다.다익스트라를 구현해서, 1부터 시작하는 최단거리, v1 또는 v2에서 시작하는 최단 거리, N에서 시작하는 최단 거리를 구하고, 조건에 부합하

다익스트라집 -> 파티장, 파티장 -> 집 의 거리를 최단 거리를 학생 별로 구하고, 그 중 최대를 출력한다.단방향으로 주어지는 점에 주의한다.다익스트라를 구현하고, 파티장에서 집까지 거리 + 각 학생이 파티장에 오는 거리 의 최단 거리를 구한다.ans과 비교해서 크면

BFS, 다익스트라부수는 벽의 개수를 최소화해서 도착하는 경우를 출력한다.0-1 BFS도 사용가능하다 (가중치가 0, 1뿐이므로)다익스트라 풀이BFS 풀이BFS와 다익스트라의 차이에 대해 생각했다.기존에 BFS문제에서 deque를 사용할 때, 일반적으로 좌표 또는 인덱

다익스트라가중치가 최소가 되도록 도착지에 도달해야한다.

다익스트라 또는 BFS최단시간으로 가는 경우를 찾기

플로이드 워셜경로가 존재하면 1로, 그렇지 않으면 0으로 놓기

플로이드 워셜결과 그래프를 그대로 출력한다.경로가 여러 개가 있을 수 있다.경로가 없는 경우 0을 출력한다.

다익스트라간선 정보를 입력 graph에 반영heapq 를 사용해서, 비용이 제일 작은 것부터 확인해당 위치에서 이어진 곳으로 가는 데 비용 확인하고, 기존보다 적으면 갱신

다익스트라단방향이고, b에서 a로 향하는 것에 주의한다.같은 의존성이 여러 번 입력으로 들어오는지, 그렇지 않은지도 생각하기.

모든 음식 조합에 대해서 신맛과 쓴맛의 차를 구해봐야한다.N개의 요리가 있으면, 재료 1개, 2개, 3개, ... N개로 이루어진 수열을 먼저 구해야한다.재료는 중복되면 안됨재료에 순서는 필요 없음구한 조합에 대해서 신맛과 쓴맛의 차를 구한다

DP메모리가 4MB로 제한되어 있다.모든 경우를 포함하여 2차원 배열을 만들면 메모리 초과가 발생한다.리스트 크기를 최소한으로 제한해야 했다.따라서 현재 값만을 가지고 있는 리스트만을 사용해서, 각 칸마다 최대값, 최소값으로 변경하는 방식으로 진행했다.메모리 초과가 발

1차원 배열을 만든다. 인덱스는 서류 심사 순위를 나타내도록 한다.서류 심사 순위에 대해 자동으로 정렬이 된 상태이다.배열은 무조건 작아지는 경우만 세어 나가야한다.배열을 순회하며 현재까지 나타난 최솟값을 저장해준다. 저장한 최솟값보다 더 작은 값이 나오면, 최솟값은

숫자 카드를 비교하고, 비교한 숫자 카드는 합친다.모든 숫자 카드에 대해 위 과정을 반복한다고 하면, 숫자 카드를 비교한 횟수의 최소값을 구한다.그리디 : 남은 숫자 카드 중 가장 작은 두 카드를 비교하고 합쳐야한다.카드를 비교할 때마다 비교한 카드 수는 답에 더해지게

N개의 알파벳 대문자로 이루어진 단어 수학 문제각 알파벳을 0~9 숫자 중 하나로 바꿔서 N개의 수를 합하기합한 수가 최대인 경우, 합을 출력하기단어를 입력 받으며, 알파벳의 가중치를 배열에 더하며 저장한다.AB면, A는 10의 자리에 있으므로 가중치는 10, B는 1

S:시작점, G,H:지나간 곳, X:목적지후보S에서 X로 가는데, 최단 거리로 가는 중 G,H를 지나게 될 때의 X는 가능한 목적지가 된다.S-G-H-X, S-H-G-X 순서 중 최소인 거리가 S-X의 최단 거리보다 크면, 불가능한 목적지이다.

백트래킹연산자들 순서대로 배열을 만들고, 최대값, 최소값 계산하고 업데이트비효율적인 코드 같다.좋은 풀이 같아요

다솜이가 사람들을 매수해서, 다른 국회의원의 표 수보다 크게 만들기사람을 매수하면, 해당 국회의원의 표 수는 -1이 되고, 다솜이의 표 수 는 +1이 된다.다솜이의 표 수가 다른 국회의원 표 수보다 크면, 그렇게 되기까지 매수한 사람 수를 구하기우선순위 큐 사용최대값을

투포인터시작점을 0, 끝점을 마지막으로 해서두 수를 더한 값이 X와 같으면 세고,X보다 작으면 시작점 +1X보다 크면 끝점 -1을 한다.

브루트포스뒤에서부터 세는 방식각 숫자를 1씩 빼면서 카운트0이 되면 나타낼 수 있는 최대값으로 변경

Python3깉은 복사 얕은 복사 생각하기 귀찮고, 그냥 처음부터 Kx, Ky, Sx, Sy로 변수를 나눠서 생각할 걸 그랬다.원래는 좌표를 (1, 2) 꼴로 받아서 처리하려했는데 얕은복사 때문에 잘 안됐었다.시간 낭비만 함...