s0n9h2

문제 https://www.acmicpc.net/problem/13910 13910번: 개업 해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 www.acmicpc.net 사용 언어 Python3 풀이 과정 일단 푼 시간도 진짜 오래 걸렸는데 푸는 과정에서 문제를 잘못 봐서 두 번이나 함정에 빠졌다... 1. 해빈이는 양손잡이이기 때문에 한 번에 두 개의 웍만 사용할 수 있다. 2. 정확한 짜장면의 수만큼 요리할 수 있는 경우가 없을 경우 -1 출력 나는 1번을 안 보고 아래와 같이 모든 조합의 합을 구했고 당연히 이중 for문으로 시간이 오래 걸릴 수밖에 없었다. 내가..

문제 https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 사용 언어 Python3 풀이 과정 문제를 천천히 이해하며 풀었는데 로직은 다 맞는 것 같았는데 이상하게 띄엄 띄엄 6문제만 오답이었다. 차라리 틀릴거면 다 틀려야하는데 너어무 답답해서 테스트 케이스를 추가하고 내 머리의 정답과 비교했는데 운이 좋..

문제 https://www.acmicpc.net/problem/15828 15828번: Router 인터넷을 사용하기 위해서는 컴퓨터에 인터넷 회선을 연결하거나 Wi-Fi를 연결해야 한다. 이렇게 연결된 네트워크를 통해 컴퓨터에는 통신이 가능하다. 마음에 드는 노래나 동영상이 있는 곳에 www.acmicpc.net 사용 언어 Python3 풀이 과정 실버 IV인 만큼 문제를 읽고 한 줄씩 그대로 구현했더니 어렵진 않은 문제였다. 그런데 다른 스터디원들 이야기를 들어보니 50점을 맞은 분들이 꽤 있었고 시간초과가 이유일 것 같다는 추측이어서 그 분들의 코드와 비교해보면 크게 아래 두 가지의 차이점이 있었다. 1. input() 대신 sys.stdin.readline() 사용 2. list, queue 자료..

문제 https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 사용 언어 Python3 풀이 과정 처음에는 막 항상 끝이 PAP로 끝나야 하니까 그런 조건들을 생각하다가... 절대 모든 조건을 고려할수도 없고 그렇게 푸는 문제가 아닌 것 같아서 더 생각해봤다. 그런데 문제 조건에서 다음과 같이 명시했으므로 1. P는 PPAP 문자열 2. PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열 반대로 PPAP를 다시 P로 바꿔도 PPAP 문자열이 된다는 사실을 깨달아야 했다. 저 로직을 깨..

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 사용 언어 Python3 풀이 과정 비슷한 로직으로 첫 번째 시도는 틀렸지만 두 번째에 뜬 맞았습니다! DFS랑 BFS 개념을 여러번 공부중인데 그래도 문제에 적용하는게 왜 어려운지 나는.... 공부 방법을 바꿔서 더 많은 문제의 예시를 좀 따라 쓰고 안 보고 다시 쳐보는 연습을 해야겠다. 제출 답안 # 입력 변수 받기 N, M, V = map(int, ..

문제 https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 사용 언어 Python3 풀이 과정 또다른 동적 프로그램 문제였다. 처음 아이디어는 금방 생각 했는데 코드로 구현하는데는 좀 오래걸렸던 것 같다. 특히 경우의 수를 제대로 나누는 것이 어려웠는데, 일단 0으로 시작하는 경우만 걸러주고 이후에 해독이 안되는 코드는 자동으로 걸러지도록 경우를 나누었다. if code[0] == 0: # 0으로 시작하면 잘못된 코드 else: # 이후 한 자리, 아니면 두 자리로 ..

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 사용 언어 Python3 풀이 과정 또다른 동적계획법 문제! 처음에는 아래 제출 방식대로 제출했다가 아래와 같이 수정해봤는데 append를 사용하는게 조금은 더 시간이 걸리는 것을 확인했다. from sys import stdin input = stdin.readline n = int(input()) sequence = list(map(int, input().split())) maxSum = [] fi..

문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 사용 언어 Python3 풀이 과정 1로만들기 첫 번째 문제와 비슷하게 풀고 getpath 함수를 하나 추가해주었다. 사실 원래 풀던 방식으로는 path를 기록하는게 너무 어렵고 감이 안와서 다른 분의 코드를 참고해서 풀었다. def getpath(x): global path current = x while current != 0: print(current, end=' ') current = path[current] 나한텐 살짝 어렵긴 했지만 ㅠㅠ 공부했다 치고 맞았습니다!! 음 메모리랑 시간은 ..

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 사용 언어 Python3 풀이 과정 처음엔 아래와 같이 또 재귀로 모든 경우의 수를 나눠 연산하려 했는데 숫자가 커지니 recursion error를 냈다.. 재귀 처음엔 어렵더니 계속 쓰게 되는데 DFS가 아니라면 안쓰도록 노력해봐야겠다. if x in count: return count[x] else: if x % 3 == 0 and x % 2 != 0: # 3의 배수만일 때 count[x] = 1 + min(makeOne(x//3), makeOne(x-1)) elif x % 2 == 0 and x %..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 사용 언어 Python3 풀이 과정 동적 계획법 문제는 점화식을 구하는 것이 중요하다는 걸 다시 한 번 깨달은 문제. 그리고 그 점화식을 구할 때에는 대개 마지막 경우의 수가 어떻게 되는지 생각해 보는게 쉽게 접근하는 방법인 것 같다. 1, 2, 3 숫자만 써서 합이 정수 n이 되는 조합을 만든다고 할 때, 마지막 더하기의 경우는 x + 1 = n x + 2 = n x + 3 = n 위 세 가지 경우밖에 없기 때문에 경우의 수는 n - 1을 구하는 경우, n - 2를 구하는 경우, n - ..

문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 사용 언어 Python3 풀이 과정 요세푸스 순열의 규칙을 생각해서 나름 쉽게 풀었다. 그런데 출력 형식을 간단하게 구현하는데 고민을 많이 했다. 처음에는 다음과 같이 구현했는데 76ms가 나왔고, 후에 다른 사람들의 답안을 참고하여 출력 형식만 바꿔줬더니 72ms가 되었다. from sys import stdin N, K = map(int, stdin.readline().split()) table = [x for x in range(1, N + 1)] Josephus = [] id..

문제 https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 사용 언어 Python3 풀이 과정 이진트리의 전위 순회-중위 순회-후위 순회는 학부시절부터 공부했던 것이지만 이걸 코드로 구현한다 하더라도 각각을 구현했지 두 가지 트리 정보로 나머지 순회를 구하는 것은 처음이라 어떻게 풀어야 할 지 막막했다. 그래도 전위 + 중위 > 후위나 중위 + 후위 > 전위는 쉬운 편이고 전위 + 후위 > 중위가 생각할 점이 훨씬 많은 것 같아 나중에 따..

문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 사용 언어 Python3 풀이 과정 재귀는 컴퓨터가 하는건데 내 머리로 짜려니 항상 머리가 아프다... 그래도 어찌저찌 풀어서 채점율 7~80%까지 쭉쭉 오르길래 맞았나!!! 했더니 마지막 순간에 틀렸습니다 어디서 틀린걸까 한참을 보다가 질문하기를 보고 어떤 현자님의 답변에서 힌트를 얻었다. def cutting(N, papers): pieces = [] globa..

문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 사용 언어 Python3 풀이 과정 bfs 문제라지만 bfs로 못풀겠어서(이론에서 문제에 적용 어떻게 하는건즤!!!) 내 논리대로 풀었다가 틀렸다. 근데 웬만한건 정답이 떠서 웨!!! 틀린거야!!하고 스터디원들과도 상의했지만 맞을 듯 말듯 계속 틀렸다. 알고보니 문제는 내가 각 숫자에 방문처리를 해서(시작은 bfs였기 때문) [[1, 2], [2, 3], [3, 4], [5, 6], [7, 8],..

문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 사용 언어 Python3 풀이 과정 처음에 나는 d(현재 바라보고 있는 방향)에 따라서 다음 좌표값을 다르게 설정해주려 했는데, 그럼 왼쪽으로 회전할 때 뒤로 갈 때 등의 좌표값을 모두 조건문으로 나눠줘야 했다. if d == 0: # 북쪽의 왼쪽 next = (r, c-1) elif d == 1: # 동쪽의 왼쪽 next = (r-1, c) elif d == 2: # 남쪽의 왼쪽 next..

문제 https://www.acmicpc.net/problem/4881 4881번: 자리수의 제곱 89, 145, 42, 20, 4, 16, 37, 58 사이클 1 사이클 www.acmicpc.net 사용 언어 Python3 풀이 과정 이게 제일 효율적인 방법은 아니더라도 테스트 케이스는 다 맞길래 맞다고 생각했는데!!! 왜 때문에 틀렸습니다?! 반례를 찾으려고 열심히 아무 숫자나 넣어봤는데 내 머리로 계산한 답과 모두 일치했다... import sys cases = [] while True: case = list(sys.stdin.readline().strip().split()) if case == ['0', '0']: break cases.append(case) def sumEach(case): se..

문제 https://programmers.co.kr/learn/courses/30/lessons/42746?language=python3 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 사용 언어 Python3 풀이 과정 처음에 풀었던 답안은 다음과 같다. 이것도 처음에 if문으로 case를 엄청 나누다가 이게 아닌것 같아 다 엎고 질문하기에서 힌트를 얻어 작성한 코드인데... 아래와 같이 틀린 케이스가 절반이나 돼서 ㅋㅋㅋㅋㅋㅋ 한숨 쉬고 틀린..