티스토리

chaewss

검색하기

블로그 홈

chaewss

chaewsscode.tistory.com/m

서채리 님의 블로그입니다.

구독자: 6

방명록 방문하기

주요 글 목록

[Java] BOJ/백준 17070번 파이프 옮기기 1 [문제] https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [풀이] 약간.. 구현문제에 DFS 살짝 추가한 정도의 문제 같다. 그냥 7가지 경우의 수에 따라 파이프의 한쪽 끝이 원하는 위치에 도달할 때까지 깊이 우선 탐색을 진행한다. 아래 5가지에 유의하면서 풀었다. 1. 파이프 끝점을 기준으로 한다. 2. 파이프 주위 꼭 빈칸이어야 하는 곳에 벽이 있을 경우 파이프를 이동할 수 없다. 3. 파이프가 가로일 경우, 가로로.. 공감수 0 댓글수 0 2024. 4. 16.
[Java] BOJ/백준 1194번 달이 차오른다, 가자. [문제] https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net [풀이] 민식이의 최소 이동 횟수를 구해야 하기 때문에 BFS 문제라고 유추할 수 있다. 하지만 일반 BFS 문제와는 다른 점이 크게 두 가지 있는데 1. 열쇠 정보값에 따라 방문할 수 있는 미로가 다르기 때문에 획득하는 열쇠 값을 저장해야 한다. 2. 다른 BFS 문제와는 달리 이미 방문했던 곳을 다시 방문해야 되는 경우가 발생한다. 📌 열쇠 정보 저장하기.. 공감수 0 댓글수 0 2024. 4. 16.
[Java] BOJ/백준 16236번 아기 상어 [문제] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net [풀이] 문제에서 중요한 조건은 1. 초기 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 2. if (아기 상어 크기 ≥ 물고기 크기) 아기 상어가 지나갈 수 있다. 3. if (아기 상어 크기 > 물고기 크기) 아기 상어가 물고기를 먹을 수 있다. 4. 먹을 수 있는 물고기가 1마리라면 그 물고기를 먹으러 가고, 5. 먹을 수 있는 물고기가.. 공감수 0 댓글수 0 2024. 4. 15.
[Java] BOJ/백준 14003번 가장 긴 증가하는 부분 수열 5 [문제] https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net [풀이] [Java] BOJ/백준 12738번 가장 긴 증가하는 부분 수열 3 [문제] https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,00.. 공감수 0 댓글수 0 2024. 4. 11.
[Java] BOJ/백준 14002번 가장 긴 증가하는 부분 수열 4 [문제] https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [풀이] [Java] BOJ/백준 11053번 가장 긴 증가하는 부분 수열 [문제] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {.. 공감수 0 댓글수 0 2024. 4. 11.
[Java] BOJ/백준 12738번 가장 긴 증가하는 부분 수열 3 [문제] https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net [풀이] [Java] BOJ/백준 12015번 가장 긴 증가하는 부분 수열 2 [문제] https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,0 .. 공감수 0 댓글수 0 2024. 4. 11.
[Java] BOJ/백준 12015번 가장 긴 증가하는 부분 수열 2 [문제] https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net [풀이] [Java] BOJ/백준 11053번 가장 긴 증가하는 부분 수열 [문제] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, chaewsscode.tistory.com 해당.. 공감수 0 댓글수 0 2024. 4. 11.
[Java] BOJ/백준 11053번 가장 긴 증가하는 부분 수열 [문제] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [풀이] 📌 최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 알고리즘 원소가 n개인 배열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 일반적으로 LIS의 길이를 .. 공감수 0 댓글수 0 2024. 4. 11.
[Java] BOJ/백준 16947번 서울 지하철 2호선 [문제] https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net [풀이] 이 문제는 1) 사이클이 발생하는 구간을 구할 수 있는지, 2) 그래프 탐색으로 최단 거리를 구할 수 있는지 를 판단하는 문제이다. 따라서 아래와 같은 순서로 문제를 풀었다. 1. DFS 탐색을 통해 사이클이 발생하는 구간을 체크한다. 2. BFS 탐색을 통해 모든 노드에서 사이클이 발생하는 노드까지의 최단 거리를 계산한다. 1️⃣ 사이클 발생 구간 체.. 공감수 0 댓글수 0 2024. 4. 8.
[Java] BOJ/백준 2170번 선 긋기 [문제] https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net [풀이] 이 문제의 핵심은 아래 두 가지로 요약할 수 있다. 1. 선을 좌표 기준으로 정렬해야된다. (우선순위 큐 혹은 배열 정렬) 2. 선이 포함되는 경우 조건문으로 처리 👎 배열에 선을 그은 곳은 1로 채워 총 1의 수를 구할 경우, 배열 크기를 2조로 지정해야되기 때문에 다른 방법을 생각해야한다. 문제에서 주어진 입력된 선을 형광펜으로 표시하면 이렇다.. 공감수 0 댓글수 0 2024. 4. 5.
[Python] BOJ/백준 2309번 일곱 난쟁이 [문제] https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net [풀이] "아홉 난쟁이의 키는 모두 다르지만 그중 일곱 난쟁이의 크기의 합은 100이 된다" 는 것은 sum(난쟁이 리스트) - (난쟁이1 + 난쟁이2) == 100과 같다. 두 난쟁이를 구하기 위해 전체 탐색을 해야 한다. [코드] import sys men = [int(sys.stdin.readline()) for _ in range(9)] flag = False for i in range(9.. 공감수 1 댓글수 0 2022. 9. 19.
[Python] BOJ/백준 11000번 강의실 배정 [문제] https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net [풀이] 문제의 핵심은 현재 수업의 종료 시간이 다음 수업의 종료 시간보다 늦을 경우 회의실 하나를 더 배정해야 한다. 먼저 수업의 시작과 끝 시간을 queue에 넣고 이를 정렬하면 시작 시간이 가장 빠른 수업이 가장 앞에 오게 되기 때문에 첫 수업의 종료시간을 새로운 큐인 room에 넣는다. 두 번째 수업부터 첫 번째 회의와 비교를 하는데 두 번째 수업의 시작시간 < 첫 수업의 종료시간 일 경우 강의실을 새로 배정해야 하고 그렇지 않.. 공감수 1 댓글수 1 2022. 9. 14.
[Python] BOJ/백준 15903번 카드 합체 놀이 [문제] https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net [풀이] 처음에는 간단하게 sort 함수를 이용해 풀었는데 이는 O(nlogn)으로 우선순위 큐를 이용하면 O(logn)으로 시간복잡도를 줄일 수 있다. 우선순위 큐 사용시, 값을 바꿀 카드 2개를 우선순위 큐에 삽입만 하면 되기 때문에 매번 정렬해야하는 sort 보다 훨씬 효율적인 것이다. 따라서 cards 리스트를 만든 후 heapq 내장 모듈 사.. 공감수 1 댓글수 0 2022. 9. 10.
[Python] BOJ/백준 9009번 피보나치 [문제] https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net [풀이] 우선 피보나치 리스트를 만들어 올바른 값을 미리 넣어준다. 문제에 n의 최댓값이 1,000,000,000이라고 했기 때문에 44번 째 피보나치 수열까지만 구하면 된다. 만들 수 있는 숫자 중 최소 개수로 n을 만들기 위해서는 n 이하의 수 중 가장 n과 가까운 수를 써야 한다. 문제에 나온 예시처럼 100을 만들기 위해서는 (3 + 8 + 89) 도 가능하지만 (3 + 8 + 34 .. 공감수 1 댓글수 1 2022. 9. 6.
[Python] BOJ/백준 1946번 신입 사원 [문제] https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net [풀이] 우선.. for문을 두 번 쓰면 런타임 에러가 난다. 당연함. 100,000명을 2차 반복문으로 돌리면.. 따라서 반복문 한번에 비교를 끝내야한다. 그러기 위해 우선 첫 번째 점수를 기준으로 정렬을 한 후에 rank_asc 변수에 담는다. rank_asc 변수의 첫 번째 원소는 서류 심사가 가장 높은 사람이 오기 때문에 이 사람의 면접 결과가 몇 점이든 무조.. 공감수 0 댓글수 0 2022. 9. 6.
[Python] BOJ/백준 1817번 짐 챙기는 숌 [문제] https://www.acmicpc.net/problem/1817 1817번: 짐 챙기는 숌 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책 www.acmicpc.net [풀이] 이 문제의 핵심은 책을 차례대로 박스에 넣을 수 있다는 것이다. 때문에 차례대로 반복문을 돌며 박스에 책을 넣었을 때 박스에 들어간 무게가 M을 넘는다면 박스 무게를 초기화 하여 현재 책의 무게를 담고 cnt를 1 증가시킨다. [코드] import sys N, M = map(int, sys.stdin.readline().split()) if N > 0: bo.. 공감수 1 댓글수 1 2022. 9. 4.
[Python] BOJ/백준 1439번 뒤집기 [문제] https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net [풀이] 입력받은 문자열을 한 글자씩 리스트에 넣는다. 첫 번째 문자가 0이면 zero_count를 1 더해주고, 1이면 one_count를 1 더해준다. zero_count: 0을 1로 바꿔야 하는 횟수 one_count: 1을 0으로 바꿔야 하는 횟수 반복문으로 문자열의 (i - 1) 인덱스와 (i) 인덱스의 값이 일치하는지 확인한다. 일치하지 않을 경우 (i) 인덱스의 값이 0이면 .. 공감수 1 댓글수 3 2022. 9. 4.
[Python] BOJ/백준 3578번 Holes [문제] https://www.acmicpc.net/problem/3578 3578번: Holes You may have seen a mechanic typewriter — such devices were widespread just 15 years ago, before computers replaced them. It is a very simple thing. You strike a key on the typewriter keyboard, the corresponding type bar rises, and the metallic letter mo www.acmicpc.net [풀이] 문제에 쓸데없는 설명들이 많은데 요약하자면 0, 4, 6, 9 를 타이핑 할 경우 종이에 구멍이 1개 생기고 8 을 타이.. 공감수 1 댓글수 1 2022. 9. 3.
[Python] BOJ/백준 10162번 전자레인지 [문제] https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net [풀이] 그리디 문제! 최종 결과는 신경쓰지 않고 일단 현재 가장 이익이 될 것을 선택한다. 여기서 현재 가장 이익이 될 것 = 거스름돈이 제일 작을 것 시간이 긴 버튼을 누르는 게 이익이 되기 때문에 5분부터 차례대로 답을 찾아간다. [코드] import sys T = int(sys.stdin.readline()) A, B, C = 300, 60, 10 if T % C != 0.. 공감수 0 댓글수 0 2022. 9. 3.
[Python] BOJ/백준 2468번 안전 영역 [문제] https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net [풀이] 지역의 높이 정보를 set 으로 모아 어떤 높이의 건물이 있는지 비가 얼마나 오는 지 모르기 때문에 0부터 건물 최고 높이까지 비를 내리게 한다. 건물의 높이는 지역의 높이 정보를 set 으로 모아 확인한다. 건물 높이보가 현재 내리는 비 높이보다 크고 아직 그 건물을 방문한 적이 없으면 count 를 하나 올리고 bfs 함수로 들어간다. 현재 기준이 되는 건물의 상하좌우 에 있는 건물.. 공감수 0 댓글수 0 2022. 8. 26.
[Python] BOJ/백준 10159번 저울 [문제] https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net [풀이] 2022.08.25 - [문제풀이/BOJ] - [Python] BOJ/백준 2458번 키 순서 [Python] BOJ/백준 2458번 키 순서 [문제] https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명.. 공감수 0 댓글수 0 2022. 8. 26.
[Python] BOJ/백준 1956번 운동 [문제] https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net [풀이] 2022.08.23 - [문제풀이/BOJ] - [Python] BOJ/백준 11404번 플로이드 [Python] BOJ/백준 11404번 플로이드 [문제] https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m.. 공감수 0 댓글수 0 2022. 8. 26.
[Python] BOJ/백준 2458번 키 순서 [문제] https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net [풀이] 두 학생 a, b를 a가 b를 향하는 방향 그래프로 나타내면 키의 크고 작음을 표시할 수 있다. 플로이드-와샬 알고리즘을 통해 한 정점에서부터 모든 정점으로의 연결 상태를 알아내어 그래프를 갱신한다. 왼쪽 리스트는 예제 2번 문제를 플로이드-와샬 알고리즘을 통해 그래프를 갱신한 상태이다. 위 그림의 1번 노드는 다른 정점을 통해 모든 정점으로 연결될 수 있기 때문에 리스트[0] 은.. 공감수 0 댓글수 0 2022. 8. 25.
[Python] BOJ/백준 11404번 플로이드 [문제] https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net [풀이] 문제에도 플로이드라고 나왔지만 모든 정점에서 다른 모든 정점으로의 최단 경로를 구해야 하기 때문에 플로이드 와샬로 풀었다. + 처음에는 INF 로 안풀고 문제에 비용의 최댓값이 100,000 이라 나와있어 리스트를 100001로 초기화하고 풀었는데 틀렸다.. 이유는 모르겠음 그냥 앞으로 저런 문제 나오면 int(1e9)로 풀어야지 [코드] from sys import stdin .. 공감수 0 댓글수 0 2022. 8. 23.
[Python] BOJ/백준 11403번 경로 찾기 [문제] https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 그래프 최단 거리 문제 다익스트라 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 플로이드 와샬 거쳐가는 정점을 하나씩 다 설정을 하여 해당 정점을 기준으로 최단 거리를 구하도록 구성 → 모든 쌍 간의 최단 거리를 구할 수 있음 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 [코드] import sys N = int(sys.stdin.readline()) graph = .. 공감수 0 댓글수 0 2022. 8. 20.
[Python] BOJ/백준 16928번 뱀과 사다리 게임 [문제] https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net [풀이] 우와 탐욕법인가 했는데.. 이게··· BFS 문제라니.. 충격과 공포 그자체였음 그렇지만!.... 탐색 문제인걸 알기만 하면 문제 푸는건 쉽다 하하 사다리와 뱀 dictionary를 만들어 key와 value로 저장한다. deque로 선언한 큐에 처음 출발지인 1을 넣는다. 주사위 숫자인 1부터 6까지 반복문을 돈다. 이동할 칸이 1.. 공감수 0 댓글수 0 2022. 8. 19.
[Python] BOJ/백준 10026번 적록색약 [문제] https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net [풀이] 딱봐도 탐색문제..~ 내가 계속 BFS로 풀어서 DFS로도 한번 풀어봤다 계속 까먹어서 적어두는데 BFS는 deque를 이용해 풀고 DFS는 재귀 호출을 이용해 푼다. 공통점은 둘 다 visited를 이용해서 해당 칸 방문 여부를 검사했다. [BFS 코드] import sys from collections import deque n = int(sys.stdin.readli.. 공감수 0 댓글수 0 2022. 8. 18.
[Python] BOJ/백준 1010번 다리 놓기 [문제] https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net [풀이] 우선 이 문제는 풀이 방식이 두 가지가 있다. 동적 프로그래밍을 이용해 풀기 조합을 이용해 풀기 동적 프로그래밍 풀이 1 2 3 4 5 1 1 2 3 4 5 2 X 1 3 6 10 3 X X 1 4 10 행이 n, 열이 m을 나타낼 때 1. n이 1인 경우 만들어지는 경우의 수는 m과 같다. 2. n이 2이상인 경우 num[n][m] = num[n][m - 1] + num[n -.. 공감수 0 댓글수 0 2022. 8. 2.
[Python] BOJ/백준 1992번 쿼드트리 [문제] https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net [풀이] 재귀 문제.. 분할 정복법 문제 2021.08.11 - [문제풀이/BOJ] - [Python] BOJ/백준 2630번 색종이 만들기 [Python] BOJ/백준 2630번 색종이 만들기 [문제] https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, .. 공감수 0 댓글수 0 2022. 7. 6.
[Python] BOJ/백준 2667번 단지번호붙이기 [문제] https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net [풀이] 🔥 DFS vs BFS ✨ DFS, BFS 모두 적합한 유형 단순히 모든 정점을 방문하는 것이 중요한 문제인 경우 ✨ DFS가 적합한 유형 검색 대상 그래프가 큰 경우 (정점과 간선의 개수가 많음) 경로의 특징을 저장해둬야 하는 문제 ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제 BFS는 경로의 특징을 가지지 못함 .. 공감수 0 댓글수 0 2022. 7. 4.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.