시나위

https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 손풀겸 푸는 문제 딕셔너리 자료형을 사용해서 '0'부터 '9'까지 그리고 'A'부터 'Z'까지 생성한뒤 각 자리에 맞는 값을 구해서 계속 더해주었다. import sys nums_dict = dict(zip( map(chr, range(ord('A'), ord('Z') + 1)), range(ord('A') - ord('A') + 10, ord('Z') - ord('A') + 11) )) for i..

https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 확률 Z값을 구하고, s와 e의 중간값으로 만든 새로운 확률이 Z보다 큰 값을 찾으면 된다. 그리고 커지는 값중에 최솟값을 찾아야하니 s가 e보다 커지는 값을 종료 조건으로 반복문을 설정해서 이분탐색을 하면 된다. def main(): X, Y = map(int, input().split()) Z = (Y * 100) // X s, e = 0, X while s

https://www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net 문자열은 파이썬이 편하다. 마지막에 f가 있을거라 예상해서 f를 기준으로 단어를 나눴다(인덱스만 저장). 그리고 각각의 인덱스를 기준으로 4의 배수인지 확인하면 wwwoolllfff 같이 중간에 하나 빠져있는 단어들을 제거할수 있다. 그다음은 wlof 와 같은 단어를 제거한다. 나누어진 단어의 길이를 4로 나누면 한 단어당 나와야하는 알파벳의 갯수가 나온다. 이 개수로 wolf 각각 문자열을 곱하고 더해서 단어를 만들고 원래 기존의 단어와 비교하면 제거할수 있다. 여기까지..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net pypy에선 되는데 python에선 시간초과와 메모리 초과가 뜬다. python에서 하려면 다른 방법으로 접근해야한다. 문자 테이블을 만들어서 두 문자열을 비교했다. 비교하는 알파벳이 같으면 1로 체크하고, 같지 않으면 0으로 체크한다. 여기서 공통부분 문자(1이 체크된 것)에서 대각선 방향으로 가장 긴 배열찾으면된다. 길이를 알아야하므로 memoization을 실행할때 공통문자이고, ..

1. 작심이주 블로그도 알고리즘으로 꾸준히 작성중이다. 영어도 Duolingo 어플리케이션을 사용해서 매일 단어 공부중이다. 아직 어렵진않은데 현재 완료 구문은 이해가 잘 가지 않고 문장을 봤을때 해석을 바로하긴 어렵다. 하지만 이번주는 CS 공부를 하지 못했고, 운동도 못했다. 다행히 주간회고는 작성 중이다. 2. 취업 준비 취업을 위해 여러 단계를 거치고 있다. 자기소개서도 많이 작성했고, 코딩테스트도 여러개 봤다. 다음주엔 면접도 몇개 있는데 이번 주말은 면접 준비 할 겸 나를 위한 글이라는 글을 쓰고 있었다. 면접 준비가 되고 있는지는 잘 모르겠고 그래도 프론트엔드에 중요한 지식들을 다시 배우고 있는 느낌이다. 다음주에 당장 면접인데 어떻게 준비를 해야할지도 모르겠다. 자기소개라도 준비해야지.....

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분탐색 문제이다. 높이를 오름차순으로 정렬하고 시작점은 0, 끝점은 가장 큰 값(정렬했으므로 마지막 값)으로 설정해서 이분탐색을 한다. 합이 M보다 작거나 같을때는 최솟값을 올리고, 작을때는 최댓값을 내려서 탐색한다. 이때 합도 이분탐색으로 찾는데 처음에 누적합을 구하고, 처음으로 목표값 보다 커지는 인덱스를 찾으면 해당 구간에서의 합을 쉽게 구할수 있다...

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 손 풀 겸 푼 문제. 백트래킹을 사용해서 모든 조합을 만들어내면 된다. 조건이 별로 걸지 않아서 dfs와 차이가 없다. visit = None numbers = None ans = None def backtrack(ind, limit, total, prev): global visit, numbers, ans if ind == limit: ans = max(ans, total) return for i in ran..

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 모든 값을 탐색하면서 이전보다 큰 값인 경우에만 백트래킹하는 방법으로 풀었다. desc_nums = [] visit = [False for _ in range(10)] def make_number(visit): ret = 0 for i in range(9, -1, -1): if visit[i]: ret = ret * 10 + i return ret def backtrack(ind=-..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션을 요구하는 삼성 느낌의 기출이다. 주어진 조건대로 만들어주기만하면 되는데 그게 너무 오래걸리는 문제여서 구현이 오래걸렸다. 완전탐색으로 맵에 그렸다가 지웠다를 반복하면 값이 나온다. import sys; input = sys.stdin.readline answer = None N, M = None, None cctv_list, d_map, r_map = None, None, ..

https://www.acmicpc.net/problem/11811 11811번: 데스스타 젊은 제다이 이반의 임무는 데스스타에 침투하여 파괴하는 일이다. 데스스타를 파괴하기 위해서는 길이 N의 음이 아닌 정수 수열 ai가 필요하다. 그러나 이반은 이 수열을 가지고 있지 않다. 대 www.acmicpc.net 손 푸는 문제 n_ij는 a_i와 a_j가 겹치는 비트를 보여주므로 bitwise 연산자 or로 모두 합치면 쉽게 풀수 있다. import sys; input = sys.stdin.readline def main(): N = int(input()) ans = [0 for _ in range(N)] for i in range(N): for nij in map(int, input().split()): ..