본문 바로가기

전체 글207

[BOJ] 9370 : 미확인 도착지 문제 링크 9370번: 미확인 도착지 (acmicpc.net) 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 어느 부분에서 틀렸는지 감이 안와서 한참을 헤맨 문제였다. 풀이 처음에 나는 다익스트라 알고리즘 한 번으로 풀려고 시도했다. 다익스트라로 돌면서 지정된 도로를 지나가기 전에는 도착점에 false를 표기하고 지정된 도로를 지나간 후 부터는 true를 표기하기로 했다. 그렇게 해서 만약 최단거리로 목적지를 갔을 때 true라고 표기돼있으면 그 목적지는 유효한 것으로 판단 하려고 했다. 1 2 3 4.. 2022. 1. 24.

[BOJ] 1707 : 이분 그래프 문제 링크 1707번: 이분 그래프 (acmicpc.net) 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 처음 떠올린 내 아이디어는 이렇다. DFS를 이용해 탐색하면서 인접한 정점은 현재 내가 있는 정점과 다른 그룹에 정점 번호를 집어 넣는다. 그리고 그룹에 새로운 정점이 들어올 때 마다 같은 그룹에 있는 앞서 들어온 정점들과 인접한지 체크한다. 그렇게 짠 코드가 아래의 코드이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2.. 2022. 1. 21.

[BOJ] 1697 : 숨바꼭질 문제 링크 1697번: 숨바꼭질 (acmicpc.net) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 실버라고 만만하게 봤다 풀이 BFS를 활용한 문제. 앞으로 한 칸을 가든 뒤로 한 칸을 가든 순간이동을 하든 사용되는 시간은 동일하다. 큐를 만들어서 위치와 시간을 저장하려고 했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #de.. 2022. 1. 20.

[BOJ] 1579 : 앱 문제 링크 7579번: 앱 (acmicpc.net) 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 일단 내가 생각해낸 아이디어는 Cost 를 기준으로 오름차순 정렬한 다음 백트래킹으로 메모리를 더해가면서 메모리의 합이 M을 넘으면 그때의 Cost를 기존과 비교해서 최솟값을 저장하는 방식. 먼저 앱에 대해서 우리가 취할 수 있는 경우의 수는 1. 비활성화 한다 2. 그대로 둔다 두 가지 방법이 있다. 이를 바탕으로 백트래킹을 작성하면 아래의 코드가 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 1.. 2022. 1. 20.

[BOJ] 10942 : 팰린드롬? 문제 링크 10942번: 팰린드롬? (acmicpc.net) 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 팰린드롬이란 양쪽이 대칭을 이루는 것을 말한다. 예를 들면 12321 같은 것들. 최대 2000길이의 수열을 1000000회 동안 매번 팰린드롬인지 검사하면 0.5초의 시간으로 절대 부족하다. 그래서 palinedrome이라는 이차원 배열을 만들어 palinedrome[Start][End] 까지가 팰린드롬인지 아닌지 저장해뒀다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2.. 2022. 1. 20.

[BOJ] 6716 : Collecting Beepers 문제 링크 6716번: Collecting Beepers (acmicpc.net) 6716번: Collecting Beepers Karel is a robot who lives in a rectangular coordinate system where each place is designated by a set of integer coordinates (x and y). Your job is to design a program that will help Karel pick up a number of beepers that are placed in her world. To do so www.acmicpc.net 백트래킹이라고 소개되어있어서 풀어본 문제지만 딱히 백트래킹으로 풀리는 문제가 아니라서 백트래킹 문.. 2022. 1. 19.

[BOJ] 2629 : 양팔저울 문제 링크 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 풀이 백트래킹을 공부하다가 만난 문제다. 저울을 기준으로 생각했을 때 i번째 추를 처리하는 방법은 3가지가 있다. 1. 왼쪽에 놓는다 2. 오른쪽에 놓는다 3. 놓지 않는다 맨 처음 떠오른 아이디어가 이것이었으므로 이것을 기반으로 코드를 작성했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3.. 2022. 1. 19.

[BOJ] 2661: 좋은 수열 문제 링크 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 예전에 누군가의 코드를 따라치면서 대충 이해만 하고 넘어갔던 문제다. 이번에 다시 백트래킹을 풀어보면서 제대로 풀어보기로 했다. 백트래킹으로 string에 숫자를 하나씩 붙여나가는 방식으로 코드를 작성했다. 처음에 depth 1인 str은 '1'로 시작하는 백트래킹 함수를 호출했다. 그 이유는 좋은 수열중 가장 작은 수 이므로 맨 앞자리는 1일 것이다. 매 함수마다 지금까지 만들어진 수열이 좋.. 2022. 1. 19.

[BOJ] 1799 : 비숍 문제 링크 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 백트래킹에 관한 문제다. 풀이 처음 문제를 읽었을 때 왜 이게 골드1 난이도의 문제일까? 라는 의문이 들었다. 비숍이 들어갈 위치는 정해져있고 거기에 비숍이 1. 놓이거나 2. 안놓이거나 둘 중 하나다. 비숍이 놓일 수 있는 모든 위치를 벡터에 저장한 뒤 그 위치를 백트래킹으로 모두 돌면서 depth가 비숍이 놓일 수 있는 모든 칸의 개수와 같아지면 그때 체스판에 놓여있는 체스의 개수 중 최대값.. 2022. 1. 19.

이전 1 ··· 20 21 22 23 다음

티스토리툴바