분류 전체보기

[Baekjoon] 7576 토마토

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 ..

[Algorithm] Dynamic Programming에 관해

소마 13기 코테를 준비하며, dp문제를 많이 풀 기회를 접하였다. 그래봤자 난이도가 실버급에 있는 문제들이긴 하지만, 그래도 일단 내가 풀면서 느낀 점들을 정리하려 한다. 먼저 DP, Dynamic Programming은 문제풀이 알고리즘의 한 종류로, DFS나 그리디, 백트래킹과는 또다른 성격의 문제풀이법이다. 풀면서 수학적 귀납법과 비슷하다는 느낌을 받았다. 먼저, 속도에 관해 말해 보자면 DFS는 시간이 엄청 걸리고, 백트래킹은 그걸 조금 줄여주지만 DP는 확실히 줄여 주는 것을 느꼈다. 여기서 한 가지 느낀 점은 "DP는 시간과 공간을 trade해서 효율성을 올린 알고리즘" 이다. DP문제를 풀다 보면 점화식 형태의 풀이법이 많다. 대부분 배열이나 리스트를 이용하여 점화식을 세워 문제를 푸는데,..

[개인 프로젝트] 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..

[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..

[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..

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

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

[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가 나..

[Pylearn] 1213 / 문자열 응용하기

- 문자열 일부 바꾸기 - s.replace('arr1', 'arr2')로 사용. word = 'python is great' word.replace('python', 'c') print(word) #c is great - 만약 문자열이 일치하지 않는 경우 -> word.replace('bython', 'c') print(word)# python is great => 바꿀 문자를 찾지 못하고 그대로 출력된다. 응용 => 문자열 A가 있을시에 A를 문자열 B로 바꾸는 프로그램을 만들 때 A가 있는지부터 검사할 필요 없이 바로. replace('A', 'B') 하면 된다. - 문자 바꾸기 - translate(str.maketrans('aeiou', '12345'))으로 사용. - table = str.ma..

[Python] 1210 / file 입출력, 클래스 #1

파일 입출력을 하기 위해서는 여러 방법이 있다. 먼저, 가장 기본적인 open()을 이용한 방법이 있다. (open('이름', '용도')로 사용) 같은 폴더 내에 'hello.txt'파일을 만든 후, 그 파일에 'hello, world!'를 쓰는 프로그램은 다음과 같다. file = open('hello.txt', 'w') file.write('hello, world!') file.close()​ 이때 file.close()를 해줘야 메모리가 낭비되지 않고, 사소한 실수가 중대한 피해로 이어지는 걸 막을 수 있다. 'w'의 의미는 파일을 쓰는 용도로 열겠다는 뜻이다. write()를 하게 되면 파일에 기존에 있던 내용은 삭제되고, 새로운 내용이 적힌다. 이제 파일의 내용을 읽는 법을 알아보자. file ..

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

스도쿠는 재미있는 게임이다. 9 * 9 칸 안에서 한 세로줄, 한 가로줄, 한 블록(3*3 칸, 여기서는 '블록'이라는 표현을 쓰겠음) 안에 1부터 9까지의 자연수가 겹치지 않도록 배열하는 규칙 내에서 모든 칸의 수를 채우는 게임이다. 예) 9 1 5 2 5 3 1 4 9 8 2 7 2 5 9 8 4 1 9 5 5 9 2 7 3 1 4 5 9 6 3 6 1 5 9 8 7 5 정답은 아래와 같다. 9 3 6 2 1 8 7 4 5 8 2 4 7 5 3 1 9 6 5 1 7 4 9 6 8 3 2 7 6 2 5 3 1 9 8 4 3 8 1 6 4 9 2 5 7 4 5 9 8 2 7 6 1 3 1 4 5 9 6 2 3 7 8 6 7 3 1 8 5 4 2 9 2 9 8 3 7 4 5 6 1 이와 같이 빈 숫자들을 ..