본문 바로가기

전체 글

 (113)
[BOJ][Python] 백준 11403번 - 경로 찾기 문제 링크: https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 플로이드 와샬로 풀은 문제이다. 최단경로를 구하는건 아니지만, N의 범위가 작다면 경로가 있는지 확인해볼 수 있다. 간단하게 i, j로 가는 거리를 1이라고 해놓고 최단거리를 구한다. 출력할 때 INF라면 0을, 아니라면 1을 출력해주면 된다. 코드
[BOJ][Python] 백준 15711번 - 환상의 짝꿍 문제 링크: https://www.acmicpc.net/problem/15711 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 문제 풀이 A와 B의 범위가 너무 커서 에라토스테네스의 체를 이용을 망설였는데, 2백만 까지 돌려도 충분히 가능하다고 한다. 일단 A+B가 짝수인 경우와 홀수인 경우를 확인해야 한다. 소수는 기본적으로 2를 제외한 모든 소수는 홀수이다. 그리고 4 이상인 경우만 가능하다. 소수 중 가장 작은 수는 2인데, 2+2가 4이기 때문이다. (1은 소수가 아니다.) 1. 짝수인 경우 - p + q..
[BOJ][Python] 백준 6118번 - 숨바꼭질 문제 링크: https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2
[BOJ][Python] 백준 15728번 - 에리 - 카드 문제 링크: https://www.acmicpc.net/problem/15728 15728번: 에리 - 카드 첫째 줄에 N, K(0 ≤ K < N ≤ 100)가 주어지고 둘째 줄에는 N개의 ‘공유 숫자카드’에 적혀 있는 정수, 셋째 줄에는 N개의 ‘팀 숫자카드’에 적혀 있는 정수가 주어진다. 이 수는 -10,000보다 크거나 www.acmicpc.net 문제 풀이 처음에는 우선순위 큐로 풀려했다가 N과 K의 범위가 작아서 브루트 포스로 풀었다. 전부 확인해서 곱이 가장 큰 팀 카드들을 뽑았다. set()을 이용해서 원소를 뽑는데 remove를 이용했다. O(1)로 없앨 수 있기 때문에 시간단축에 도움이 된다. 코드
[BOJ][Python] 백준 16917번 - 양념 반 후라이드 반 문제 링크: https://www.acmicpc.net/problem/16917 16917번: 양념 반 후라이드 반 현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다. 양념 치킨 한 마리의 가격은 www.acmicpc.net 문제 풀이 최소한으로 먹는 경우는 2가지가 있다. 첫 번째는 반반치킨으로 먼저 시키고 남은 치킨을 사는 방법이 있다. 일단 반반치킨이므로 한 번 시킬때 반마리이므로 2번 사야 1마리이다. 이 부분을 체크해주자. 두 번째는 그냥 모두를 반반치킨으로 시켜버리는 거다. 반반치킨을 시킬경우 극도로 싼 경우가 있어서 그렇다. 첫 번째 방법은 정말로 최소 마리로 시켰고, 두 번째는 후..
[BOJ][Python] 백준 17403번 - 가장 높고 넓은 성 문제 링크: https://www.acmicpc.net/problem/17403 17403번: 가장 높고 넓은 성 첫 번째 줄에 n개의 정수 x1, x2, ..., xn을 공백으로 구분하여 출력한다. xi는 i 번째 표지판이 사용되었을 경우 사용된 층수이며, 사용되지 않았으면 0이다. www.acmicpc.net 문제 풀이 볼록 껍질 문제이고, 감옥 건설(2254번) 문제에서 볼록 껍질을 계속 만들고 점 없애는 로직은 같다. 단지, 그 볼록 껍질이 몇 층인지 표기해야 하는데 점을 입력받을 때 인덱스도 같이 받으면 문제없이 해결 가능하다. 볼록 껍질을 계속 만들 때 반복문이 끝나는 경우는 2가지가 있다. 1. 볼록 껍질을 만들기 위한 점이 2개 이하이다. 2. 볼록 껍질을 만드는 과정이 끝났는데 볼록 껍질..
[BOJ][Text] 백준 20095번 - Sudoku 2 문제 링크: https://www.acmicpc.net/problem/20095 20095번: Sudoku 2 Fereydun, the legendary Persian hero whose prophecy was to overcome Zahhak, believes that he needs a powerful mind together with a powerful body. He has just learned a new brain teaser, called Sudoku, from a Japanese trader. Sudoku is played on a board t www.acmicpc.net 문제 풀이 이번에는 3*3 스도쿠이다. 이 역시 자필로 풀었으며, 코딩으로 답을 찾으려면 백트래킹으로 풀 수 있고, ..
[BOJ][Text] 백준 20094번 - Sudoku 1 문제 링크: https://www.acmicpc.net/problem/20094 20094번: Sudoku 1 Fereydun, the legendary Persian hero whose prophecy was to overcome Zahhak, believes that he needs a powerful mind together with a powerful body. He has just learned a new brain teaser, called Sudoku, from a Japanese trader. Sudoku is played on a board t www.acmicpc.net 문제 풀이 스도쿠를 푸는 문제. 2*2 스도쿠라 어렵진 않다. 입력으로는 밑의 사진 딱 1개만 나온다. 빈칸은 정확히..

티스토리툴바