기록

문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 1) dfs 깊이/너비 우선 탐색을 할 때 재귀를 잘 사용하지 않았다. 이 문제를 반복문으로 풀었더니, pypy3로 제출하더라도 시간초과가 발생했다. (물론 이 방법으로 푸는 다른 방법도 있겠지만... ) 백트래킹이 필요한 경우에 기존에는 stack에 배열 자체를 넣어서 반복문을 돌렸는데, 이런 경우 재귀를 사용할 수 있음을 알아두자. 2) 논리 unknown에 0으로 표시된 위치..

문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 2부터 N까지의 소수를 구하고, Two Pointer 을 이용해서, 합이 N이 되는 경우를 찾는다. 1) 에라토스테네스의 체 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소..

문제https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를programmers.co.kr풀이문제에서 주어진 방법을 따라 그대로 구현한다.1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수..

문제 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 풀이 1) 패턴 파악하기 1의 자리수는 (0, 1)이 반복된다. (0이 1개, 1이 1개) 2의 자리수는 (0, 0, 1, 1)이 반복된다. (0이 2개, 1이 2개) 4의 자리수는 (0, 0, 0, 0, 1, 1, 1, 1)이 반복된다. (0이 4개, 1이 4개) ... 2**n의 자리수는 (0...., 1....)이 반복된다. (0이 2**n개, 1이 2**n개)..

문제https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오programmers.co.kr풀이userDict에 유저의 아이디와 닉네임을 저장해둔다.log에 유저의 행동을 uid로 저장해두었다가,모든 기록을 읽고 난뒤 uid를 닉네임을 바꾸어 출력한다.코드def solution(record): # record 읽고 기록하기 userDict = dict() log = list() for item in record : ..

문제https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문programmers.co.kr풀이문자열이 "a"처럼 1자리일 때를 고려해야 한다. 1. 문자열을 주어진 길이(unit)으로 자른다.2. 잘린 문자열당 연속하여 출현하는 횟수를 구한다.3. 연속 출연 횟수가 1인 문자열의 개수를 센다. (1을 표현하지 않으므로)4. 압축된 문자열의 길이에서 1의 개수를 뺀다.5. unit의 크기를 1에서 문자열의 절반까지 늘려가면서 1~4를 반복한다.코..

문제https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서programmers.co.kr풀이1. 조건에 맞는 메뉴 조합 만들기2. 메뉴 조합별 빈도 세기코드from itertools import combinationsfrom collections import defaultdictdef solution(orders, course): answer = list() for count in course : menu_items =..

문제https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물[[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6programmers.co.kr풀이1. 누적합 구하기[EX] (0, 1)에서 (3, 3)까지 2로 채운다고 하자.모서리가 되는 4개의 점에 각각의 값을 넣는다.board[0][1] = +2board[0][4] = -2board[4][1] =..