profile
Go Go
post-thumbnail

[이코테] DFS : 14888 연산자 끼워넣기(BaekJoon)

주어진 연산 값이 + 는 x개 - 는 y개 같은 형식으로 주어졌다. 이를 어떻게 DFS 백트래킹 형식으로 풀어야 할지 감이 오지 않았다.나는 일반적인 DFS처럼 만들기 위해 각각의 개수에 대해 배열을 만들어 방문 체크를 할 수 있도록 만들었다.주어진 연산자 형태를 유지

7일 전
·
0개의 댓글
post-thumbnail

[BaekJoon] 6087 레이저 통신

처음엔 데크의 앞으로 넣어서 거울쓰는 갯수가 적은 것부터 방문하려고 했으나 실패했다. 다른 방향으로 왔을 때 빠른 경우가 존재하기 때문인 것 같다.이 문제의 핵심아이디어는 한 방향으로 갈 수 있는 곳을 모두 방문하는 것이다. 그렇게 하면 그 순간에 방문할 수 있는 곳을

2020년 10월 13일
·
0개의 댓글
post-thumbnail

[BaekJoon] 15558 점프 게임

기본적인 BFS 문제이다.각각의 경우 ( +1, -1, jump + k ) 를 나눠 큐에 넣는다.이 때 반드시 방문 체크를 해줘야 메모리가 초과되지 않는다.count가 하나씩 늘어난다는 것만 조심해주면 된다.3가지 경우를 for문을 통해 깔끔히 정리했다.또한 for문을

2020년 10월 13일
·
0개의 댓글
post-thumbnail

[BaekJoon] 12100 2048 (Easy)

두가지 의문이 있었다. 어떻게 배열의 정보를 유지할 것인가? 모든 정보를 보관하면 dfs, bfs 시 메모리가 너무 많아지지 않을까?5번만 진행하면 되기 때문에 dfs를 하면 최대 5개의 배열 복사본이 생긴다.그렇기 때문에 메모리 초과를 걱정하지 않아도 된다. 🤔 그

2020년 10월 10일
·
0개의 댓글
post-thumbnail

[BaekJoon] 9328 열쇠

BFS의 실행 순서를 종잡을 수가 없다..어떡하지?\-> 순서를 뒤죽 박죽이라면 일단 저장해두는 것이 옳다.\--> Key가 없는 문을 만난다면 현재 진행할 수 없지만 나중에 진행할 수 있는 것이므로 다른 큐에 저장해둔다.열쇠를 찾기전에 문을 검사하고 그 후에 열쇠를

2020년 10월 9일
·
0개의 댓글
post-thumbnail

[BaekJoon] 9376 탈옥

일반적인 BFS와 문제풀이 방법이 다르며 아이디어가 필요했다. 죄수들이 문을 열며 탈출하는 경우가 있고 상근이가 죄수들을 구하러 가는 3가지 시나리오가 있다고 생각해보자.첫번째 죄수가 문을 열고 나오는 경우두번째 죄수가 문을 열고 나오는 경우상근이가 죄수를 구하러 가는

2020년 10월 9일
·
0개의 댓글
post-thumbnail

[BaekJoon] 12851 숨바꼭질2

보통 문제는 가장 빠른 시간에 구한 답을 가지고 루프를 탈출한다. 하지만 이 문제는 가장 빠른 시간에 도착한 모든 답을 원했다.같은 시간에 같은 위치에 도달한 것 까지는 인정해줘야 한다.방문 체크를 push 전에 하면 동시에 도착한 단 하나만 push된다.방문 체크를

2020년 10월 8일
·
0개의 댓글
post-thumbnail

[BaekJoon] 2251 물통

물의 양이 항상 같으므로a->b , a->cb->c , c->ac->b , b->a이 6가지 경우로 물을 옮기는 것만 생각해주면 된다.또한, 방문 검사는 a, b, c 각 물의 양에 따라 체크하기 위해 3차원 배열을 이용했다.C의 물통을 표시하지 않고 A와 B 두개의

2020년 10월 8일
·
0개의 댓글
post-thumbnail

[BaekJoon] 1525 퍼즐

첫 풀이 때 메모리 제한이 있다는 걸 알았지만 3x3 배열의 상태를 큐로 넣어서 넘기려고 했고 당연히 메모리 초과가 발생했다.메모리 초과를 피하기 위해선 리스트로 위치를 표현하는 방법 대신 문자열로 위치 상태를 표현해야 한다.문자열을 통한 위치 상태 기록 및 방문 파악

2020년 10월 8일
·
0개의 댓글
post-thumbnail

[BaekJoon] 9019 DSLR

전형적인 BFS 문제이며 생각해야 할 것은 딱 하나였다. \-> 어떻게 LEFT와 RIGHT를 네자리수가 아닐때에도 적절히 구현할 것인가..?L : 첫번째 자릿수는 나누기 1000을 통해 나머지 세자리는 나머지 1000을 통해 구할 수 있다. => (X%1000)\

2020년 10월 7일
·
0개의 댓글
post-thumbnail

[BaekJoon] 7453 합이 0인 네 정수

모든 조합의 합을 구하면 $O(4^{4000})$이 최악이므로 절대 불가능 하다.따라서, 4개의 숫자를 쪼개 두 개씩 더한 값으로 나눈다.< 풀이 순서 >1\. 투 포인터를 사용하기 위해 두 리스트를 정렬한다.2\. 두 리스트 값을 더해서 0 이면 각각의 리스트에

2020년 10월 5일
·
0개의 댓글
post-thumbnail

[BaekJoon] 1208 부분수열의 합 2

$2^{20}$ 은 $10^6$, $2^{40}$ 은 $10^{12}$1억은 $10^8$ (시간복잡도 계산 시 사용)40개의 모든 조합을 만들기 위해선 $O(2^{40})$ 만큼이 필요하다.따라서 조합을 반절 씩 나눠 모든 조합을 구하고 그 합을 투 포인터로 구해서 답

2020년 10월 5일
·
0개의 댓글
post-thumbnail

[BaekJoon] 2143 두 배열의 합

원소가 자연수가 아닌 음수가 가능한 정수이다.따라서, 이전 투 포인터 문제와 같이 푸는 것은 불가능하다.각자의 모든 조합을 구해( $O(2^1000)$ ) 더해보는 것은 시간이 엄청 많이 걸린다.< 풀이 순서 >모든 부분합은 $O(n^2)$으로 처리 가능하다.딕셔

2020년 10월 5일
·
0개의 댓글
post-thumbnail

[BaekJoon] 1644 소수의 연속합

🔦 문제 링크 ✍️ 나의 풀이 > * 에라토스테네스의 체 + 투 포인터 문제 에라토스테네스의 체에서 $i^2$까지 🛠 나의 코드 ✍️ 다른 사람 풀이 🛠 다른 사람 코드 📝 정리 🎈 참고

2020년 10월 3일
·
0개의 댓글
post-thumbnail

[BaekJoon] 2003 수들의 합 2

투 포인터 문제left와 right를 정해서 값이 작으면 더해주고 크면 빼주고 같으면 count를 세주는 형식으로 진행한다.<중요포인트>sum이 m보다 더 작을 때 right가 n을 넘어가면 sum이 더 증가할 수 없으므로 종료해도 상관없다. 투 포인터 사용법에

2020년 10월 2일
·
0개의 댓글
post-thumbnail

[BaekJoon] 13460 구슬탈출 2

최소 이동을 구해 빠져나오면 되므로 BFS로 구한다.빨간구슬과 파란구슬의 동시에 움직이기에 4차원배열을 통해 방문여부를 검사한다. (블로그를 참고)\`> \* 만약 두 구슬 위치가 같다면 더 많이 움직인 구슬을 한 칸이전으로 돌려줘야한다.4차원 배열을 선언해 방문여부

2020년 10월 1일
·
0개의 댓글
post-thumbnail

[BaekJoon] 1062 가르침

5개 미만 일 때와 5개 이상일 때를 구분해야한다.무조건 배워야 하는 알파벳은 배웠음을 체크해둔다.DFS를 통해 k개 알파벳의 모든 경우의 수를 따져볼 수 있다.<시간초과 해결>배우는 순서는 중요하지 않기 때문에 이전에 배운 단어를 다시 볼 필요는 없다.따라서,

2020년 9월 30일
·
0개의 댓글
post-thumbnail

[BaekJoon] 14391 종이조각

빠른 계산을 위해 1과 0으로 나눠 가로와 세로를 비트마스크로 표현한다.모든 경우의 수는 배열이 가질 수 있는 모든 경우이다.따라서 (1 << n\*m) 이라고 볼 수 있다.2차원 배열을 비트마스크로 표현했으므로i\*m+j의 식을 이용해 모든 위치를 검사한다

2020년 9월 30일
·
0개의 댓글
post-thumbnail

[BaekJoon] 9663 N-Queen

백트래킹 문제같은 행은 어차피 하나 밖에 못두므로 검사할 필요 없음아래 열은 신경쓰지 않고 위에 열과 겹치는 부분이 있는지 검사col\[j] == col\[i]를 통해 현재 열보다 위에 있는 열의 행과 겹치는 지 검사abs(col\[i] - col\[j]) == (i

2020년 9월 28일
·
0개의 댓글
post-thumbnail

[BaekJoon] 2580 스도쿠

배열에서 값을 정해야하는 위치를 zero에 기록해둔다.DFS를 이용해 가능한 경우의 수를 백트래킹으로 따져본다.작은 사각형의 시작 지점을 찾는 것이 중요하다 -> (x//3 \* 3)<검사 조건>1\. 가로 줄에 없는 숫자 확인2\. 세로 줄에 없는 숫자 확인3\

2020년 9월 28일
·
0개의 댓글