알고리즘

내가 작성한 코드이다. 개인 테스트할 때에는 정상적으로 돌아갔는데 제출해보니 메모리 초과가 떳다. 아마도 예외처리를 안해주고 모든 경우를 돌린다음 답을 도출해서 그럴 것이라고 생각이 된다. 참고한 블로그의 코드이다. 대체적으로 코드가 비슷하지만 재귀함수에서을 통해 반복

정답코드

1부터 차례로 경우의 수를 적어보니 si는 si-2 + si-1이라는 결과를 얻을 수 있었다. 왜 이런 결과를 얻을 수 있었을까?이친수는 맨 앞의 자리 숫자는 무조건 1이 되어야하고 1이 연속되지 않아야하기 때문에 맨 앞자리 수 1은 고정이고 뒤에 '0'이 붙는 경우와

간단한 알고리즘이었다. 전형적인 DP알고리즘이고 피보나치 수열과 같았다. 하지만 주의할 점은 결과 값에만 15746을 나눠주는 것이 아니라 각 배열의 값마다 나눠줘야지 메모리 초과가 발생이 되지 않는다.

백준 2193번이랑 동일한 문제이다.

풀지는 못했고 정답코드를 보고 이해가 되었다.예를들어서 dp0의 값이 최대가 되려면dp1나 dp1의 값이 최대가 되어야 한다. index 0 1 2 3 40 50 10 + 30 = 40 max(100, 30) + 100 = 200 max(120, 100) + 20 =

https://pacific-ocean.tistory.com/151 각 자리수에서 맨 뒤에 올수 있는 숫자의 개수(0~9)자리수(1) 0 1 1 1 1 1 1 1 1 1자리수(2) 1 1 2 2 2 2 2 2 2 1자리수

한번 풀었던 문제이다.처음에 아래와 같이만 조건을 주었는데실패했다. 곰곰이 생각해보니 연결 지점이 나중에 나타나는 경우 오류가 발생하기 때문이다.ex) 만약에 1 22 55 36 4같은 경우에 1부터 시작해서 각 지점을 방문 처리 하는데 4같은 경우에는 1로 표시된 지

처음에 recursion error가 발생해서을 해줬는데 다시 메모리 초과 오류가 발생해서으로 해줬더니 해결 되었다. DFS로 푸는 것 보다. BFS로 푸는게 나아보인다.

백준 1012에서 주어진 조건의 지점의 개수만 구하면 된다. 재귀 함수를 쓰면 recursion 에러가 발생하는데 이번에는 sys.setrecursionlimit(10000) 으로 설정해주었다. 3000은 recursion error가 10**6은 메모리 초과랜다..ㅠㅠ

예전에 한번 풀었던 문제이다. 백준 1012 유기농 배추와 1743번 음식물 피하기 문제를 합쳐놓은 문제이다. 다만, 오름차순으로 정렬해서 출력해야하기 때문에 영역의 1의 합을 answer 리스트에 저장해놓았다가 정렬하고 출력한다.

문제 자체는 어렵지 않았지만 정상일때와 색맹일 때와 구별을 해서 작성을 해야해서 어떻게 해줄까 고민하다가 그냥 제일 클래식한 방법으로 copy 모듈을 import 해서 배열을 2개 만들어서 진행했다.

dfs_list의 초기화를 해주는 것이 중점인 문제이다. 어차피 사각형별로 좌표가 2개 주어지니 각 좌표의 x, y의 차이를 구해서 각 영역에 표시를 해주는 방법으로 초기화를 해주고 나머지는 백준 문제 2667번이랑 동일하다.백준 2667번

문제를 이해 못했다.

참고할 블로그문제의 아이디어는 학생들은 자기가 지목한 학생이 안갈경우 자신도 안가게 되니깐 학생들 사이에 순환(사이클)이 생기게 된다. 순환이 생길경우 학생들은 전부 가거나 전부 못 가는 경우가 생긴다. 순환이 생겼는데 갈 수 있는 학생 수보다 순환이 클 경우 -> 전

Brute Force 알고리즘이다. 브루트 포스 알고리즘은 사람 이름이 아니라 무차별 대입이라고도 하며 단순히 다 대입하면서 정답을 구하는 알고리즘이다.

특이하게도 문제를 직접 입력 받고 '대각선'도 검사를 해야하는 문제였다. 계속 틀려서 문제를 살펴봤더니 대각선도 체크를 해줘야하는 문제였다. 결론 : 맨 처음 문제를 잘 읽자

다른 사람의 코드를 참고했다. BF (Brute Force) 알고리즘을 사용했다.

알고리즘 한문제당 1시간을 넘기지 않으려고 하다보니 일단 다른사람의 코드를 가져왔다.

루트와 자식간의 관계를 표현하기 위해 집합으로 표현하는 아이디어를 배운 것 같다. 우선 순위 탐색이므로 재귀 함수를 사용하여 DFS 방식으로 구현이 되었다.

DFS와 BFS이다. BFS의 핵심은 큐를 사용하는 것인데 파이썬에서는 deque를 이용한다. 일반적인 리스트를 사용할 때와 시간 차이가 어마무시하게 난다.

dfs 처럼 각 함수에bfs(x+1, y)bfs(x, y+1)..처럼 입력해주려다가 각 경로마다 돌면서 경로의 갯수를 그래프 변수에 넣는게 낫다라는 생각이 들었다. (dp의 memoriable)

세상 원시적으로 풀었다. 몇가지 조건을 추가해주면 될 것 같아서 추가 해주다보니 이미 내 코드가 잘 못 되었다는 것을 직감했다. 역시 index error가 발생했다. 이유는 test case에 음수가 들어갈 경우 visited 배열에 없기 때문이다. 문제 푸는 아이디

나름 맞게 푼거 같은데 왜 틀릴까..? 정답을 보고 분석을 해보자..열심히 분석을 해보니 D 값이 - 일경우 나는 그냥 use stairs 출력하는데 정답 코드는 에러가 발생한다. D가 그냥 <= 1000000 로만 나와 있었는데 마이너스 값을 의도 한 것 같다라

불 처리하는게 시간내에 되지 않았다. 정답코드는 어떻게 했는지 확인해보자..문제를 잘 못 이해하고 있는 것을 확인했다. 불이 동서남북으로 한번만 번져나가는 줄 알고 어떻게 구현해야하나 고민을 했는데 시간이 지날 수록 불이 번져나간다는 이야기였다. 그럴경우 사람과 불을

BFS에 대해서 다시 한번 이해하게 되는 계기가 되었다. 가면서 벽을 부수고 이동하면 되는 것이 었다. 처음에는 그냥 모든 벽을 다 부수면서 경우의 수를 찾는다고 생각하다가 그럴거면 알고리즘을 왜 배우나라는 생각이 들었다. 문제 해결은 간단했다. 일단 간 다음 벽을 부

for 문을 2번 사용해서 해결하는 코드이다. 5427번 불 문제랑 비슷한 것 같다.백준 5427번 불 문제 처럼 while을 2개 써서 구하려 했는데 어제는 이해 했다고 생각해서 구해봤는데 아직 덜 이해가 된 것 같다. 하지만 이번에 탈출의 정답 코드는 for문을 2

나름 열심히 머리를 굴려서 풀었는데 로컬에서는 성공인데 백준에서는 실패가 뜬다.. 내가 생각치 못한 부분이 있었겠지..맙소사.. 한가지의 레지스터가 아니라 조합해서 답을 구하는 것이었다. visited \* 10000 리스트를 만들어서 방문을 체크한다. 어느 레지스터든

단순히 빈칸을 이동시켜서 리스트가 정렬될 때, 출력해주면 될 줄 알았는데 실패했다.

최대한 앞에서 캠핑을 진행하면 된다.

처음에는 무슨 문제인가 했다. 푸는 시간이 누적 되므로 (10) + (10+10) + (10+10+10) + (10+10+10+20) -> 이런식으로 리스트에 슬라이싱을 사용하여 계산했다.

핵심인 것은 처음에 2차원 배열로 나타냈었다. 하지만 이 문제는 노드의 개수가 최대 100,000개 이므로 이차원 배열에서 연결상태를 표시하게 되면 10만\*10만 = 100억개의 칸을 사용하기 때문에 메모리 초과가 날 수 밖에 없어 append로 추가해주는 방식으로

끝나는 시간이 같다면 빨리 시작하는 순서대로 정렬이 되어야 한다.예를 들자면22 21 2의 경우 이 상태로 한다면 (2 2)가 되고 (1 2)는 (2 2)의 끝나는 시간보다 시작시간이 일찍이기 때문에 무시되어 1번의 회의가 진행된다고 나온다. 하지만 정렬을 통해 (1

시간 초과가 발생하였다 코드자체는 맞게 한 것 같은데..

문제가 너무 이해가 안되어서 고민을 오래 했다. 문제가 이해한 뒤에는 금방 풀었다.

나름 맞게 코드를 짠 것 같은데 틀렸다. 정답 코드가 없으므로 계속 맞을 때 까지 해보는 수 밖에 없을 것 같다..

이분 탐색을 이해한대로 코드를 작성하였지만 역시나 시간 초과!!어느 순간부터 시간 초과도 신경 써줘야하는 단계로 온 것 같다..하지만 시간을 어떻게 줄일 수 있는 몰라서 검색을 해봤다. 그래서 나온 개념이 파이썬의 리스트 내포 였다.일단 리스트 내포는 간단하게 말하자면

일반적인 이분 탐색 문제이다.

코드 임시 저장..

너무 쉬워서 풀면서도 이렇게 푸는게 아니구나 생각을 했다. 역시 시간초과 발생..어차피 탐색문제니 이분 탐색으로 구하면 될 것 같다.리스트가 2개 만들어지는데 첫번째 리스트만 정렬해서 이분 탐색을 해주면 된다.이분 탐색은 정렬된 배열에서만 사용할 수 있으므로 일단 비교

times가 주어진다. 문제 해결 방법은 시간을 이분탐색으로 계산하는 방법인데 times에 입국 심사대가 몇개가 있던 시간에서 각 심사대의 걸리는 시간을 나눈 다음에 더하면 심사를 받을 수 있는 사람들의 수가 계산이 된다.

수학적 사고가 필요한데.. 모르겠다.. 아직까지는..

dp는 항상 아이디어를 떠올리는게 어려운 것 같다.. 사실 그게 dp의 전부긴 하지만..이 문제 같은 경우에는 dp라는 리스트를 만들어서 누적합을 더해가고 계산할 값이 답겨져 있는 arr리스트의 현재 값과 비교해서 max 값을 넣어주면 되는 문제이다. 부분합이 최대가

세상 코드가 이렇게 간단하다니.. 고민하면서 풀었는데도 못 풀었는데 뭔가 현타가 왔다..

회심의 코드 작성 후 첫번째 시도인데 틀렸다..

첫번째 시도 코드

힙 문제였다.

힙 문제였다.

lambda를 사용해서 푸는 문제였다. 문제 풀 때, lambda를 사용해야겠다고 생각이 들었는데 lambda 사용방법에 저런게 있는지 몰랐다. key=lambda x: x \* 3은 num 인자 각각의 문자열을 3번 반복한다는 뜻이다.마지막에 모든 값이 0일 경우 답

알고리즘 스터디 나미님이 푸신 것 보고 나도 한번 풀어봤다. 높은 경우와 낮은 경우의 경우의 수를 구해서 하는 방법으로 풀었는데 풀면서 잘 못 됨을 느끼고 시간도 초과되어 코드를 확인했다. 오름차순으로 정렬하고 for를 돌리면서 돌은 만큼 갯수를 빼주는 방식으로 푼게

딕셔너리로 구현했다.

실패 코드..

문제를 잘 못 이해했다. 어제 ssafy 보면서 느끼는건데 내가 문제를 대충 읽고 푸는 경향이 있어 시간 낭비가 심한 것 같다. 이번에도 같은 문제가 발생했다. 일단 다른 알고리즘을 풀어야해서 올려놓기만 한다.

내림차순으로 정렬한다음 구명보트 제한에서 리스트 값을 뺀 나머지가 제일 몸무게가 적게 나가는 사람보다 클 경우 pop으로 몸무게가 제일 작은 사람을 제거해서(태워서) 계산해주었다.

메모리 초과에 주의해야한다. 주어진 범위 0 <= number < 100001를 조건에 설정을 해줘야지 초과가 발생하지 않는다.

코드가 지저분하다라는 느낌을 받았다. 일단 문제 흐름대로 구현을 했는데 더 좋은 코드가 있는지 고민해봐야할 것 같다. 다른 분의 코드를 참고해보자. 2진수로 변환할때 bin 함수를 사용했다. 깔끔하게 구현한 것 같아서 참고해봐야겠다.

너무 간단한 코드이다. 지금 생각해보니 굳이 리스트를 만들 필요도 없이 range를 0부터 10까지 설정해놓고 작성해도 될 것 같다.

너무 기초 문제라서 따로 작성할 것이 없다..

살짝 복잡하게 생각할뻔 했으나 결국에는 종류가 많으면 주어진 리스트의 /2 만큼 가져갈 수 있고 아닐경우 종류만큼 가져갈 수 있게 코드를 작성하면 되었다.

answer에 기본으로 n 값으로 초기화 해놓고 n-1부터 1까지 나누어서 나머지가 1일 경우 최솟값을 비교해서 answer에 넣어주면 된다.

정규 표현식도 공부할겸 정규 표현식으로 풀었다. 이제 좀 정규 표현식에 대해서 익숙해진 것 같아서 뿌듯하다.정규 표현식

좌표를 계산해서 하려하다가 계산 공식이 안잡혀서 그냥 dictionary로 초기화 해주고 진행했다.

딕셔너리로 풀었다. report_history에는 사용자가 신고한 사용자들이 담겨있다.report_count에는 신고당한 사용자의 신고 당한 횟수가 담겨있다.ban_list에는 k이상 신고당한 유저들의 이름이 담겨 있다.final_count에는 받은 메일 갯수가 담겨져

코드 자체는 어렵지 않았지만 효율성 테스트에서 문제가 생겼었다. 원하는 조건이 나왔을 때, 바로 결과를 종료할 수 있도록 반복문에서 종료 조건을 설정해주는 방식을 앞으로 고려해야겠다. 정말 필요할 때만 검사를 하는 방법이 필요하다.

BFS방법으로 풀었다. 다만 que를 사용하지 않고 리스트에서 각 계산 결과를 누적하는 방법으로 해결했다.

처음에 리스트로 만들어서 복잡하게 풀었지만 간단하게 해결할 수 있는 문제라 생각하고 토너먼트의 성질을 사용하려 했지만 실패해서 일단 정답 코드를 보고 분석을 해보려고 한다. 조가 2의 n제곱이기 때문에 각조를 계산하는 방법은 (a+1) // 2 방법이 된 것 같다. 이

문제 링크순열 문제이다. 내장 함수를 통해서 해결했다.

문제다른 사람 풀이2 < common의 길이 < 1,000 이므로 0, 1, 2는 무조건 존재하므로 이를 이용해서 풀었다.

문제 링크내 풀이대부분 비슷하게 풀었고 파이써닉하게 한줄로 표현한 코드도 있다.

문제파이썬에서 문자열을 거꾸로 뒤집는 방법for 문으로 문자열을 더해가는 방법(위에서 사용)list로 변환후 reverse 함수 사용문자열 슬라이싱 :-1

문제 링크Lv1에서는 문자열 관련 문제들이 많은 것 같다. checkString에 문자를 역순으로 더해가면서 가장 가까운 문자의 index를 반환하는 방법으로 해결했다. 다른 사람 풀이를 한번 봤는데 dictionary를 통해서 각 문자의 최신 index를 저장해놓는

replace 문자열 내장함수를 사용한 풀이이다.

그리드 문제를 풀 때에는 매번 최선의 선택을 하는 것이 좋다는걸 기억해야겠다.

\-가 있을 경우 다 빼버리면 원하는 값을 얻을 수 있다. 원래는 각 문자열을 돌면서 구분하려고 했는데 로직이 복잡해서 정답코드를 찾아봤더니 간단하게 split을 사용해서 분리를 했다.

왜 안되는지 도저히 모르겠어서 검색해봤더니 data = sys.stdin.readline()때문이었다. input의 오른쪽에 공백이 같이 오기 때문에 rstrip()를 해줘야한다.

원래는 순서대로 진행하면서 다음 나오는 숫자가 현재 나오는 숫자보다 작으면 지금까지의 값들을 전부 계산하는 식으로 했다. 하지만 이럴경우 1 3 2 7 같은 경우 성립하지 않는다.알고리즘을 풀 때, 다양한 방법으로 접근하는 연습이 필요해보인다. 거꾸로 생각해봤더니 쉽게

원래는 N이나 M이 3이하일 때 -1을 출력하는 코드를 작성했다. 하지만 애초에 두 행렬이 같을 경우 정답이 0이 된다.1 111

B와 R을 기준으로 2개의 리스트를 만들어서 분리해주었다.메모리는 44728KB 시간은 80ms가 나왔다.딕셔너리를 사용한 풀이이다. 전 값이랑 비교해주면서 저장했다. 이후에 횟수에 1을 더했다. (처음에 한 색으로 전체 칠한다는 조건)

참고 코드위 코드를 참고하기 전에 먼저 제 마음대로 2가지 방법으로 풀었습니다. X, Y를 정렬하고 indexOf와 lastIndexOf로 X, Y에서 숫자의 차이 만큼 answer 배열에 push 해주어서 풀었습니다.xObj, yObj라는 객체를 만들어 X, Y에서

참고 코드처음 풀 때, 문제 푸는 아이디어는 생각했습니다만.. 단어가 반복되었을 경우 단어를 합쳐서 체크만 해주면 되는 생각을 떠올리지 못했습니다.

문제의 아이디어를 떠올리긴 했습니다. 하지만 그게 슬라이딩 윈도우 알고리즘이라는 것을 몰랐고 코드로 구현하는게 어려웠습니다. 참고 블로그구간의 넓이가 고정되어 있을 때, 구간 합을 구하는 알고리즘처음의 구간에서만 합을 구하고 한칸씩 밀면서 처음 더한 값을 빼주고 다음

두 수 a, b의 최소 공배수를 구하는 방법은 'a \* b / 두 수의 공약수'로 구할 수 있습니다. reduce를 사용해 배열의 첫번째 숫자와 두번째 숫자부터 시작합니다. 그리고 두 수의 공약수를 구합니다. (유클리드 호제법으로 구할 수 있습니다.) 이후, redu

문제문제에서 시키는 그대로 작성했습니다. 하지만 숫자 범위가 너무 커서 메모리 초과, 시간 초과 오류가 발생했습니다. 위의 코드를 작성하면서 배운 것들만 정리하고 정답 코드를 살펴보려고 합니다.1\. 2차원 배열 초기화 const answer = Array(n).fil

'해당 종류의 옷을 입은 경우와 안입은 경우를 고려해주면 됩니다'즉 각 종류의 옷의 갯수 + 1을 해주면 입지 않는 경우까지 고려됩니다.그리고 뭐라도 하나는 입어야 하니 전부 안입는 경우의 수를 전체에서 1빼주면 정답이 나오게 됩니다.

처음에는 중복을 허용하는 집합인지 모르고 풀다가 오답이 나왔습니다. 문제를 잘 읽어보니 중복을 허용하는 집합이라 코드를 고쳤습니다. 문제는 처음부터 끝까지 차근차근 꼼꼼하게 읽어봐야겠습니다.알파벳으로 이루어진 2개의 문자만 허용하므로 정규식을 통해서 알파벳을 판별해줍니

통과는 되었지만 불필요한 연산이 너무 많다고 생각됩니다. 그래서 다른사람의 코드를 살펴봤습니다.문제 해결 아이디어입니다.isCorrect 함수를 만들었습니다.filter를 사용해서 각 문자열마다 가능한지 체크를 해줍니다.만약 skill에 없는 스킬이면 continue를

Stack을 이용한 풀이입니다. 문제를 해결하는 아이디어는 다음과 같습니다.\-1로 초기화 된 배열을 만들어줍니다.numbers를 순회하면서 각 index를 stack에 push 해줍니다.만약의 stack의 마지막 값 인덱스를 가진 numbers의 값이 현재 값보다 작

큐 방식을 통해 BFS로 풀었습니다. 하지만 시간초과.. JS의 shift()는 O(n)만큼의 시간 복잡도를 갖고 있기 때문에 시간 제한내에 풀기 어려웠습니다. 그래서 dp 방법을 통한 메모이제이션으로 불필요한 연산을 막아서 풀었습니다.dp를 사용했고 for문을 이용한

문제 링크풀이 아이디어numbers의 원소를 전부 문자열로 바꿔준다.문자열로 바꾼 원소들을 sort 함수를 통해서 정렬한다.\+를 통해 비교할 문자열을 합쳐주고 다시 반대로 합쳐줘서 -를 통해 숫자로 자동 변환하여 계산해준다.정렬하고 합쳐주었을 때, 큰 수를 구해야하므

문제문제를 충실하게 구현해서 1부터 n가지 모든 3진법 수를 구했습니다. 하지만 생각해보니 진법을 구하는건 기존 n에서 원하는 진법의 숫자로 나누면 되는 것을 망각했습니다. 예를 들어서 2진법으로 나타내고 싶으면 간단하게 n에서 2로 계속 나누면 되는거죠. 여기서 10

개인적으로 그리디 문제 유형에 약합니다. 그리디 문제 유형을 파악하는 연습을 해야할 것 같습니다. 이번 문제는 그리디로 풀 수 있는 문제였습니다. 문제를 푸는 아이디어는 다음과 같습니다.number의 각 원소를 순회하면서stack에 값이 존재하고 k가 0보다 크고 스택

처음 풀이 (오답 -> 시간초과) 문제에 충실히 구현했습니다. 다만 JS에서 큐를 구현하기 위한 shift()는 상당히 성능이 느리기 때문에 풀면서 시간 초과가 예상되었고 몇개의 테스트 케이스에서 시간 초과가 발생하였습니다.

문제 처음 풀이 (오답 -> 시간초과) 최대한 문제에서 소개된 순서대로 풀었습니다. 테스트 케이스도 맞고 이론상 풀리긴하지만 시간 초과가 발생했습니다. 아마 2차원 배열을 계속 복사하고 반복해서 같은 곳을 반복해서 그렇다고 생각이 됩니다. 문제를 풀면서 다시 한번

문제링크DFS를 사용해서 풀었습니다. 처음에 문제푸는 아이디어가 생각이 안나서 고민을 많이 했지만 계속 다방면으로 생각하다보니 풀 수 있었습니다.문제를 푸는 핵심 아이디어는 마을 1에서 다른 마을로 이동할 때, 그 경로가 가장 짧을 경우에만 확정시켜줘야합니다. 마을 1

문제 링크(https://school.programmers.co.kr/learn/courses/30/lessons/62048수학 문제 알고리즘이었습니다. 대각선이 지나가는 단위 정사각형의 개수를 구하는 수학적인 공식이 있습니다. 그래서 정답은 위와 같이 구현해

문제 링크기존에는 조합과 조건문을 사용해서 풀이했지만 시간 초과가 발생해서 다른 방법을 찾던 중에 hash를 사용한 방법을 알게 되었습니다.문제를 푸는 아이디어는 다음과 같습니다.weights를 정렬을 통해 내림차순으로 변경해줍니다.각 몸무게에 나올 수 있는 경우의 수

문제1시간 정도 고민하다가 도저히 시간과 효율성 부분에서 해결이 나지 않아 다른 분의 코드를 참고했습니다. 풀이 아이디어각 배열을 오름차순으로 정렬해준다. (각 배열의 첫 원소를 나눌 수 있어야하므로)arrayA의 첫 원소를 첫 원소를 기준으로 -1해주면서 조건에 맞는

문제백트레킹의 대표적인 문제 N-Queen 입니다.백트래킹(Backtracking)이란?해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다.즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.이를 가지치기라

2가지 경우로 나누어서 생각했었습니다. 순간이동을 할 경우 시간이 증가하지 않기 때문에 예외 처리를 해줘야 했습니다.문제를 푸는 아이디어처음 방문을 한 경우와 한번 이상 방문한 경우를 나누었습니다.처음 방문했을 경우 (visitedidx가 false인 경우) 순간 이동

문제3차원 배열을 사용한 BFS 문제였습니다. 처음에 시간 초과가 발생했었는데 방문 처리를 현재 좌표일 경우에 해줘서 생긴 문제였습니다.

문제 링크맨처음에는 단순하게 shift와 push를 통해서 큐를 구현했지만 시간초과가 걸렸습니다.다른 분들 풀이는 대부분 링크드 리스트를 구현해서 푸시던데 단순하게 배열의 idx와 push를 통해서 구현했습니다.