문제 https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 풀이 문제 이해부터 하자면, 2-친구라고 말해서 좀 복잡한데 그냥 A-B가 친구이거나 / A-B가 친구가 아니여도 A, B에게 C라는 공통된 친구가 있으면 A-B가 친구가 된다. (A-C, B-C친구 -> A-B친구) 이 문제에는 다양한 풀이법이 있다. 아무래도 n이 최대 50이라 완전탐색, O(n^3)에도 문제 해결이 가능하다. BFS :여기 정리가 잘 되어있는데 나는 잘 이해가 안된다ㅠ.ㅜ ..
문제 https://www.acmicpc.net/problem/1987 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 풀이 왜 시간초과가 날까 DFS 연습하려고 고른 문제인데 DFS로 풀면 시초 뜬다.. 솔직히 BFS가 더 쉬울 것 같긴하고, 시초도 안뜰 것 같다. 그리고 dx,dy순서에 따라 시초 나는지 안나는지도 결정되니까 아무리 생각해도 DFS로 완탐하는 문제는 아닌 것 같다. pypy3로 해야 통과되기도 하고.. 코드 n,m = map(int,input().split()) arr = [list(map(str,input())) for _ in range(n)] dx = [-1,..
문제 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 LG 기출이랑 비슷하다. #17298과 비슷하게 stack + 그리디.. 하지만 값 출력하기 편하게 stack이 아닌 deque를 사용했다. 문자열의 이전 값들이 더 작으면 pop을 계속 해주고 k값을 감소한다. 72%정도에서 계속 틀렸습니다가 떴는데, 마지막 출력하는 과정에서 dq.size()-k을 꼭 해줘야했다. 그냥 auto써서 dq다출력하는게 아니라.. k를 빼줘야하는 이유는 뭘까..? 5 1 76543 의 예시를 생각해보자. k가 0보다 크고 dq도 비어..
문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 이진 탐색을.. 완전히 이해하고 싶었다. 간단한 문제인줄 알았는데 난관을 많이 만나버렸다.. 일단, Test case로 2 10 3 9 가 주어진다면 답이 0이 아니라 1이 되어야한다. 즉 처음 시작할 때 start값을 1로 세팅해주어야 한다. 그리고.. 시간초과가 자꾸 나서 뭐가 문제인지 찾아보다가.. for문 사용 방식에 있어서 1번으로 하니 ..
문제 https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 풀이 BFS로 풀었다. 우선 전체 배열을 탐색하며 방문한 적이 없다면 제일 높은 건지 확인하기 위해 해당 위치에서 BFS를 시작한다. check라는 변수를 통해 인접 지역 중 해당 위치가 가장 높을지 안높을지 체크한다. 높으면 0, 안높으면 1을 반환했다. 큐에 해당 위치를 넣어주고, 8개를 돌며 인접한 곳을 모두 탐색하는데 이때 다음 탐색할 곳의 높이가 현재 ..
문제 https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 vis배열을 삭제해 주며 나머지는 위와 동일하다. 코드 import sys read = sys.stdin.readline n, m = list(map(int, read().split())) num = list(map(int, read().split())) #입력받은 수 저장 arr = [0 for _ in range(m)] num.sort() def choose(k): if (k =..
문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 코드에 주석으로 다 써놨다.. 문제에 약간 논란이 있는 듯 한데, 문제 이해가 관건이다. 파이썬은 위대하다.. rotate랑 count를 처음 써봐서 신세계였던 문제 코드 import sys from collections import deque read = sys.stdin.readline n, k = map(int, input().split()) belt = de..
문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 기본 BFS 문제이다. 상하좌우가 아닌, 나이트가 이동할 수 있는 좌표를 탐색한다. dx,dy만 잘 설정해주면 된다. 거리를 계산해서 배열에 저장하고, 목적지에 저장된 거리를 출력하면 된다. 코드 import sys from collections import deque read = sys.stdin.readline T = int(read()) dx = [2,1,-1,-2,-2,-1,1,2..
문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 설명 자바로 dfs를 구현하는 것은 처음인데, 이때 ArrayList를 활용했다. ArrayList를 배열형태로 만들어서 인접리스트를 구현하였다. 우선 인접 리스트를 초기화 한 뒤, 인접 리스트에 그래프를 저장한다. 이때 양방향이기 때문에(방향이 없는 그래프) a[s].add(e)와 a[e].add(s)를 둘 다 추가해 주었다. 방문하지 않은 경우 카운팅을 하고 dfs를 재귀 방식으로 호출한다. ..
https://www.acmicpc.net/problem/9742 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 백트래킹을 사용한 문제. 테케 갯수가 정해져 있지 않기에 읽은 라인이 null일때까지 반복 package algo0314; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class B9742_순열 { static..