Daim's blog

Python으로 푸는 백준 6359. 만취한 상범

백준 6359. 만취한 상범 기숙사 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생들이 구금되어 있다. 감옥 간수인 상범이가 문을 열고 닫는 게임을 했을 때, 모든 게임이 끝나고 난 후에 열린 문으로 도망친 학생의 수를 구하는 프로그램을 짜시오. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 Github에서 코드 보기 문제 조건 감옥에 주어진 N개의 방을 열고 닫는 게임을 한다. 1부터 n의 숫자가 될때까지 숫자들을 k(1

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 6. 2. 09:00

Python으로 푸는 백준 2579. 계단 오르기

백준 2579. 계단 오르기 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 계단에는 일정한 점수가 쓰여있으며 계단을 밟으면 그 계단에 쓰여있는 점수를 얻게 된다. 계단에 오르는 규칙을 지키며 계단의 꼭대기에 올랐을 때, 얻을 수 있는 총 점수 최댓값을 구하는 프로그램을 작성하시오. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 Github에서 코드 보기 문제 조건 계단을 오르는 규칙은 다음과 같다. 1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.(0층) 3. 마지막 도착 계단은 반드시 밟..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 6. 1. 09:00

Python으로 푸는 백준 2163. 초콜릿 자르기

백준 2163. 초콜릿 자르기 정화가 N x M 크기의 초콜릿을 친구들과 나눠먹기 위하여 1 x 1 크기로 자르려고 한다. 최소 쪼개기 횟수로 초콜릿을 쪼개기 위해선 몇 번 쪼개야 하는지 구하는 프로그램을 작성하시오. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 Github에서 코드 보기 문제 풀이 이 문제는 크기마다 초콜릿을 쪼개는 수의 규칙을 찾아 문제를 풀 수 있다. 나는 수의 규칙을 찾아 문제를 풀었다. 가로가 N 조각이라는건 총 N-1 번 자르게 나눠져 있다는 점을 주의해서 문제를 해결하면 된다. 예를 들어, 5 x 3인 초콜릿이 주어졌다고 하자. 가로로 4 번을 잘라 1x3 짜리가 5조각이 나오고, 이 5조각을 각각 2 번씩 잘라야 1 x 1 짜리 초콜릿을 얻을 수 있다. 조건을 일반화 ..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 5. 31. 10:00

Python으로 푸는 백준 1563. 개근상

백준 1563. 개근상 한학기의 출석 일수 N이 주어졌을 때, 개근상을 받을 수 있는 경우의 수를 세는 프로그램을 작성하시오. 백준에서 푼 문제 리스트 백준에서 문제 보기 Github에서 코드 문제 조건 출결 사항이 기록되는 출결은 출석, 지각, 결석이다. 개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다. 문제 풀이 문제의 조건을 이해해 보자. 지각 횟수는 누적되고, 결석은 연속되지 않으면 초기화된다. 주어진 한 학기 출결 일 수 N일까지, 1일부터 차근차근 경우의 수를 살펴나갈 것이다. 매일 현재의 지각 횟수, 연속 결석 수를 확인하여, 문제 조건에 제시된 '개근상을 받을 수 없는 조건'에 해당되지는 여부를 확인한다. 이처럼 N일까지 매일 조건을 체크하면서..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 5. 30. 14:00

Python으로 푸는 백준 1793. 타일링

백준 1793. 타일링 2 * N 직사각형을 2*1과 2*2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 Github에서 코드 보기 문제 풀이 이 문제를 이해하는데는 어렵지 않다. 다만 어떻게 풀지 막막할 뿐이다. 다이나믹 프로그래밍으로 문제를 풀기 위해서 문제를 자세히 들여다보자. 이 문제는 매번 다음 타일을 무엇을 두느냐를 결정하는 작은 문제로 나눠질 수 있다. 하나의 타일을 놓을때마다 (1) 2*1짜리를 놓을지, (2) 2*2 짜리를 놓을지, 아니면 (3)2*2를 만들기 위해서 1*2짜리를 2개를 합쳐 모양을 만들지를 고민한다.(2*1을 돌려놓으면 1*2가 된다) 다음에 놓을 수 있는 (1)(2)(3)을 이미지로 보면 아래와 같다. Ca..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 5. 29. 21:00

Python으로 푸는 백준 1991. 트리 순회

1991 트리 순회 이 문제는 트리의 구조를 입력받아, 트리를 순회하는 전휘, 중위, 후위 순회 방식대로 값을 출력하는 문제이다. 트리의 기본 문제라고 할 수 있다. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 github에서 코드 보기 문제 풀이 트리의 순회하는 방법으로는 전위 순회, 중위 순회, 후위 순회가 있다. 백준 1991 문제는 이진 트리의 순회에 관한 매우 기본적인 문제이다. 그럼에도 이 문제를 풀면서 난 매우 고전을 했다. 아무래도 트리를 구현하고나서 순회를 진행해야 하는데 트리를 구현하는 방식을 너무 쉽게 생각한 듯 하다. 1. 트리를 list(배열)로 구현한 방식 - 메모리 초과로 실패 내가 처음으로 푼 방법은 트리를 list(배열)로 구현한 방식이다. 문제에서 제안한 노드의 수는..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 5. 28. 19:00

Python으로 푸는 백준 10799. 쇠막대기

괄호로 표현된 쇠막대기와 레이저가 있다. 긴 쇠막대기 위에 작은 쇠막대기를 층별로 쌓았을 때, 레이저를 수직으로 쏘게되면 몇개의 쇠막대기 조각이 나오는지 알아보는 프로그램을 짜시오. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 github에서 코드 보기 문제 풀이 문자열을 순회하면서 어디서부터 레이저이고, 막대기의 시작과 끝인지를 구분할 수 있어야 한다. '(' 의 뒤가 ')'이면 레이저이다. '('의 뒤가 '('이면 막대기의 시작이다. ')'의 앞이 ')'이면 막대기의 끝이다. 레이저를 발견하면 아직 끝이 닫히지 않은 막대기들은 레이저에 영향을 받아 쪼개질 수 있다. 막대기가 레이저 1개의 영향을 받으면 2개로 쪼개진다. 막대기가 레이저 2개의 영향을 받으면 3개로 쪼개진다. 즉, 레이저 N개의 ..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 5. 5. 21:30

Python으로 푸는 백준 2309. 일곱 난쟁이

백준 2309. 일곱 난쟁이 백설공주와 일곱난쟁이가 함께 살고 있었다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉명이 돌아왔다. 일곱 난쟁이의 키의 총 합은 100이다. 진짜 난쟁이를 골라내어 오름차순으로 키를 출력하는 프로그램을 짜시오. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 Github에서 코드 보기 문제 조건 입곱 난쟁이들의 키는 서로 달라야 한다. 입곱 난쟁이의 키는 100을 넘지 않는다. 일곱 난쟁이의 키를 오름차순으로 출력해야 한다. 일곱 난쟁이를 찾을 수 없는 경우는 없으며, 여러 가지 경우가 가능하다면 하나의 경우의 수만 출력한다. 문제 풀이 나는 itertools의 combinations(조합)으로 문제를 풀었다. 입력되는 난쟁이의 키는 9가지이고, 그 가운데 7가지를..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 5. 1. 09:00

Python으로 푸는 백준 2210. 숫자판 점프

백준 2210. 숫자판 점프 주어진 격자판을 상하좌우로 이동하여 만들어 낼 수 있는 6자리의 수들 중 중복되지 않은 수들의 갯수를 반환하는 프로그램을 짜시오. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 Github에서 코드 보기 문제 조건 숫자판의 모든 지점에서 수를 만들어 낼 수 있다. 만들어진 6자리의 수는 서로 중복되지 않아야 한다. 문제 풀이 이 문제는 이해하기 쉽도록 재귀로 풀 수 있다. 주어진 입력값의 크기는 2차원 배열 5*5이므로 재귀로 풀어도 stackoverflow 에러가 나지 않기 때문에 해당 방법으로 문제를 풀었다. 문자의 길이가 6이 아니면 count를 더해 재귀한다. 현재의 문자의 길이가 6이 될때에 만들어진 수를 집합(set()) 컨테이너에 넣어서 중복을 제거해준다. b..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 4. 30. 20:00

Python으로 푸는 백준 9012. 괄호

이 문제는 괄호 문자열이 쌍에 맞게 구성되어 있는지를 확인해서 'YES', 'NO'를 반환하도록 프로그램을 짜야한다. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 github에서 코드 보기 문제 풀이 Stack을 이용하여 괄호 문자열이 쌍이 맞는지 확인한다. 문자열은 앞에서부터 순서대로 문자 하나씩 Stack에 넣는다. Stack이 비어있는 경우에는 ')'는 들어갈 수 없다. ('NO' 반환) '('은 계속해서 쌓을 수 있다 (단, 모든 문자열을 확인했을때에는 Stack은 반드시 비어있어야 한다, 그렇지 않으면 'NO' 반환) ')'이 다음 차례로 들어갈 경우에는 ')'를 넣었다가 pop해줬다 치고 '(' 만 pop() 해준다. 위의 작업을 반복해 준다음, 모든 문자열을 확인하였을 때에 Stack이..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 4. 17. 16:00

Python으로 푸는 백준 3184. 양

문제의 조건에 따라 하루가 지났을 때, 영역 안에 살아 남아있는 양과 늑대의 수를 출력하는 코드를 짜시오. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 github에서 코드 보기 문제 조건 - 영역 안의 양의 수가 늑대의 수보다 적으면, 늑대가 그 지역 안의 모든 양을 잡아 먹는다. - 영역 안의 양의 수가 늑대의 수보다 많으면 양이 이긴다. 이럴 경우 늑대가 죽는다. (주의) 문제 풀이 문제의 조건에서 주의할 점은 양이 늑대와 싸워서 이길 경우에는, 늑대가 죽는다는 점이다. 문제 조건에서 단순히 '이긴다' 라고만 표시가 되어 있어서, 늑대와 양이 대치 상태로 끝날 줄 알고 늑대의 수를 차감시켜주지 않았더니 결과값이 틀리게 나왔다. 이 부분만 코드에 추가하면 문제는 쉽게 풀린다. 알고리즘은 다음과 ..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 4. 12. 18:30

Python으로 푸는 백준 2638. 치즈

이 문제는 실온에 둔 치즈가 있고, 공기를 접한 치즈 부분은 정확히 한시간 후에 사라진다고 가정했을 때, 치즈의 모든 부분이 녹아 없어지는게 걸리는 정확한 시간을 구하는 프로그램을 작성해야 한다. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 github에서 코드 보기 문제 풀이 공기에 닿은 치즈인지를 구분하는 방법을 찾는게 문제 풀이의 관건이다. 공기와 밀접한 치즈의 경우에는 얼마나 많은 면이 공기와 맞닿아 있는지 치즈에 수치를 적어준다. 수치가 2이상인 치즈와 맞닿아 있는 치즈인 경우에는 직접적으로 공기와 닿진 않지만 간접적으로 공기와 닿아있는 것과 같다. 치즈를 다 녹인 다음에는 다시 수치를 측정하기 위해서 치즈의 수치를 본래 값으로 변경해주어야 한다. 파이썬 코드 1 2 3 4 5 6 7 8 ..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 4. 5. 19:01