코딩,안되면 될때까지

solved.ac 난이도 : GOLD5 백준 9663번- 파이썬 풀이 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net -백트랙킹 이번 문제는 대표적인 백트랙킹 문제인 N-Queen이다. 필자는 처음 이문제를 풀때 2차원 배열을 이용해야하나 했지만 그렇게 하게되면 너무 복잡해진다. 그래서 일차원배열을 이용해 문제를 풀었다. 그 과정은 다음과 같다. 1)체스판에 체스 놓기 일차원 배열의 한 위치에 값을 rows[i] = a 와 같이 값을 저장시킨다. 이것은 체스판..

solved.ac 난이도 : Silver3 백준 1748번- 파이썬 풀이 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net -구현,시뮬레이션 필자는 이 문제를 보고 처음엔 굉장히 단순하게 생각해 다음과 같은 코드를 작성했다. n = int(input()) number = "" for i in range(1,n+1): number+=str(i) print(len(number)) n을 입력받은 다음 빈문자열 number를 선언해 1부터 n까지 number에 추가한후 number의 길이를 구하는 것이다. 하지만 역시나 이렇게 간단한 문제가 아니었고 시간초과로 인해 실패를 ..

solved.ac 난이도 : Silver3 백준 1449번- 파이썬 풀이 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net -그리디알고리즘 우선 배열을 입력받은 다음 배열의 원소를 오름차순 정렬한다. 테이프의 길이를 m이라 할때 배열의 첫번째 원소를 start라 하고 다음 원소를 i라 할때 (i+0.5)-(start-0.5) r가 m 보다 작으면 continue, 크면 테이프의 갯수를 +1해준다 수리가 필요한 곳의 위치가 [1 2..

solved.ac 난이도 : GOLD4 백준 7569번- 파이썬 풀이 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net -그래프이론,너비우선탐색,그래프 탐색 이 문제는 필자의 블로그에 있던 기존 토마토 문제에 좌표하나만 추가하면 된다. 즉 ,2차원 리스트를 사용하는 풀이에서 2차원 리스트를 3차원 리스트로만 바꿔주면 된다. 3차원리스트의 선언방법은 다음과 같다. tomato1 = [[list(map(int,input().s..

solved.ac 난이도 : GOLD4 백준 2206번- 파이썬 풀이 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net -그래프 탐색,그래프 이론,너비 우선 탐색 이 문제는 일반적인 너비 우선 탐색문제와는 다르게 3차원 배열을 사용해야한다. 그 대표적인 이유는 벽을 부수고 이동할수 있는 경우가 딱 한번밖에 존재하지 않기 때문이다. 때문에 벽을 부수고 이동하는 경우, 벽을 부수지 않고 이동하는 경우를 각각 구하기 위해 3차..

solved.ac 난이도 : Silver5 백준 1439번- 파이썬 풀이 https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net -그리디 알고리즘 이 문제는 '0'을 뒤집는 부분과 '1'을 뒤집는 부분을 각각 구현해 두 개의 결과중 작은값을 출력하는 식으로 풀이를 구서해 봤다. 이때 뒤집는 부분을 필자는 큐 자료구조를 이용해 봤다. -'1'을 뒤집는 부분- 우선 핵심은 다음과 같다. 큐에 문자열의 처음 원소를 삽입한다. 이때 연속된 숫자는 한번에 뒤집..

solved.ac 난이도 : GOLD5 백준 7576번- 파이썬 풀이 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net -BFS,그래프 이론,그래프 탐색 이 문제는 여러곳에서 시작하는 bfs 문제로 난이도는 GOLD5 지만 크게 어렵지는 않았던 거 같다. 하루가 지날때마다 인접한 토마토가 익는다 했으므로 토마토가 안익은 지역을 bfs를 통해 방문할때마다 +1을 해주고 그래프에서 가장 큰값을 찾으면 되는 문제였다. 이때 이문제에서 ..

solved.ac 난이도 : GOLD5 백준 7662번- 파이썬 풀이 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net -자료구조, 우선순위 큐, 트리를 사용한 집합과 맵 이 문제는 두 배열을 어떻게 동기화 시켜주는지가 관건이다. 우선순위 큐에 대한 내용은 아래에 링크를 참고하면 이해하기 편할 것이다. https://hae-sooo97.tistory.com/22?category=925334 우선순위 큐( heapq) heapq : heapq...