song — song

[swea 4615-파이썬]재미있는 오셀로 게임

2023.06.21

swea 4615 재미있는 오셀로 게임 사용언어 : PYTHON 풀이 방향벡터를 이용하여 모든 방향을 백트래킹 하며 조건에 부합하면 돌의 색상을 변경한다. ( 백트래킹이 맞는건가..? ) 조건에 부합한다는 말은 WBBBW 혹은 BWWWWWB와 같은 경우이다. 백트래킹 방향 벡터가 가리키는 방향 한 칸 앞의 색상이 현재 색상과 다르면 flag변수를 1로 바꾸고 한 칸 앞의 색상을 현재 색상으로 변경하고 백트래킹 함수를 수행한다. 이때 변경하기 전 색상을 변수에 저장해두어야 한다. 만약 조건에 부합하지 않는다면 원상복구 해야하기 때문이다. flag변수 : 2 1 1 1 2 와 같이 한 숫자가 다른 숫자를 감싸는지 확인하기 위해 필요한 변수이다. 재귀함수로 호출한 check()함수가 False를 리턴한다면 조..

📂코딩테스트:CodingTest

[swea 1216-파이썬]회문2

2023.06.21

swea 1216 회문2 사용언어 : PYTHON 풀이 시간복잡도를 줄이기 위해 길이가 1인 문장부터 오름차순으로 100까지 검사하는 것이 아닌 100부터 내림차순으로 검사를 해야한다. 내림차순으로 검사를 수행하다가 그 문장이 회문이 맞다면 가장 긴 회문이 되기 때문이다. 행 방향으로 가장 긴 회문의 길이와 열 방향으로 가장 긴 회문의 길이 중 더 큰 값이 정답이 된다. 총 세 개의 함수를 이용하였다. 회문인지 확인하는 check함수 행 방향으로 탐색하는 find_row함수 열 방향으로 탐색하는 find_col함수 (함수 안에서 find_row를 호출하고 크기를 비교한 뒤 최종 정답을 return함) 코드 def check(st): for i in range(len(st)//2): if st[i]!=st..

📂코딩테스트:CodingTest

[swea 2814-파이썬]최장 경로

2023.06.21

swea 2814 최장 경로 사용언어 : PYTHON 풀이 무방향 그래프에서 최장 경로의 길이를 구해아 한다. 최장경로는 그래프의 정점들 중 더 이상 이동할 수 없을때 까지 탐색한 경로 길이 중 가장 큰 값이다. 더 이상 이동할 수 없을때 까지 탐색하기 위해 dfs를 활용하였다. 1.우선 입력이 연결된 간선들로 주어지기 때문에 이들을 2차원 행렬로 정리해서 그래프로 표현하였다. 👇 for _ in range(M): l.append(list(map(int,input().split()))) # 입력으로 주어지는 연결된 간선 for j in l: # 2차원 행렬의 그래프로 표현 graph[j[0]].append(j[1]) graph[j[1]].append(j[0]) 2.다음으로 모든 정점들을 돌아가며 dfs를..

📂코딩테스트:CodingTest

[swea 1244-파이썬][S/W 문제해결 응용] 2일차 - 최대 상금

2023.06.21

swea 1244 [S/W 문제해결 응용] 2일차 - 최대 상금 사용언어 : PYTHON 풀이 구현을 위한 생각 백트래킹을 사용하여 모든 경우를 중복없이 탐색한다. 모든 경우를 탐색하며 goal(주어진 숫자를 내림차순으로 정렬한 값)과 차이가 가장 작은 값이 정답이다. 💡 goal : 이동횟수 제한이 없다고 할 때, 숫자를 swap해서 도달할 수 있는 최대값은 내림차순으로 정렬한 값이다. 백트래킹 숫자카드 1,2,3,4가 있다고 할 때 두 번 교환할 수 있는 모든 경우는 위 그림과 같다. (x표시는 중복되는 경우) 바로 직전에 교환한 경우보다 뒤의 경우만 조회하면 중복없이 교환할 수 있다. 바로 직전에 교환한 경우를 기억하기 위해서 stack을 활용하였다. 코드 def backTracking(m): gl..

📂코딩테스트:CodingTest

[백준 14500번-파이썬]테트로미노

2023.06.20

백준 (BOJ) 14500 https://www.acmicpc.net/problem/14500 사용언어 : PYTHON 1.문제 2.풀이 브루트포스 알고리즘을 사용하는 문제이다. ( 다른 풀이를 추가하였습니다) 시간제한은 2초인데 1억=1초의 룰에 대입했을때 2천8백만이 나오므로 브루트포스 알고리즘을 사용해도 된다. 499*499*19*6 = 28,386,114 회전 또는 대칭으로 만들 수 있는 모든 테트로미노를 1과 0의 배열로 만든다. 19개의 테트로미노들을 돌아가며 종이의 모든 배치 가능한 구역에 배치한다. 그리고 모든 배치중에서 최댓값을 찾는다. 이 문제를 통해서 연산이 복잡해 질 때는 함수를 사용하여 복잡한 연산들을 분할하면 좀 더 쉽게 구현할 수 있음을 알게되었다. 3.코드 import sys..

📂코딩테스트:CodingTest

[백준 1107번-파이썬]리모컨

2023.06.20

백준 (BOJ) 1107 https://www.acmicpc.net/problem/1107 사용언어 : PYTHON 1.문제 2.풀이 2-1. 시도했다가 실패한 풀이 N : 5457 M : 3 고장난 버튼 : [5,7] 이면 입력이 가능한 버튼들은 [0,1,2,3,4,5,6,8,9]이다. 5457의 첫 번째 숫자 5가 없으므로 첫 번째 숫자를 4 혹은 6을 입력하는 것이 최소로 이동할 수 있는 수가 될 것이다. 이 때 4를 입력한 경우는 뒤에 숫자를 최대한 큰 수로 입력해야 하고, 6을 입력한 경우는 최대한 작은수를 입력해야 한다고 생각하여 문제를 풀고자 했다. 2-2. 올바른 풀이 브루트포스 알고리즘 0 ~ 999899+1 까지 리모컨으로 입력할 수 있는 모든 숫자들을 비교하며 최솟값을 찾는다. N의 ..

📂코딩테스트:CodingTest

[백준 11053번-파이썬]가장 긴 증가하는 부분 수열

2023.06.20

백준 (BOJ) 11053번 https://www.acmicpc.net/problem/11053 사용언어 : PYTHON 1.문제 2.풀이 A={10,20,10,30,20,50}을 예로 들어 생각해보았다. dp[i] = A[0], A[1], ... A[i] 일때 '증가하는 부분 수열'에서 A[i]의 위치(인덱스)값 이다. i=0 일 때 dp[0]는 A[0] 즉 10의 '증가하는 부분 수열'={10} 에서 위치 즉 1 이다. i=1 일 때 dp[1]는 A[1] 즉 20의 '증가하는 부분 수열'={10,20} 에서 위치 즉 2 이다. i=2 일 때 dp[2]는 A[2] 즉 10의 '증가하는 부분 수열'={10,20} 에서 위치 즉 1 이다. i=3 일..

📂코딩테스트:CodingTest

[백준 11052번-파이썬]카드 구매하기

2023.06.20

백준 (BOJ) 11052번 https://www.acmicpc.net/problem/11052 사용언어 : PYTHON 1.문제 2.풀이 최적해(최댓값)을 구하는 문제이므로 다이나믹 프로그래밍을 사용하여 풀 수 있었다. 최적해의 일부분이 그 부분에 대한 최적해가 DP 순환식을 세우는 출발점임을 생각했다. N이 4이고 P1=1, P2=5, P3=6, P4=7인 경우 최댓값 = max(P4를 선택하지 않은 경우, P4를 선택한 경우)이다. 이때 P4를 선택하면 N의 갯수를 모두 채우기 때문에 P4하나만 살 수 있다. 따라서 max{(P1,P2,P3)의 조합을 이용해서 4를 만들 수 있는 최댓값, 7}이 된다. 위 최적해의 일부분 (P1,P2,P3)의 조합을 이용해서 4를 만들 수 있는 최댓값 = (P3를 ..

전체 글

[swea 4615-파이썬]재미있는 오셀로 게임

[swea 1216-파이썬]회문2

[swea 2814-파이썬]최장 경로

[swea 1244-파이썬][S/W 문제해결 응용] 2일차 - 최대 상금

[백준 14500번-파이썬]테트로미노

[백준 1107번-파이썬]리모컨

[백준 11053번-파이썬]가장 긴 증가하는 부분 수열

[백준 11052번-파이썬]카드 구매하기

티스토리툴바