www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 아이디어: 백트래킹과 DFS를 사용하여 구현하였다. 내가 이해한 방식이 맞는 지는 모르겠지만.. 일단 재귀함수로 구현하였고, pypy로 통과했다. 조건은 크게 어렵지 않았던 것 같다. 차근차근히 풀면 풀어졌다. 최댓값을 갱신하는 부분과, DFS에서 돌아온 후에 True를 다시 False로, cnt--를 해주는 것에 유의하자. (이 부분을 if문 밖에 써서 삽질을 했었다.) + 좌표 범위 체크하는 조건도!..
알고리즘💻
www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 아이디어: BFS 혹은 DFS로 그냥 그래프를 탐색하기만 하면 되는 간단한 문제이다. BFS는 큐를 사용해야 되니까 귀찮아서 DFS로 탐색했다. 이제 조금 DFS를 구현하는 게 익숙해진 것 같다. import sys N = int(sys.stdin.readline()) K = int(sys.stdin.readline()) graph = [[] for _ in range(N+1)] visit = [False]*(N+1..
www.acmicpc.net/problem/5829 5829번: Luxury River Cruise Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with N ports (1
www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net 아이디어: 큐를 두개를 사용하여서 루머를 믿는 사람을 저장하는 큐 A와 A의 인접한 노드들을 저장하는 큐 B로 나눈다. A의 요소들을 pop하면서 시간을 저장하고 해당 요소의 인접리스트를 B에 저장한다. A의 요소가 모두 비게 되면 시간이 +1되는 것이다. 그리고 B의 요소들을 pop하면서 루머에 감염되었는지 여부를 판단하고 감염된 노드만 A에 다시 추가한다. 처음에는 최..
www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 아이디어: 앞선 A->B 문제와 비슷한 방식으로 그래프를 구현하여 풀 수 있을 것 같다. 대신 이번 문제는 무조건 BFS로 풀어야 한다. 생각해야 할 조건이 많아서 예상외로 까다로웠다. 처음에 그냥 제출하니 메모리 초과가 났고.. 그래서 한 번 만든 수를 다시 만들지 않도록 visit 배열을 추가했다. 예를 들면 *2를 하여 이미 한번의 경로만을 사용하여 만든 수를 +1 두번을 사용하..
www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A *2 끝에 1을 추가 -> *10+1 A부터 시작해서 갈 수 있는 경우가 2가지밖에 없으니까 그 방향으로 BFS로 탐색하면서 B가 나오면 도달하기까지 간선의 개수+1를 출력한다. 큐에 [변해가는 A의 값, cnt]를 추가하면서 탐색을 진행하고, n[0]이 B보다 큰 경우에는 연결된..
www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 아주 기본적인 DFS, BFS 구현 문제이다. 백준 기록 보면 인접리스트로 푼 것과 인접배열로 푼 것 두 가지 방식을 확인할 수 있다. dfs를 구현하는 방식에는 재귀함수로 구현하는 방법과 스택을 이용하는 방법 두 가지가 있는데, 이 문제에서는 정점번호가 작은 순서대로 출력해야해서 재귀함수로 구현하는 방법이 더 나을 것 같아 그렇게 풀었지만, 코드는 일단 올려놓는다. (df..
www.acmicpc.net/problem/20002
www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 아이디어: 부분합을 이용하면 되지 않을까. 2k+1만큼의 길이를 더하면서 최댓값을 갱신한다.. 일단 ice배열을 1,000,000개씩 만들고, g와 x를 받으면서 ice[x]=g를 넣는다. 그리고 큐를 하나 만들어서 ice를 하나씩 추가하고 길이가 2k+1이 되면 하나씩 pop하고 다음 걸 더한다. 이때 최댓값을 갱신해준다. 간단한 문제인데.. 이렇게 막막하면 우짤꼬....ㅠㅠ #게으른 백곰 import sys from collect..
www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 아이디어: 주어진 수열을 돌면서 F(Ai) 배열을 채운다. 무식하게 풀어보자면.. 그냥 배열을 돌면서 다 비교할 수 있겠지만 그러면 O(n^2)이므로 시간초과가 날것이다.. 구글링을 해보니, 스택으로 조금만 생각하면 쉽게 풀 수 있었다. 일단 뒤에서부터 배열을 읽어나가는 게 핵심이다! 그리고 F[i]의 값을 스택에 push하되, 만약 현재 읽는 배열의 F[i]값이 스택의 top보다 작다면 NGF(i)는 스택의 top이 된다..
