Dalin's Archive

문제 보러 가기! 설명 😎 구현 문제였다! 처음에는 퍼즐판이 주어져서 뭔가 2차원 배열로 풀어야 하나? 했지만, 문제를 찬찬히 읽어보니 아니었다. 표의 정중앙에 있는 글자만 꼭 사용해야 하니까, 그 글자만 중요하게 고려하면 된다. 또 어떤 글자를 정중앙에 놓았을 때 정답 개수가 가장 적게/많게 되는지를 찾아야 한다! 그러니까 각 글자가 사용되는 횟수를 구하면 된다. 퍼즐판의 문자들이 주어질 때, 그 문자를 가지고 사전의 단어를 만들 수 있는지 본다. 만들 수 있다면, 각 글자의 사용 횟수를 1씩 더한다. 사전의 단어를 모두 본 후에, 글자 중에 가장 적게/많이 사용하는 글자(사전순)와 그 개수를 출력하면 된다!! 헷갈렸던 부분 🤔 퍼즐판에서 주어진 문자들을 가지고, 사전의 단어를 만들 수 있는지 체크하는..

문제 풀러 가기!! 오 ㅎㅎ 재밌는 BFS 문제였다. 처음에는 어떻게 풀지 고민되어서 문제 분류를 봤다. BFS 라고 하니 감이 와서 풀 수 있었다! 보통 너비 우선 탐색을 하면 2차원 테이블 안에서 가장 빨리 도착하는 식으로 풀었는데, 직선 상에서 오리, 육리가 만나는 걸 찾아서 특이했다. 또 보통은 하나에서 출발해서 고정된 도착점을 찾는 식이었는데, 이번에는 오리, 육리가 둘 다 움직여서 독특했다. 오리, 육리가 만날 수 있는 최소 일수를 구해야 하므로 BFS를 사용했다. 1. 오리, 육리의 (점프 횟수, 위치, 이름)을 q에 넣었다. 2. q가 있는 동안 while문을 돌렸다. 2-1. q에 있는 원소를 popleft로 꺼냈다. (먼저 들어온 걸 먼저 꺼냄) 점프 횟수, 위치, 오리인지 육리인지가 ..

문제 보러가기 구현, 시뮬레이션 문제였다. 처음에는 '어떻게 윷판 위 현재 위치를 나타내지?' 고민했는데, 4가지 루트가 있다는 걸 보고 그걸 이용해서 문제를 풀었다. 현재 어떤 루트로 가고 있는지 나타내는 course, 말의 위치를 idx로 두었다. 위 그림 순서와는 다르게, 나는 빙~ 돌아가는 걸(위 그림에서 4번) 0, 첫번째 갈림길에서 꺾이는 걸(위 그림에서 3번) 1, 젤 빠른 길(위 그림에서 1번)을 2, 위 그림에서 2번을 3으로 뒀다. 그 뒤에 윷을 던져서 앞으로 가는 칸수에 따라서 idx를 바꿔준다. 이때 주의점은 다 앞면이거나 다 뒷면이면, 윷 던질 기회를 한번 더 준다는 것! 그래서 while을 이용해서 처리했다. 지름길을 만나면 지름길로 간다. 위에서 바꾼 idx를 이..

문제 풀러 가기 문제가 참 재밌다..ㅋㅋㅋ 그리디로 풀었다. 쭉~~ day 리스트에 튜플로 정보를 입력받았다. 이때 꼭 시작해야 하는 날(꼭 끝내야 하는 날 - 과제할 때 걸리는 일수 +1)을 구해서, (이날에는 꼭 시작해야 하는 날, 과제 할 때 걸리는 일수, 이때까지 꼭 끝내야 하는 날)형식의 튜플을 만들어서 리스트에 넣었다. 리스트를 정렬하는데, 꼭 끝내야 하는 날 기준으로 내림차순으로 정렬했다. 오늘로부터 먼 순서대로 과제를 해야, 내일부터 가장 오랫동안 놀 수 있는 날을 구할 수 있으니까. now는 과제를 시작하는 날을 의미한다. 일단 첫번째 과제를 시작하는 날은, 최대한 늦게 시작하는 게 좋으니까, 과제를 꼭 시작해야 하는 날로 초기화해서 시작한다. 그 다음부터는 두번째 과제부터 마지막 과제까..

문제 보러 가기!!! 예전에 틀린 코드💫 DFS로 풀려고 했던 듯. 예제는 맞추는데, 채점을 하면 메모리 초과가 난다. import sys sys.setrecursionlimit(10**6) def DFS(depth,score): if depth==k: if score>0: A.append(score) else: DFS(depth+1,score+L[depth]) DFS(depth+1,score) if __name__ == "__main__": k=int(input()) L=list(map(int,input().split())) A=[] DFS(0,0) A=list(set(A)) for i in range(1,max(A)): if i not in A: print(i) break 정답 코드 💟 아이디어가 정..

문제 보러 가기 DP로 풀었다 !! 특정 숫자의 가격은 딕셔너리에 저장해뒀다. (그런데 생각해보니 어차피 0~ N-1 순서니까 그냥 리스트에 가격을 저장했어도 될 것 같다.) dp 리스트의 인덱스는 돈, 값은 그 돈으로 살 수 있는 제일 큰 방 번호를 의미한다. 각 값은 '-'으로 초기화해뒀다. 처음에는 0으로 했는데, 그러면 숫자 0을 살 수 있다는 뜻인지, 아무것도 못 산다(or 안 샀다)는 뜻인지 구분이 안가서 '-'으로 했다. 그 후에 dp 세팅을 했다. 각 숫자를 하나 사는 경우를 dp에 넣어줬다. dp[그 숫자의 가격] = 그 숫자 로 해줬다. 그 다음에는 본격적인 DP! 숫자 가격이 젤 작은 것 X 2부터 M까지 쭉 ~ 보는데, 그 지점에서 각 숫자 가격을 뺀 위치의 값과 비교했다. 다시 말..

https://www.acmicpc.net/problem/16196 16196번: 중국 신분증 번호 첫째 줄에 신분증 번호가 주어진다. 신분증 번호는 18자리이고, 처음 17자리는 0부터 9까지 숫자로만 이루어져 있다. 마지막 1자리는 0부터 9까지 숫자이거나 'X'이다. 둘째 줄에는 올바른 지역 코 www.acmicpc.net 그냥 꼼꼼하게 조건을 고려해서 풀면되는 문제였다!!!! 고려할 게 많은데 자꾸 빠뜨려서.. 많이 틀렸다. - 지역 코드 6자리 -> 가능한 지역 코드를 리스트에 저장한 후 in으로 판단함 - 생일 코드 -> 년, 월, 일 따로 처리. 일을 처리할 때 그 달이 몇 일까지 있는지(30 or 31), 2월인 경우 윤년인지 체크해야 함 - 순서 코드 -> 000은 안된다. 짝수이면 여자..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 예전 코드(시간 초과) import heapq as hq N=int(input()) a = [] for _ in range(N): n = int(input()) if n == 0: if len(a) == 0: print(0) else: tmp=-hq.heappop(a) # 루트 노드 값 print(tmp) else: hq.heappush(a, -n) -> 잘 짜서 놀랐다(??)..

1년 전에 틀렸던 문제를 풀어봤다. 이번에는 과거의 나에게 알려주는 말투로 적어보려고 한다. ㅎㅎ 만우절이니까..ㅎㅎ 문제 보러 가기 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 안녕! 베르트랑 공준 문제구나. 와 저런 수학적인 명제가 있다니 정말 놀랍네. 음 이 문제는 뭐가 포인트일까? 맞아 맞아~ 소수를 구하는 게 포인트겠지~ 너는 어떻게 풀었는지 볼까? while True: n=int(input()) if n == 0: exit() for i in range(n+1,2*n+1): if n==1..

TMI 일기 다음 주는 싸피 프로젝트 마지막 주이다..! 다들 프로젝트하느라고 바빠서 알고리즘 스터디를 쉬기로 했다. 그래도 오랜만에 문제를 풀고 싶어서 백준에 들어왔다. 무슨 문제를 풀까 하다가 '내가 못 푼 문제'를 눌러봤다. 내가 전에 풀다가 실패했던 문제들도 나와서 그것들을 풀어봤다. 먼저 풀 문제는 소인수 분해 문제~~ https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 💦1년 전에 시간초과 나온 코드 N=int(input()) # N이하 소수 찾아서 리스트 S에 넣기 S=[2,3] for i in range(4, N+1): if i%2==1: for j i..