파이톨치

[문제] https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [어떻게 풀까?] 이 문제는 백준에 나와있는 예시 자체가 힌트였다. 어떻게 풀까 고민하던 중에 먼저 눈치 챈 것은 끝나는 시간이 작을 수록 좋다는 것이다. 회의가 빨리 끝나야 다음회의를 할 수 있고, 애초에 끝나는 시간보다 시작하는 시간이 더 빠르니까 말이다. 이것을 고려하여 수를 정렬해주면 되는데 어떻게 정렬할지 몰라서 https://dailyheumsi.tistory.com/67 파이썬 정렬, 다중 조건으로 한 번에 하기. 파이썬으로 문제를 풀다보면, 여러 조건으로 소팅을 해야하는 경우가 있다. 일반..

[내용] 그리디 알고리즘의 개념은 지금 현재 가장 욕심이 나는 것을 선택하는 것이라고 한다. 가령 이런 것이다. 지금 내가 가장 하고 싶은 것은 게임이다. 내가 현재 게임을 하게 된다면 나는 행복할 것이다. 하지만 이것이 나의 미래에 긍정적인 발적을 만들어주지는 못한다. 이것이 그리디 알고리즘의 단점이라고 한다. [백준 문제] https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 정말 ..

[문제 및 출처] https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net [어떻게 풀까?] 계단 오르기와 굉장히 유사하지만 한가지 다른 점이 있는데, 그건 건너뛰는 것이다. 계단오르기의 경우 마지막 계단을 무조건 올라야 했지만 포도주 시식은 그럴 필요가 없다. 또한 필요에 따라서 3개씩 건너서 마셔도 된다. 대충 그림으로 그리면 이런식으로 될 것이다. 중간에 글자는 NO를 쓴것이다 ^^. [코드] n = int(input()) nums = [] dp =..

[문제 및 출처] https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net [어떻게 풀까?] 이 문제에 대해 이해하기 위해서 간단하게 그림을 그려보았다. 우리가 i번째 계단에 가기 위해서는 저런 식으로 가야한다. 왜냐하면 3계단을 연속으로 오를 수 없기 때문! 이것을 동적 계획법과 연관지어 어떻게 풀어야 할까? 경우의 수를 누적시키면 된다. 코드를 보면 이해가 될 것이다. [코드] n = int(input()) array = [0 for i in range(301)..

[문제 및 출처] https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net [어떻게 풀까?] 흠...일단 아직 백트래킹을 어떻게 쓰는지 감이 잘 안 잡혀서 아무 생각 없이 구현이라도 해봐자는 마음으로 코드를 작성해 보았다. 정말 비효율적인 코드라고 나도 생각한다. 그렇기에 시간초과가 걸리고 말았고 이에 대해 다시 공부해야겠다는 생각을 가지게 되었다. [CODE] COLUM, ROW = 9, 9 board = [[0 for i in range(COLUM)..

[문제 및 출처] https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net [어떻게 풀까?] w(1,1,1) -> w(0,1,1) + w(0,0,1) + w(0,1,0) - w(0,0,0) 나열을 해보면 이런식으로 된다. w(2,2,2) -> w(1,2,2) + w(1,1,2) + w(1,2,1) - w(1,1,1) 이라? 나는 w(1,1,1)을 알고 있지 않나? 그렇다면 컴퓨터에게도 이것을 알려주면 좀더 쉽고 빠르게 하지 않을까? 반복은 컴퓨터가 훨씬 잘..

[문제 및 출처] https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [어떻게 풀까?] 이 문제는 오래 전부터 풀고 싶었다. 하지만 내 실력이 부족하여 나는 이전에 풀지 못하였고 지금에 와서야 구글링과 여러 경험치들을 쌓아 다시 도전했다. 이 전에는 남들이 쓴 코드를 보고도 이게 뭔 소린가 싶었다. 하지만 지금은 코드를 보고 제대로 이해하고 있다. 스스로의 성장이 느껴지는 문제라 감회가 새롭다. 나는 프로그래밍을 시작한지 반년도 되지 않아서 사실 이 문제가 많이 ..

[문제 및 출처] https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [어떻게 풀까?] 조건은 다음과 같다. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 앞에서 나온 문제들을 차근차근 풀었다면 굉장히 쉽게 풀 수 있을 것이다. [코드] N, M = map(int, inpu..