본문 바로가기

백준107

[백준] 9012번 괄호 사용 언어 - Python3 9012번: 괄호 (실버4, 스택) 문제 ★스택 문제★ 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 정답 간단한 스택 문제 !! (내 코드 풀이) 열린 괄호를 스택에 넣어, 닫힌 괄호가 있으면 열린 괄호 한개를 빼주는 형태. 열린 괄호인 경우, 스택에 append / 닫힌 괄호인 경우, 스택에 pop 닫혔으나 스택에 아무것도 없는 경우 ans = False로 하여, 더이상의 for문을 진행하지 않고 break. 최종적으로 스택에 아무것도 안남아있고.. 2023. 1. 20.
[백준] 10773번 제로 사용 언어 - Python3 10773번: 제로 (실버4, 스택) 문제 ★스택 문제★ 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 정답 간단한 스택 문제 !! 스택을 활용해야 한다는 것을 알고, 문제를 풀어서 너무 쉽게 맞췄어요. 문제에 대해 아무런 정보가 없는 상태에서도 스택을 사용해야한다고 알게 될 때까지 열심히 파이팅! :) (내 코드 풀이) 스택의 "선입후출" 구조만 이해하면 되는 문제 # 정답 k = int(input()) stack = [] for i in ran.. 2023. 1. 20.
[백준] 14889번 스타트와 링크 사용 언어 - Python3 14889번: 스타트와 링크 (실버2, DFS 백트래킹 문제) 문제 ★백트래킹 문제, 삼성 SW 역량 테스트 기출 문제 ★ 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 다른 분들 답중에 가장 좋다고 생각하는 풀이법 2가지로 공부했습니다. 맨 아래에 링크를 올립니다! 1. 방문 여부에 따라 팀 지정하는 방법 1팀은 2팀이 방문하지 않은 곳, 2팀은 1팀이 방문하지 않은 곳으로 생각한다. visited[i]를 순차적으로 방문해서 visited를 True로 해.. 2023. 1. 20.
[백준] 14888번 연산자 끼워넣기 사용 언어 - Python3 14888번: 연산자 끼워넣기 (실버1, DFS 백트래킹 문제) 문제 ★백트래킹 문제, 삼성 SW 역량 테스트 기출 문제★ 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 다른 분들 답중에 가장 좋다고 생각하는 풀이법으로 공부했습니다. 맨 아래에 링크를 올립니다! 1. maximum, minimum 지정 결과값을 출력할 때 결과값은 항상 -10억보다 크거나 같고, 10억보다 작거나 .. 2023. 1. 19.
[백준] 2580번 스도쿠 사용 언어 - PyPy3 2580번: 스도쿠 (골드4, DFS 백트래킹 문제) 문제 ★백트래킹 문제★ 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 다른 분들 답중에 가장 좋다고 생각하는 풀이법으로 공부했습니다. 맨 아래에 링크를 올립니다! 1. 전체 숫자를 모두 확인하면 재귀함수가 너무 많이 필요하기 때문에 답을 구해야하는 0인 부분만 찾는다. zeros = [(i,j) for i in range(9) for j in range(9) if sudoku[i][j.. 2023. 1. 19.
[백준] 9663번 N-Queen 사용 언어 - PyPy3 9663번: N-Queen (골드4, DFS 백트래킹 문제) 문제 ★백트래킹 문제★ 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! (아래 그림 참고) 1. DFS nqueen() 행(x)이 고정되어 있을 때 열(i)를 하나씩 증가시켜준다. (0,0) -> (0,1) -> (0,2) -> (0,3) 조건을 만족해서 퀸을 두려고 한다면, row[x] = i 로 (x,y)에 퀸의 위치를 저장해야한다. 모든 열에 테스트를 완료했으면, 행을 한개 증가시켜 다시 .. 2023. 1. 19.
[백준] 2339번 석판 자르기 사용 언어 - Python3 2339번: 석판 자르기 (골드1, DFS 백트래킹 문제) 문제 ★분할 정복 문제★ 2339번: 석판 자르기 첫 번째 줄에는 석판의 크기 N(1 ≤ N ≤ 20)이 들어온다. 다음 줄부터 N줄에 걸쳐서 석판의 상태가 입력으로 들어온다. 여기서 1은 불순물을 의미하며, 2는 보석 결정체, 0은 불순물과 보석결정체가 www.acmicpc.net 정답 석판을 자를 수 있을 때까지 분할하는 "분할 정복" 알고리즘 (백준에서 정답자의 풀이를 보고 이해했습니다) x의 start, end 범위 설정 sx, ex y의 start, end 범위 설정 sy, ey #정답 def f(sx, sy, ex, ey, hv): noise = [] #불순물 dia = 0 #보석결정체 for i in ra.. 2023. 1. 18.
[백준] 15652번 N과 M(4) 사용 언어 - Python3 15652번: N과 M(4) (실버3, DFS 백트래킹 문제) 문제 ★LG CNS 21년 상반기 코테랑 유사★ 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 15649,15450,15651,15652번은 세트로 공부 아래 백트래킹 문제 링크를 첨부합니다. 15450번과 15652번을 적절히 조합하는 문제이다. 중복을 제거하는 if문을 없애고, start 지점을 활용한다. 현재 i가 ans에 있을 때, i부터 N까지를 for문으로 차례.. 2023. 1. 18.
[백준] 15651번 N과 M(3) 사용 언어 - Python3 15651번: N과 M(3) (실버3, DFS 백트래킹 문제) 문제 ★LG CNS 21년 상반기 코테랑 유사★ 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 15649,15450,15651,15652번은 세트로 공부 아래 백트래킹 문제 링크를 첨부합니다. 중복도 허용하는 모든 가능한 수열을 뽑는 문제이다. 15651번에서 중복이 가능하게만 해주면 된다. if i not in ans: 제거 # 정답 N, M = map(int,input.. 2023. 1. 18.
[백준] 2667번 단지번호붙이기 사용 언어 - Python3 2667번: 단지번호붙이기 (실버1, DFS 문제) 문제 ★코테 자주 등장하는 DFS 문제★ 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 정답 DFS 재귀함수 (정답 풀이) 1. dfs 함수 정의 1.1. 1 값인 x,y 좌표 찾기 x,y가 N*N 정사각형 범위 안에 없다면 return해준다. N*N 정사각형 범위 안에 속해있다면, 1이 있는 좌표 x,y를 찾는다. 개수를 한개씩 더해주면서 1이 있는 총 개수를 카운트한다. (count+=1) 방문한 좌표는 0으로 만들어 방문했다.. 2023. 1. 17.

티스토리툴바