[BOJ/백준] 1043 거짓말 - 파이썬
·
💻 알고리즘/PS
문제 진실을 알고 있는 사람이 파티에 오는 경우, 진실을 알고 있는 사람과 같은 파티에 왔던 사람이 다른 파티에 오는 경우, 거기에 있는 다른 사람이 참석하는 또 다른 파티의 경우 등이 존재하는 상황에서 지민이가 과장된 이야기를 할 수 있는 파티 수의 최댓값을 구하는 문제. 문제풀이 Union-Find 알고리즘으로 풀이 지민이가 과장된 이야기를 할 수 없는 사람들을 하나의 집합으로 구성 ffind 함수로 해당 원소의 parent 원소를 찾는다. union 함수로 진실을 아는 사람들과 그와 같이 파티에 오는 사람들(연쇄적)을 하나로 묶는다. - 입력받은 두 원소가 모두 진실을 아는 사람 -> 변화 X - 둘 중 한 원소가 진실을 아는 사람 -> 진실을 아는 사람을 부모로 갱신 - 둘 다 진실을 아는 사람이..
[BOJ/백준] 2160 그림비교 - 파이썬
·
💻 알고리즘/PS
문제 https://www.acmicpc.net/problem/2160 2160번: 그림 비교 N(2 ≤ N ≤ 50)개의 그림이 있다. 각각의 그림은 5×7의 크기이고, 두 가지 색으로 되어 있다. 이때 두 가지의 색을 각각 ‘X’와 ‘.’으로 표현하기로 하자. 이러한 그림들이 주어졌을 때, 가장 비 www.acmicpc.net 문제풀이 간단한 bruteforce 문제이다. 입력받은 그림을 하나씩 비교해서 각 원소가 같은 값인지 아닌지 확인한다. 가장 비슷한 두 그림(값이 다른 원소가 최소인 그림 두가지)의 번호를 출력한다. 코드 import sys input=sys.stdin.readline n=int(input()) pic=[] for i in range(n): pic.append(list([inp..
[2017 카카오코드 예선] 컬러링북 - 파이썬
·
💻 알고리즘/PS
문제 https://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 영역의 수와 가장 큰 영역의 넓이를 구하는 문제이다. 문제풀이 흔히 볼 수 있는 bfs 문제와 유사하다. que에 좌표를 넣고 que가 빌 때까지 move를 이용해 주위 좌표(상,하,좌,우)를 탐색하고, 동일한 값을 지닌 좌표는 que에 추가해주는 방식으로 탐색을 진행한다. 해당 좌표를 방문했다면 check 값을 바꿔주어 방문 체크를 해준다. bfs를 새로 실..
[BOJ/백준] 13302 리조트 - 파이썬
·
💻 알고리즘/PS
문제 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 문제풀이 1일권, 3일권, 5일권과 그에 따른 쿠폰을 사용해서 리조트 이용을 위한 최소 비용을 구하는 dp 문제이다. bottom-up 방식으로 각각 날에 대해 dp 값을 갱신해주었다. dp[day][coupon]으로 2차원 dp 배열을 선언해서 이용권에 따라 쿠폰 값도 갱신해주었다. 1일권 구매 dp[i+1][j]=min(result+10000 , dp[i+1][j]) 3일권 구매 dp[i+k][j..