(백준, 파이썬)블랙잭블랙블랙잭잭블랙 (06-28 해결)
2022. 6. 28. 16:48
PS/BOJ
(2022-06-14) 최근 CS50을 수강하면서, 시간복잡도와 의사코드에 대해 알게 되었다. 시간복잡도는 아직 익숙하지 않고, 더 배워야할 것 같지만, 의사코드는 이전에 내가 문제를 풀면서 주석을 달듯이 먼저 설계해보는 그런 과정인 것 같다. 이 스타일이 맘에 들어서 앞으로 문제를 풀 때는 의사코드를 작성해보고 구현하는 연습을 해보려고 한다. + 시간복잡도도 구해보고! --- 2주가 지난 지금 드디어 풀었다. -오늘 풀 문제- 브루트포스 알고리즘(Brute Force) : '야만적으로', '꼼꼼히', '모든 경우'를 찾는다. 2798 - 블랙잭 (https://www.acmicpc.net/problem/2798) 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘..
(백준, 파이썬) 분해합
2022. 6. 28. 11:47
PS/BOJ
2231 - 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. -맞힌 코드- 1 2 3 4 5 6 7 8 9 10 11 12 13 14..
네이버 부스트캠프 1차 코딩테스트 후기
2022. 6. 27. 22:03
Daily/일기
오늘 내 소감이다. 코딩을 시작한지 벌써 50일이 되었다.. 좋은 환경에서 동료들과 함께 공부해보고 싶어서, 네이버 부스트캠프에도 지원해봤다. 인터넷 검색이 가능했기 때문에 기존에 알음알음 알아 놓은 CS + 정보검색능력으로 객관식을 어느 정도 괜찮게 채우는 데에는 성공했지만.. 코딩 문제로 들어가는 바로 그 순간! 백준 물실버인 나에게는 너무나도 폭력적인 비주얼과 가혹한 환경.. 특히 IDE 못 쓰는게 컸다. 은혜를 갚기 위해 까치들이 종에다가 스트레이트로 헤딩을 박는 느낌이 바로 이 느낌이 아니었을까..? 의사코드만 주절주절 쓰고 (교수님 사랑해요 코딩ver) 0솔로 끝났다. 아직 입과 난이도가 있는 교육을 듣기에는 부족한 것 같다. 원래 읽으려던 책이랑, 강의랑, 프로젝트들 마저 해야지. 알고리즘 ..
(백준, 파이썬)문자열 ★폭발★
2022. 6. 25. 16:02
PS/BOJ
9935 - 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. 입력 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보..
(백준, 파이썬)비루스
2022. 6. 23. 19:51
PS/BOJ
2606 - 바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸..
(다시)DFS & BFS 찍먹
2022. 6. 23. 18:11
CS/자료구조-알고리즘
나는 이 포스트를 다시 봐야할 때에, 밑의 DFS 예제를 재귀함수 / 스택으로 구현해봐야하고, BFS 예제를 큐로 구현해봐야하고, 음료수 얼려먹기 / 미로 찾기 문제를 풀어야한다. 1번 노드와 연결되어 있는 것 [2, 3, 8] 2번 노드와 연결되어 있는 것[1, 7] 이런 식이다. 그리고, 방문 여부를 표현하는 1차원 리스트를 정해준다. 1번 노드로 시작한다 (방문 1) 1번 노드와 인접한 노드들 중 방문하지 않은 노드[2, 3, 8]로 굴린다. 2부터 시작한다. 2는 방문하지 않았으므로, 재귀한다 2번 노드로 시작한다 (방문 1, 2) 1은 방문 했으므로 7로 재귀한다. 7번 노드로 시작한다 (방문 1, 2, 7) 2는 방문 했으므로, 6으로 재귀한다. 6번 노드로 시작한다 (방문 1,2,7,6) 7..
(백준) 3111 - 검열(실패)
2022. 6. 22. 23:03
PS/BOJ
검열은 사랑.. 돈? 문제 김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다. 상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모두 없애려고 한다. T에 A가 없으면 알고리즘을 종료한다. T에서 처음 등장하는 A를 찾은 뒤, 삭제한다. T에 A가 없으면 알고리즘을 종료한다. T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다. 1번으로 돌아간다. 상근이는 마을을 지배해야하기 때문에, 검열을 할 시간이 없다. 상근이의 검열을 대신해주는 프로그램을 작성하시오. 입력 첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다. 출력 검열을 한 이후의 텍스트를 출력한다. - 틀린 ..
구현 - 좌표이동 / 조건부 시각 세기 / 왕실의 나이트
2022. 6. 22. 21:55
CS/자료구조-알고리즘
- 내가 쓴 코드 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 # NxN 지도를 만들 것인가? N, 그냥 좌표로 움직여도 될 듯. # 무시되는 제한 조건을 구현해야 한다. # LRUD를 구현해야 한다. N = size = int(input()) commands = list(input().split()) class traveler: def __init__(self): global size self.position = [1, 1] #y, x좌..
(프로그래머스, 파이썬) 정렬 : [K번째 수, H-index, 가장 큰 수]
2022. 6. 22. 12:51
PS/프로그래머스
레벨 2부터 벽을 느끼는 나.. 역시 물 실버였다. 코딩테스트 연습 - 정렬 - K번째 수 -내 코드- def solution(array, commands): answer = [] for cmd in commands: i, j, k = cmd array_processed = sorted(array[i-1:j]) answer.append(array_processed[k-1]) return answer 딱 눈에 보이고 이해되는 대로 풀었다. -신박한 풀이- def solution(array, commands): return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands)) 허허.. 차근차근 알아보자 array를 [i-1 : j]까지 슬라이스,..
그리디 알고리즘
2022. 6. 21. 23:18
CS/자료구조-알고리즘
나동빈님의 이것이 코딩 테스트다 강의를 이용해서 공부하고 있다. 신찬수 교수님 강의도 짬짬이 병행하고 있는데, 원론 + 실전문제풀이 느낌이라 딱 좋다. - 맞힌 코드 - N이 10만까지이므로, 내 풀이방법처럼 할 수야 있지만, 좌측의 풀이방법의 시간복잡도에 비해 내 풀이의 시간복잡도가 높다. (n - target)으로 덩어리로 쳐내냐 vs (n-target)만큼 반복으로 -1로 쳐내냐 29와 5를 입력했다. 29와 5의 1차 타겟은 25다(가장 가까운 5로 나눌 수 있는 수) 29에서 25까지 4(N - target)를 빼야하므로, 시행횟수는 4가 더해진다(result +=) 그렇게 N은 target과 동일해진다. 25 < 5는 거짓이기 때문에 넘어간다. 25를 5로 나누고, 시행횟수를 1 더한다. (1..