시냅스

https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 백트래킹을 이용하여 풀었다. 부등호들은 brackets라는 배열로 관리하였고, dfs로 체크하는 동안 check_up이라는 함수를 통해 부등호가 만족하는지 확인하였고, 만족하는 것들은 배열에 담아두었다가 dfs가 끝나면 맨 처음 것과, 마지막 것을 출력해주었다. code n = int(input()) brackets = list(input().split()) visited = [0] * 10 ans = [] ..

https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 브루트포스와 백트래킹을 활용하여 풀었다. 가능한 조합을 모두 뽑아줘야 했지만, 시간제약의 관계로 dfs를 돌릴 때 for문을 쓰지 않는 방법으로 접근하였다. 조합을 뽑아 냈으면 start와 link로 나눠 차이를 구하고, 최소값을 갱신해줬다. code n = int(input()) stats = [list(map(int, input().split()))..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 다이나믹 프로그래밍을 통해 해결하였다. 다만, 문제를 풀면서 고려해야할 조건이 2가지인데, 최대값과 일자를 고려하여야 했다. 주어지는 일자를 넘어가면 안 되는데, 이를 위해 for문을 역순으로 돌렸다. 값을 구할 때에 뒤에서부터 더해질 수 있는 최대값을 구해나가고, 일자를 벗어난다면 전의 결과를 저장함으로써 0번째 인덱스에 최대값을 도출할 수 있게 했다. code total = int(input()) days =[] cost = [] dp = [] for i in range(total): n, m = map(int, input().s..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹을 이용한 문제였다. 주어지는 6개의 문자 중에 4개를 뽑아 조합해야 하는데, 문자 4개 중 최소 2개는 자음, 1개는 모음이 되어야 한다. 백트래킹을 통해 모든 가능성을 체크하면서, 모음을 포함하는지에 대한 여부와 자음을 2개 이상 포함하는지에 대한 여부를 함수로 판단하였고, 위 조건에 만족되는 경우에만 출력 할 수 있게 해주었다. code vowel = ['a', 'e', 'i', 'o', ..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 이용하는 기본 문제였다. 다만, 중복에 관한 제약조건들이 있었는데 자기 자신을 출력하면 안되고, 이미 출력한 조합은 다시 출력해서는 안 된다. 자기 자신에 대한 여부는 visited 라는 배열로 관리하였고, 이미 출력한 것에 대한 여부는 printed 라는 배열을 통해 출력한 것들을 저장하여 비교해주었다. code n, m = map(int,input().split()) input_l..

https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 이어서 쓰인 수의 length 값을 구하는 문제였다. 물론, 시간초과를 한 번 맛본 후 반복문을 쓰지 말아야겠다 하고 생각했던 풀이법은 한자리 수인, 1 ~ 9 의 총 합은 9 두자리 수 까지인, 1 ~ 99 의 총 합은 189 세자리 수 까지인, 1 ~ 999 의 총 합은 2889 로 규칙성을 찾아 내었다. 이후에는 각 자리수의 총합에서 입력받은 수 까지의 차이를 빼 결과값을 나타내었다. code n = input() every_nineth = str(len(n) - 1) + ('8' * (len(n) - 1)) ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 각 숫자에 대해 1, 2, 3 으로 이뤄진 경우의 수를 모두 찾는 문제였다. 만약 n > 3 이라면, 수식은 f(n) = f(n - 3) + f(n - 2) + f(n - 1) 로 세울 수 있다. dynamic programming 을 통해 문제에서 제시한 10 이하까지 결과값을 미리 구해둔 뒤, 입력받아 출력해주었다. code dp = [1, 2, 4] for i in range(3, 10): dp.append(dp[i - 3] + dp[i - 2] + dp[i - 1]) t = int(inp..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 현재 채널을 기준으로 고장난 버튼을 제외한 버튼을 눌러 최소한으로 목표 채널까지 도달하는 문제였다. 5457의 경우 5455 혹은 5459 에서 2번을 ++하거나 --하여 이동하는 것으로 5455(4) + ++ (2)로 총 6이다. 현재 채널의 경우, 100으로 만약 100이 목표채널로 설정되면 그냥 0을 출력, 또 고장난 버튼이 없다면 목표채널의 길이값을 출력해주면 된다. 브루트..

https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 문제는 진수를 달리하는 각 숫자들에 대해 10진수로는 몇 년도인지를 나타내라는 문제였다. 다만 그것들에 대한 나머지만 주어지기 때문에 브루트포스를 이용하여 년도를 계속 더해주는 방식으로 풀이했다. code e, s, m = map(int, input().split()) # 각각 15, 28, 19 일때는 나머지가 0 이기때문에 치환해줬다. if e == 15: e = 0 if s == 28: s = 0..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 브루트포스를 활용하여 문제를 해결하였다. 문제 제한 시간이 1초라 시간초과에 유의했으나, 애초에 입력값이 작아 o(n^4) 되는 나의 솔루션도 문제가 없는 것 같다. 풀이는 입력값을 받은 배열에 있는 모든 원소를 가로로 한 번 교체하여 최대값을 확인하고, 세로로 한 번 교체하여 최대값을 확인하였다. 다만 교체한 후에는 원상복귀하여 배열에 이상이 없게 해야했다. 그렇게 도출된 cnt와 result를 비교하여 더 큰 값을 결과값으로 도출하였다. 파이썬의 스왑은 언제나 감동적이다... code n = int(input(..