profile
A Student of Computer Science

[BOJ 2206] 벽 부수고 이동하기 (Python)

복습 요망!!먼저 벽과 상관없이 (1, 1)에서 출발하여 (N, M)에 도착하였을 때 최단 경로를 BFS로 구현하였다. BFS로 탐색하면서 벽을 1번만 뚫을 수 있다는 조건을 구현하는 것이 어려웠다. 처음에는 벽을 뚫었는지 안뚫었는지를 저장하는 전역 변수를 만들어서 T

어제
·
0개의 댓글
post-thumbnail

[BOJ 16437] 양 구출 작전 (Python)

복습 요망!!처음 union-find 알고리즘의 find 알고리즘을 이용하여 탐색하는 섬이 1번 섬으로 이동할 수 있는지 먼저 판단한 후, 탐색하는 섬에서부터 1번 섬으로 가는 경로가 존재한다면 1번 섬으로 가는 중에 양 - 늑대를 계산하면서 모든 경로를 전부 탐색하는

어제
·
0개의 댓글
post-thumbnail

[BOJ 2146] 다리 만들기 (Python)

문제를 푸는 대략적인 로직은 아래와 같다.대륙을 숫자화 시킨다. (넘버링)대륙의 가장자리에서 다리를 설치한다. (확장)대륙과 대륙이 만날 수 있을 때까지 다리를 설치한다.다리의 길이 중 최솟값을 계산하여 답을 도출한다.이해를 돕기 위해 그림으로 추가적인 설명을 덧붙히려

어제
·
0개의 댓글
post-thumbnail

[BOJ 1707] 이분 그래프 (Python)

처음 이분 그래프의 개념에 대해 잘 몰라 헤맸던 문제이다. 아래는 이분 그래프를 표현한 그림이다.사진 출처 : 링크그림처럼 시작하는 정점에 연결된 간선을 따라 이어진 정점들을 하나씩 탐색하면서 색을 바꿔가며 칠했을 때, 같은 색끼리는 간선이 없는 경우를 이분 그래프라고

어제
·
0개의 댓글
post-thumbnail

[BOJ 2667] 단지번호붙이기 (Python)

문제를 보자마자 BFS 방식으로 접근하였다. 하나씩 깊게 탐색하는 DFS에 비해 여러 개씩 넓게 탐색하는 BFS가 효율적이라고 생각했기 때문이다. 전체적인 로직은 아래와 같다.(0,0)부터 상하좌우에 연결된 집이 있는지 확인한다.연결된 집이 있으면 단지화 시킨다.모든

3일 전
·
0개의 댓글

[BOJ 1260] DFS와 BFS (Python)

기본적인 DFS와 BFS의 기본 개념을 알고 있는지 물어보는 문제라고 생각했다. DFS와 BFS에 대해 알고있다면 쉽게 풀 수 있다! DFS와 BFS에 대해 잘 모르겠다면 제 블로그에 글이 있으니 참고하시면 됩니다.

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

DFS / BFS

DFS

3일 전
·
0개의 댓글

[BOJ 1700] 멀티탭 스케줄링 (Python)

처음에 멀티탭 구멍 갯수만큼 먼저 전기제품을 꽂아준 후에 남아있는 전기제품들 중 사용빈도가 가장 높은 전기제품을 멀티탭에서 빼지않고, 나머지 꽂힌 전기제품들을 빼는 방식으로 접근하였다. 당연히 올바른 로직이 아니기 때문에 틀렸다. 문제를 푸는 로직은 아래와 같다.(전기

4일 전
·
0개의 댓글

[BOJ 1781] 컵라면 (Python)

같은 데드라인 문제들 중에서 받을 수 있는 컵라면 개수가 최대인 1문제를 선택해서 푸는 것으로 접근했다. 데드라인 마다 모든 문제들을 탐색하면 O(N²)으로 시간초과를 예상했다. 따라서 우선순위 큐를 이용하자는 생각을 하였고, 맞는 방법이었다. 이렇게 구현했지만 틀렸다

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

Union-Find 알고리즘

Disjoint-Set을 구현할 때 사용하는 알고리즘.집합을 구현하는데 비트 벡터, 배열, 연결리스트를 사용할 수 있으나, 가장 효율적인 트리 구조를 이용하여 구현함.크루스칼 알고리즘에서 그래프의 최소 신장 트리(MST)를 찾는데 활용된다. (정점 연결 및 사이클 형성

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

[BOJ 10775] 공항 (Python)

링크처음에는 비행기를 중심으로 1번 ~ 입력받는 gi번 사이의 모든 게이트를 탐색하여 그중 비어있는 게이트에 비행기를 도킹시키려고 하였다. 시간복잡도는 O(GP)로 100,000 x 100,000 = 10,000,000,000 시간초과를 예상하였고, 다른 방법으로 풀려

5일 전
·
0개의 댓글

[BOJ 1439] 뒤집기 (Python)

링크연속된 0의 덩어리 갯수와 연속된 1의 덩이리 개수를 구한다.그 중 최솟값이 정답이다.예제를 통해 올바른 풀이인지 확인해보자.(Ex) S=00011000연속된 0의 덩어리 -> 2개연속된 1의 덩어리 -> 1개이 중 최솟값은 1이다. 즉, 답은 1이 된다. 왜냐하면

5일 전
·
0개의 댓글

[BOJ 13458] 시험 감독 (Python)

링크아래의 로직으로 문제를 접근하였다. 각각 시험장 인원마다 시험감독관을 배치하도록 하였다.(첫 번째 시험장 경우) 시험장 총 인원 - 총감독관 감시 가능 인원을 계산하고, 필요한 감독관 수를 1 증가시킨다.계산된 시험장 총 인원 - 총감독관 감시 가능 인원을 부감독관

5일 전
·
0개의 댓글

[BOJ 1434] 책 정리 (Python)

링크수학적으로 생각하면 풀 수 있는 쉬운 문제라고 조심스럽게 생각해본다. 풀이과정은 너무나도 간단하다. 전체 박스의 무게의 합 - 전체 책의 무게의 합을 구하면 된다. 현재 책이 현재 박스에 들어가지 않으면 3번 -> 2번으로 가는 이동방향은 중요하지 않고, 문제에서

5일 전
·
0개의 댓글

[BOJ 2720] 세탁소 사장 동혁 (Python)

링크나눗셈 연산과 나머지 연산을 이용한 풀이로 접근하였다. 어렵지 않은 문제였다고 조심스럽게 생각해본다.쿼터(Quarter, $0.25) 동전부터 시작하여 거스름돈 계산을 진행한다. (나눗셈 연산)돈 거슬러주고 남은 거스름돈 갱신한다. (나머지 연산)1번, 2번 과정을

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

[자료구조] 우선순위 큐 (Priority Queue)

우선순위 큐 (Priority Queue)

2021년 4월 8일
·
0개의 댓글
post-thumbnail

[자료구조] 힙 (Heap)

힙(heap)이란? 우선순위 큐를 위해 만들어진 자료구조이다.힙은 완전 이진 트리(Complete Binary Tree)의 일종이다.힙은 반정렬 상태(느슨한 정렬 상태)를 유지한다.모든 노드에 저장된 값(우선순위)들은 자식 노드들의 것보다 우선순위가 크거나 같아야 한다

2021년 4월 8일
·
0개의 댓글
post-thumbnail

[BOJ 1041] 주사위 (Python)

링크이 문제는 수학 문제라고 생각한다. 규칙을 찾고, 수식을 도출하면 문제를 쉽게 풀 수 있다. 위 문제에서 3개의 기준을 잡고 규칙을 찾아야한다. 1\. 면이 하나만 보이는 경우2\. 면이 2개가 보이는 경우3\. 면이 3개가 보이는 경우N x N x N인 정육면체에

2021년 4월 8일
·
0개의 댓글

[BOJ 1202] 보석 도둑 (Python)

링크문제를 파악할 때 Knapsack 문제인 줄 알았으나 아니였다. 가방이 여러개가 있으며 가방 하나에는 딱 하나의 보석만 담을 수 있다는 조건이 있다. 따라서 최대한 비싼 보석을 하나라도 더 훔치는 것이 중요하다.비싼 보석인데 무겁다고 해서 더 싸고 가벼운 보석에게

2021년 4월 8일
·
0개의 댓글
post-thumbnail

[BOJ 2212] 센서 (Python)

링크각 집중국은 센서의 수신 가능 영역을 조절할 수 있고, 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. 센서가 적어도 하나의 집중국과 통신이 가능해야 한다. 즉, 센서와 집중국이 통신하지 않는 경우는 없다는 것이다. 예제를 통해 설명하려

2021년 4월 8일
·
0개의 댓글