본문 바로가기

algorithm50

[백준] 2580.스도쿠 / BackTracking @BackTracking / 1h 4m 40분만에 풀었는데 시간초과 떠서 그거 잡느라 좀 오래 걸림 문제 링크 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 구현 포인트 원래 check라는 함수를 두고 모든 칸을 다 채운 후 가로줄, 세로줄, 3*3칸에 중복되는 숫자가 없을 때에만 맵을 출력하고 종료하게 했다. 그런데 이 중복체크를 안 해도 풀린다! 1. 3차원 visit 사용하기 visit[행][열][1부터 9까지의 값] 으로 그 칸에 들어.. 2020. 9. 8.
[백준] 9663.N-Queen / BackTracking @BackTracking / 1h 나이트랑 헷갈려서 바보짓 하고.. 이후에 이전 코드 보고 다시 풀었음 ㅜㅜ 문제 링크 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 참고 자료 퀸의 공격 범위 : 수직, 수평선 및 대각선 4방향 즉, 아래에서 검은색으로 표시된 칸에는 다른 퀸을 놓을 수 없다. 출처 : http://blog.daum.net/tomayoon/7089880 구현 포인트 처음에 visit 표시를 어떻게 하지 고민이 많았다 만약 단순히 backTra.. 2020. 9. 6.
[백준] 10971.외판원 순회 2 @BackTracking / 28m (생각, 필기 20분) 알고리즘 쉰지 너무 오래돼서.. 이거 뭘로 풀어야하지 크루스칼인가.. 멍때리다가 생각하다가 떠올림 문제 링크 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 방법 1. 시작점으로 다시 돌아와야 한다 -> 즉, 어떤 점에서 출발하든 상관 없다 라는 의미임 예를 들면 1->2->3->4->1로 가는 경로라면, 2->3->4->1->2도 같은.. 2020. 9. 6.
[백준] 18809.Gaaaaaaaaaarden / BFS, 조합 @BFS, 조합 / 1h 16m (필기 12m, 디버깅 29m) 다 풀었는데 계속 틀리게 나와서 뭔가 했더니, 조건을 하나 빼먹었었다. 그런데 예전 풀이내역 보니 그때도 똑같이 이걸로 시간을 썼었음.. ㅜㅜ 같은 실수 반복하지 않기! 근데 골드 1 치고는 쉽다. 난이도가 조금 후하게 붙은 것 같기도.. 문제 링크 https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 구현 방법 1. 값이 2인.. 2020. 9. 3.
[백준] 17142.연구소3 (java) / 조합, BFS @조합, BFS / 45m 이번이 3번째 풀이 무난한 문제인데, 조건 하나때문에 틀려서 다시 풀었다. 문제 링크 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 세달 전에도 풀었던 문제인데, 그때도 삽질하고 지금도 삽질..ㅎㅎ 이전 풀이 https://buddev.tistory.com/34 [백준] 17142.연구소3 (java) / 백트래킹, DFS, BFS, 조합 @백트래킹, DFS, BFS, 조합 / 43m (필기 11분, 디버깅 8분 포함) 기본.. 2020. 5. 30.

티스토리툴바