728x90
반응형

전체 글 72

[개인 프로젝트] Python으로 2048 게임 만들기 #2

지난 글에서는 2048 게임을 만들 때 생기는 버그에 대해 알아보았다. https://fclipse.tistory.com/18 [개인 프로젝트] Python으로 2048게임 만들기 # 1 버그 1. - a를 눌러 왼쪽으로 이동시켰는데 합쳐진 4는 사라지고, 그 자리에 2가 랜덤으로 생겨난 상황. - 작업 순서가 잘못된 듯하다. - 그럼에도 score은 제대로 올라감 Sol) - 원래는 4로 합쳐진 다 fclipse.tistory.com 이번 글에서는 2048 게임을 소개하고, 앞으로 최종 목표는 어떻게 될 것인지를 정하겠다. 먼저 이 프로젝트의 최종 목표는 '웹에 2048게임을 호스팅해서 누구나 쉽게 즐길 수 있게 하는 것'이다. 전체 코드는 다음 페이지에 소개되어 있다. https://github.co..

개인 프로젝트 2022.02.28

[Python] 스도쿠 풀이 프로그램 #3

저번 글에 이어 이 글에서는 어려운 스도쿠를 풀 수 있는 프로그램을 설명한다. 백트래킹을 이용해 이를 구현했고, 생각보다 정말 간단하게 구현이 되었다. 먼저 사용된 함수는 다음과 같다. def possibilities(i, j): global sudoku exist = [] for k in range(9): if sudoku[k][j] != 0: exist.append(sudoku[k][j]) if sudoku[i][k] != 0: exist.append(sudoku[i][k]) if sudoku[i//3*3 + k//3][j//3*3 + k%3] != 0: exist.append(sudoku[i//3*3 + k//3][j//3*3 + k%3]) unexist = [i for i in range(1, 1..

개인 프로젝트 2022.02.20

[Baekjoon] 9663_N-Queen #2

저번 글에서는 Python으로 N-Queens 문제를 푸는 시도를 적었다. 하지만 최적화를 진행해도 속도가 너무 느리다는 단점이 있었다. 그래서 혹시 속도가 빠른 C언어로 진행하면 어떨까 싶어 C언어로 코드를 옮겨 실행해 보았다. 이정도면 시간 복잡도가 O(10^n)....;;;;; 결과는 놀라웠다. C언어는 월등히 빠른 속도를 자랑했지만, 여전히 n = 15까지는 가지도 못했다. 결국, 알고리즘 실력이 문제였다... 더 열심히 해야겠다. C 코드는 다음과 같다. #include #include // 함수 선언 void n_queen(int i, int j); int check(int i, int j); // 전역 변수 설정 int cnt = 0; int n = 0; int board[15][15] = ..

[Baekjoon] 9663_N-Queen #1

출처 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 먼저 이 문제를 해결하기 위해 필자는 이전 문제에서 배웠던 구조를 가져왔다. 함수 안에 반복문을 ..

[Baekjoon] 10989번 수 정렬하기 3, pypy3 메모리초과

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net [문제] N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. [입력] 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. [출력] 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 메모리 제한이 있어 (8MB) 자칫 잘못하면 메모리 초과가 떠서 문제를..

[Baekjoon] 1018 체스판 다시 칠하기

[문제] https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net M * N 보드에서 나올 수 있는 8 * 8 크기의 보드 중 최소한으로 색을 칠해 체스판으로 만드는 경우의 색을 칠할 칸의 수를 출력하는 프로그램을 만드는 문제. 입력받은 체스판을 이렇게 만드는 것이 목표. (또는 W, B가 반전된 채로) [입력] 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각..

[Python] 스도쿠 풀이 프로그램 #2

'쉬운' 스도쿠를 풀 수 있는 스도쿠 알고리즘을 알아보자. 먼저 원리는 다음과 같다. 1. 빈칸이 있는 스도쿠를 입력받는다. 2. 숫자가 없는 빈칸(가능성 칸)에 각각 들어갈 수 있는 수들을 채워 준다. 3. 행, 열, 블록(3 * 3 칸) 내에서 각각 가능성 칸에 있는 수가 유일한 수가 있다면 그 4. 이를 반복한다.숫자를 채운다. 이 알고리즘을 사용하면 가정이 필요한 스도쿠 이외의 모든 쉬운 스도쿠를 풀 수 있다. 코드는 다음과 같다. https://github.com/siejwkaodj/Sudoku/blob/second/sudoku_2.py GitHub - siejwkaodj/Sudoku: 스도쿠 풀이 알고리즘 스도쿠 풀이 알고리즘. Contribute to siejwkaodj/Sudoku deve..

개인 프로젝트 2022.01.13

[Python] 조합 알고리즘 구현하기

백준 2798번을 풀다 조합을 이용한 풀이를 생각했고, 이전에 모듈로 Combination을 가져다 쓴 기억이 있어 한번 직접 만들어 보는 것도 좋겠다 싶어 Combination을 구하는 알고리즘을 만들어 보았다. 만약 빠르게 조합을 구현하고 싶다면 itertools 라이브러리를 import 해서 조합, 순열 등을 구현할 수 있다. 이는 다음 블로그에 잘 정리되어 있다 https://yganalyst.github.io/etc/memo_18_itertools/ [Python] itertools, 원소의 경우의 수(순열, 조합) 추출하기 itertools 라이브러리를 활용해서 원소들의 경우의 수를 추출하는 방법을 배워보자. yganalyst.github.io 조합의 정의는 다음과 같다. (출처 : https..

Computer Science 2022.01.09

[Pylearn] 1222 / 딕셔너리 응용

추가 - 딕셔너리는 키-값 쌍의 형태를 지닌 자료구조이다. - 먼저 딕셔너리에서 가장 중요한 메서드 2개는 다음과 같다. - setdefault : 키-값 쌍 추가(수정은 불가) - update : 키-값 수정/추가(괄호 안에 들어가는 건 키가 문자열일때만 가능, 아닐 때는 전체 딕셔너리를 넣어야 함) # setdefault 메서드 -> 새로운 키-값 추가 x = {'a' : 10, 'b' : 20, 'c' : 30, 'd' : 40} x.setdefault('e')# 키만 추가 print(x)# {'a': 10, 'b': 20, 'c': 30, 'd': 40, 'e': None} x.setdefault('f', 100)# 키와 값 추가 print(x)# {'a': 10, 'b': 20, 'c': 30,..

[개인 프로젝트] Python으로 2048게임 만들기 # 1

버그 1. - a를 눌러 왼쪽으로 이동시켰는데 합쳐진 4는 사라지고, 그 자리에 2가 랜덤으로 생겨난 상황. - 작업 순서가 잘못된 듯하다. - 그럼에도 score은 제대로 올라감 Sol) - 원래는 4로 합쳐진 다음, 남은 공간 중 하나에 2가 생성되어야 함. 버그 2. - s키를 눌러 22를 합치려 했는데 밑에 4까지 합쳐진 상황 - 마찬가지로 score은 제대로 입력됨. (함수의 중요성) Sol) - 4는 밑으로 이동하고, merge는 한 턴에 한 번만 되도록 해야 함. 밑에 합칠 수 있는 수가 있다고 무조건 내려오면 안 됨. - 해결방법: - 반복 시 merged라는 변수를 추가해 한 번 merge 된 칸은 다시 merge 될 수 없도록 하였음. - 버그 3. - 가만히 있는 숫자 중에서 2가 나..

개인 프로젝트 2021.12.15
728x90
반응형