본문 바로가기

⭐ Problem_Solving44

[백준] 17070 파이프 옮기기1 (Python/파이썬) https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 1. 2차원 배열에서 도착지까지의 경로의 개수를 찾는 유형의 DP 문제이지만 N의 범위가 작아 BFS로도 풀 수 있습니다. 2. 저는 DP로 풀었으며 테이블은 각 좌표마다 해당 좌표를 끝점으로 하는 파이프가 놓일 수 있는 경우의 수를 각 방향(가로, 세로, 대각선)에 대해 계산한 배열로 정의했습니다. 3. 해당 좌표와 직전 좌표의 벽 여부를 검사하면서 테이블을 채워 나가면.. 2023. 4. 4.

[SWEA] 1868. 파핑파핑 지뢰찾기 (Java / 자바) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 최소로 클릭을 구해야 하므로 주변에 지뢰가 없는(카운트 0) 위치를 먼저 다 누르고 남은 위치를 눌러주면 된다. 2. 해당 위치가 주변에 지뢰가 없는 곳인지 확인하는 메서드를 만들어서 완전탐색을 통해서 해당 위치가 주변에 지뢰가 없는 곳이면 bfs로 주변을 밝혀준다. 3. 남은 곳들(주변에 지뢰가 있는 곳)은 눌렀을 때 자신만 밝혀지는 곳이므로 그냥 완전탐색으로 개수를 세주면 된다. 4. vi.. 2023. 2. 15.

[SWEA] 1767. 프로세서 연결하기 (Java / 자바) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제에 제시된 N의 개수와 프로세서 최대 개수가 12로 작은 편이기에 완전탐색으로 충분히 풀 수 있다. 2. 해당 프로세서의 연결 가능 여부를 검증하는 함수를 만들고 백트래킹으로 모든 프로세서를 선택/비선택하면서 4방향으로 연결 가능 여부를 검증했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputS.. 2023. 2. 13.

[프로그래머스] 퍼즐 조각 채우기 (Python/파이썬) https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 전략은 크게 1. 블럭 모양과 빈공간을 추출해서 + 2. 둘을 비교한다 두 과정이다. 2. 블럭 모양과 빈공간 추출은 bfs로 추출해서 모양의 인덱스를 저장한다. 3. 둘 간의 비교가 어려운데 나같은 경우는 둘 간의 1:1 매칭을 위해 인덱스를 가장 작은 좌표를 뺴줌으로서 (0, 0)기준으로 재비치하고, 시계방향으로 90, 180, 270도 회전해가면서 최솟값만을 저장해 모양들을 nor.. 2023. 2. 11.

[프로그래머스] 여행경로 (Python/파이썬) https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 나는 별 생각없이 백트래킹으로 풀어서 통과했는데 다른 사람들 풀이 보니까 역순으로 dfs 한 번만에 푸는 풀이가 있어서 둘 다를 소개한다. 2. 백트래킹은 그냥 반환 조건을 잘 설정해서 백트래킹 함수를 구현하면 어렵지 않다. 3. DFS 풀이는 조금 특이한데 출발지가 'ICN'으로 고정되어있고 반드시 모든 도시를 여행할 수 있는 경로가 주어진다는 점을 이용해서 출발지를 고정하고 경로를 복원하.. 2023. 2. 10.

[프로그래머스] 순위 (Python/파이썬) https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 언뜻 보면 위상정렬 같아 보이는데 순위가 확정된 선수들의 순위만 반환해야하므로 위상정렬로는 풀 수 없다. 2. 플로이드-와샬로 푼 사람들도 많았는데 그냥 dfs로 푸는 게 더 간단하다 3. 순위가 확정되어있다는 것은 자신의 위(자신 기준 승자)와 아래 (자신 기준 패자)를 모두 안 다는 것이므로, 승자와 패자 그래프 2개를 만들어서 각각에 대해 dfs를 적용해서 파악된 승자와 패자의 합이 자.. 2023. 2. 9.

이전 1 2 3 4 5 ··· 8 다음

티스토리툴바