국문과 유목민

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 + a 1. 문제 설명 - https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 2. 접근 방식 - 출처: https://hongcoding.tistory.com/118 참고 1) 스도쿠 판에서 '0'에 해당하는 위치를 담은 리스트를 만든다. 2) 0을 담은 리스트를 하나씩 확인하면서..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 40 + a 1. 문제 설명 - https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 2. 접근 방식 - 해당 문제는 재귀를 활용해서 문제를 한 번 풀고, 조합을 이용해서 문제를 한 번 풀었다. - 재귀적 문제풀이 1) team1에 들어갈 수 있는 번호를 재귀를 통해 집어넣는다. 2) team1에 멤버의 절반이 ..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 2시간 + a 1. 문제 설명 - https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 접근 방식 > 출처: https://rebas.kr/761 [PROJECT REBAS] 참고 - y축, 대각선 (/)방향, 역대각선 방향(\) 총 3가지의 경우를 True, False로 설정해서 재귀문을 돈다. - ..

오늘은 백준_단계별풀이 백트랙킹 파트 마무리를 지었다. 이전에 미뤄뒀던 문제들을 다 풀고자 했다. 확실히 실버 1까지는 풀만한 것 같은데 골드 4, 5 정도로 올라가면 확실히 한계를 느끼는 것 같다. 특히 백트랙킹과 같이 재귀적으로 문제를 풀어야 하는 경우 재귀식을 어떻게 구현할 것인가에 대한 생각을 잘 하지 못하는 것 같다. 백트랙킹 문제의 경우 메모리가 여유있울 땨 보통 itertools라이브러리를 활용하다보니 재귀에 대한 이해가 더 힘들었던 것 같다. 거의 한 달 가량을 알고리즘 공부를 하면서 특히 재귀 파트에 대한 이해가 제대로 되어있지 않았구나 라는 생각을 꾸준히 했다. 오늘 단계별 풀이까지 해서 재귀에 대한 문제를 어느정도 풀어본 것 같다. 지금까지 풀었던 것 중 검색을 통해 풀었던 문제들의 ..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 2시간 + a 1. 문제 설명 - https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 접근 방식 - 재귀적인 방식으로 코드를 구현해야 한다. ※ 해당 문제는 "파이썬"코드로 작성 시에 시간 초과가 된다. 특정한 조건들을 더 고려해야 할 필요가 있을 것 같다. 3. 코드 - Permutation 활용 ..

오늘은 백준에서 정렬과 백트랙킹 문제를 풀었다. 정렬 문제의 경우는 간단하게 풀었고, 백트랙킹 문제도 좀 쉽게 푸는 줄 알았는데, 백트랙킹이 아닌 permutaion이나 combination을 활용해서 문제가 쉬웠던 것 같다. n-queens문제도 처음에는 itertools 라이브러리를 활용해서 풀어보려고 했으나 메모리 초과가 나왔다. 그래서 백트랙킹으로 다시 풀었는데도 시간초과가 나와서, 다른 블로그 글을 참고해서 다시 풀었는데도 계속 시간초과가 나온다. 내 생각에 테스트 케이스가 하나 추가가 된 것 같다. 파이썬으로는 풀기 힘들 것 같다는 생각이 들었다. 백트랙킹 문제의 경우 재귀로 풀어야 하는데, 재귀에 익숙하지 못한 듯 하다. permutation이나 combination 메소드의 활용법은 알았으..