s0n9h2

문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 사용 언어 Python3 풀이 과정 이 문제는 제목부터 힙을 사용하라고 암시하고 있다. 그런데 어떤 힙? 우선순위 큐! 따라서 구글링을 통해 heapq 구현법을 찾아서 아래까지는 쉽게 구현했다. from heapq import heappop, heappush from sys import stdin, stdout input = stdin.readline print = st..

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 사용 언어 Python3 풀이 과정 처음에는 어디까지가 숫자이고 문자인지 구분하는 방법을 고민하면서 인덱스를 사용하는 방법, 스택을 사용하는 방법 등을 고민했는데 아무리 생각해도 가장 편한 방법은 split이고... 그런데 +와 - 두 가지이기 때문에 고민하다가 모든 숫자를 뺐을 때 가장 작은 수가 되기 때문에 일단 -를 기준으로 나눴다. 그런 다음 각각의 원소에 또 +가 포함된 경우가..

문제 https://www.acmicpc.net/problem/17352

문제 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 사용 언어 Python3 풀이 과정 DP를 이용해 풀었는데 Python3로는 시간 초과로 실패했다. from sys import stdin input = stdin.readline n = int(input()) # dp[i] = 숫자 i가 가지는 제곱수 합 최소개수 dp = [float("inf")] * (n + 1) dp[0] = 0 dp[1] = 1 f..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 사용 언어 Python3 풀이 과정 오랜만의 골드 문제!! 처음 내가 짰던 코드는 다음과 같다. 나름 붙어있는 RR은 원래대로 돌아오기 때문에 없애는 처리를 했는데도 시간초과가 났다..! 심지어 pypy3로도... from collections import deque from sys import stdin input = stdin.readline def func (functions, array): for func in functions: if fu..

문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 사용 언어 Python3 풀이 과정 이 문제는 조합(combinatoin)을 이용하는 법 / 백트래킹(DFS)을 이용하는 법 이렇게 두 가지 버전으로 풀었다. 조합은 진짜 쉽게 풀었지만, 백트래킹을 구현하는 과정에 있어서 N과 M (2)에 추가된 조건인 오름차순 수열만 출력하는 방식이 추가되었는데... 나는 처음에 for문을 수정하지 못하겠어서 출력시에 오름차순 정렬인지를 확인해 맞는 경우..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사용 언어 Python3 풀이 과정 level 2 문제인데... 풀지 못했다😥 이번주에 코딩테스트 스터디에서 백트래킹을 공부한 이후, 이 문제에도 백트래킹을 사용하면 해결될 것 같아 다시 도전해보려고 했다. 그런데 어떻게 시작해야할지 감도 못잡고 실패..ㅎ 블로그를 참고하니 역시 완전 탐색 문제가 맞는 것 같고 구현 방법은 combination / BFS / D..

문제 https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 사용 언어 Python3 풀이 과정 오랜만에 다시 DP 문제를 풀게 되었다. 그런데 이번에도 헷갈린 점화식 세우기...ㅎㅎ 처음엔 냅다 dp[i-1] + dp[i-2] + dp[i-3] 을 생각해봤는데 아무래도 중복되는 건 하나로 치는 경우 때문에 결과가 훨씬 크게 나왔다. 다시 곰곰이 생각해서 1을 더하는 경우는 항상 있기 때문..

문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 사용 언어 Python3 풀이 과정 이 문제는 저번에 프로그래머스 못 풀었던 문제처럼(좀 더 쉽지만) 완전 탐색 방법이 제일 처음 떠올랐다. 그래서 그대로 풀어봤더니 python3에서는 시간초고ㅏ... 혹시 몰라 pypy3로 돌려보니까 진짜 천천히 올라가더니 맞았습니다!!가 나오긴 했다. 이후 이중 for문으로 list 선언한 부분을 l..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사용 언어 Python3 풀이 과정 모각코 문제였는데 오늘은 참가하지 못해 나는 밤에 따로 풀었다. 시간 계산 때문에 예상한 시간을 살짝 넘겨서 풀었는데 점수를 1점밖에 안줘서 당황했다..?! 이유는 예상하긴 했지만 시간 복잡도가 극악이었다..! 지금까지 내 힘으로 푼 것중에 제일 별로라고 할 수 있을 정도. 아예 못풀었음 못풀었지 이건.... 한 번에 통과한 게 신기하네. 시간 날 때 코드..

[01 내장 함수] (1) 입출력 입력 : readline과 fs 두 가지 방법이 있지만 fs가 더 빠름, 프로그래머스는 입력 방식을 신경 쓸 필요 없긴 함 const fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().split('\n'); console.log(input); 출력 console.log() (2) 문자열 1. 자르기 출처 : https://codechacha.com/ko/javascript-how-to-substring/ split : 구분자로 문자열 자르기 let str = 'Hello, World, Javascript'; console.log(str.split(',')); // [ 'Hello', ' Wo..

문제 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 사용 언어 Python3 풀이 과정 이거야말로 저번에 풀었던 4256번. 트리 문제와 비슷하다고 생각했는데 한 번에 풀지 못했다... 그 문제는 그냥 트리이고 이건 이진 트리임을 이용한 문제인데 이진 트리의 개념은 알고 있었지만 탐색을 어떻게 해야할지...막막쓰.. 그래서 다른 블로그의 도움을 받아😥 맞았습니다!! 처음 제출 후 while True: 를 while count en..

문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 사용 언어 Python3 풀이 과정 사실 이 문제는 4256번. 트리 문제를 풀기 전에 풀었어야 순서적으로 맞았을 것 같다. 그 때 더 어려운 문제를 풀면서 확실히 기억했던 건 전위순회, 중위순회, 후위순회의 구현시 차이점은 print() 하는 순서의 차이였다는 것..? 그래서 딕셔너리를 이용해 혼자 풀어보다가, 마음에 안들어서 구글링을 한 뒤 class를 이용한 풀이로 변경했다...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17681 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사용 언어 Python3 풀이 과정 삼성 SW 아카데미에서 (거의 유일하게 학습한) 비트 연산 문제였다! or 연산을 하면 되겠다는건 알았는데 파이썬에서 2진수 다루는 방법을 잘 몰라 검색해서 해결했다. 그리고 아래 첫 번째 제출 코드에서 겹치는 부분이 마음에 들지 않아 한 번만 쓰도록 if문을 변경했다. def solution(n, arr1, arr2): answer = [] for i i..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=python3# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사용 언어 Python3 풀이 과정 DP문제... 점화식 너무 어려워...흐아앙 처음에 생각한 방식은 그냥 엉망진창이었고 질문하기에서 이 글의 도움을 받아 힌트를 얻었다... 그러고도 한참을 생각하다가 겨우 간신히 풀었는데 2개가 실패! 이게 틀린 코드인데 다시 보니 return이 N이 3일 때부터 가능해서 1부터 가능하도록 range 범위를 바꿔줬다. 1, ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사용 언어 Python3 풀이 과정 앗 이 문제는 첫 번째 제출에서 3개의 테스트 케이스가 실패였다! 이게 틀린 코드인데 q.popleft() 해서 얻은 num에 대한 방문처리가 빠진 것 같았다. 그런데 코드를 다시 보니 방문처리 부분이 불필요하게 겹쳐서 num에 대한 방문처리만 남기고 수정했더니 통과했다. from collections import deque ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사용 언어 Python3 풀이 과정 bfs로 풀었는데 간단한 편이라서 한 번에 통과! 추가로 효율성 점수가 있었는데 이게 높은건지 낮은건지 구분이 안가서 아래에서 다른 사람들의 코드도 돌려보았다. 실수할 뻔 한 건 처음에 무조건 N * N의 정사각형으로 입력이 주어지는 줄 알았는데 조건을 다시 읽어보니 N * M으로도 제시가 될 수 있지만 예시가 정사각형 모양인 것 뿐이었다..ㅎㅎ 항상 입출력..