'🥇코딩테스트:Algorithm' 카테고리의 글 목록 (5 Page)

[swea 1868-파이썬] 파핑파핑 지뢰찾기

2023.06.22

사용언어 : PYTHON 풀이 1. 행 우선 방향으로 탐색을 진행하다 0인 곳을 만나면 BFS를 수행(연쇄적으로 클릭)하며 정답(ans)를 1증가 이때 0으로 인해 연쇄적으로 클릭된 곳을 -로 표시 2. 행 우선 방향으로 다시 탐색하며 연쇄적으로 클릭되지 않은 곳의 갯수만큼 정답(ans)에 추가 코드 import sys from collections import deque input = sys.stdin.readline # SWEA 파핑파핑 지뢰찾기 # 1. 전체를 탐색하다 0을 만나면 BFS 수행 (방문체크), cnt += 1 # 2. 체크 되지 않은 칸 세기 def click(r, c): # 클릭을 수행하고(중복 클릭은 수행하지 않음), 0이면 True를 리턴하는 함수 if arr[r][c] == '..

🥇코딩테스트:Algorithm

[swea 3304-파이썬]최장 공통 부분 수열

2023.06.21

swea 3304 최장 공통 부분 수열 사용언어 : PYTHON 풀이 우선 최적해(최댓값)을 구하는 문제이기 때문에 다이나믹 프로그래밍을 사용하여 풀 수 있다. 순환식(점화식)을 세울때는 "최적해의 일부분이 그 부분의 최적해" 를 생각해야 한다. 이 문제 같은 경우는 두 문자열의 마지막 문자가 같은 경우와 다른 경우를 생각하여 순환식을 세워야 한다. (DP(i,j)에서 i와 j는 문자열 X와 Y의 1...i, 1...j 번째까지의 문자열) (1) 두 문자열의 마지막 문자가 같은 경우 예를들어 CDABE와 CDE라고 가정해보면 마지막 문자 E가 같다. E는 최장 공통 부분수열에 반드시 포함된다. 따라서 최장 공통 부분수열의 길이는 두 문자열의 마지막 문자 E를 제거한 후 찾은 최장 공통 부분수열의 길이 +..

🥇코딩테스트:Algorithm

[swea 3307-파이썬]최장 증가 부분 수열

2023.06.21

swea 3307 최장 증가 부분 수열 사용언어 : PYTHON 풀이 백준에서 한 번 풀이를 했던 문제였다 dp를 사용해서 풀어야 하는데 점화식을 어떻게 세워야 할 지 잘 생각이 나지 않았다. 왜 점화식을 세우지 못했는지 풀이를 보고 알았다. 이 문제는 0~n까지 차례대로 dp리스트를 채운뒤 dp[n-1]이 정답이 되는것이 아닌 max(dp)가 정답이기 때문이었다. dp[i] 는 l[i] (입력으로 받는 수열) 를 사용했을 때 생성될 수 있는 최장 증가 부분 수열의 길이이다 0

🥇코딩테스트:Algorithm

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

2023.06.21

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

🥇코딩테스트:Algorithm

[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..

🥇코딩테스트:Algorithm

[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를..

🥇코딩테스트:Algorithm

[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..

🥇코딩테스트:Algorithm

[백준 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..

티스토리툴바