성장기록지

문제   풀이트리를 순회하며 각 노드의 번호를 구하는 문제이다.트리는 중위순회를 진행하라고 설명에서 작성되어 있다.(중위순회란? LEFT - ROOT - RIGHT 순서대로 순회하는것.) 재귀를 통하여 문제를 풀고자 하였다.한 노드의 왼쪽 자식노드 인덱스는 2^n+1 이고 오른쪽은 2^n+2 이기 때문이다.따라서 아래와 같이 재귀함수를 구성하였다.def back(n): if n>=max_count: return back(2*n + 1) ans[n] = lst.popleft() back(2*n + 2) 루트 노드들은 먼저 입력받은 숫자에서 가장 왼쪽 값을 빼서 넣어주며 정답 리스트인 ans를 완성하였다. 이후에  for문을 통해 각 레벨마다 값을 출력해주며 마무리하였다. ..

문제풀이같은 단어를 그리디를 통해 어떻게 최대값과 최소값을 구별하는지가 목표인 문제다. 나는 다음과 같이 설정하고 문제를 풀었다. 최댓값은 M의 값들을 모두 10으로 곱해 누적한 뒤 K를 만나면 최종적으로 5를 곱해 처리.최소값은 M의 길이에 따라 지수 계산 (10^(길이-1))으로 값을 처리하며, K는 5를 직접 추가생각보다 쉽게 풀려서 놀랐던 문제이다. 코드n = input()num=''ans_lst=[]for i in n: num= num+i if i=='K': temp=1 for j in num: if j =='M': temp= temp*10 elif j=='K': tem..

문제풀이 예시와 같은 ABCDE가 있다는 뜻은, 그래프 안의 특정 노드에서 5개 이상 연결되어있는 것이 있는지 묻는 것과 같다.따라서 dfs를 통해서 그래프들을 탐험하게 하였고, 그중에 5개의 이상 노드가 연결되어 있을 때 (cnt>=4 일 때)ans를 1로 만들어 1을 출력하게 하였다.from collections import defaultdictimport sysinput = sys.stdin.readlinelimit_number = 15000sys.setrecursionlimit(limit_number)dic = defaultdict(list)n,m = map(int,input().split())for i in range(m): a,b= map(int,input().split()) dic..

.문제https://www.acmicpc.net/problem/14888초기 풀이많이 생각할 것 없이, 백트래킹을 통해서 문제를 해결하면 된다 .처음에는 아래와 같이 연산자들을 담는 giho라는 리스트를 활용해서 연산을 진행해주었다.하지만 그러기 위해선 visited 리스트도 활용해야 하였고, visited에 있는지 확인해주느라 시간이 많이걸렸다.n=int(input())nums = list(map(int,input().split()))lst = list(map(int,input().split()))giho = []for i in range(lst[0]): giho.append('+')for i in range(lst[1]): giho.append('-')for i in range(lst[2]..

문제https://www.acmicpc.net/problem/2668풀이아래줄의 숫자가 윗줄과 같을 때, 그래프에 넣어준다고 하면 예시 문제는 다음과 같이 표현할 수 있다.1: [2, 3]2: []3: [1]4: [6]5: [4, 5]6: [7]7: [] 이 그래프를 그림으로 그린다면,아래와 같이 표시할 수 있게 된다. 정답인 1,3,5가  사이클로 돌아가는 것을 알 수 있다. 이 문제는 그래프를 dfs탐색하여, 사이클이 생길때마다 것을 정답 리스트에 보관하여 해결할 수 있는 것이다.풀이 코드from collections import defaultdictn=int(input())dict = defaultdict(list)def dfs(x, visited): visited.add(x) check..

문제링크 : https://leetcode.com/problems/reorder-data-in-log-files/문제 해석조건에 맞게 로그를 재정렬해라.1.로그의 가장 앞부분은 식별자로서, 순서에 영향을 끼치지 않는다.2.문자로 구성된 로그가 숫자 로그보다 앞에 오며, 문자 로그는 사전순으로 한다.3.문자가 동일할 경우에는 식별자순으로 한다.4.숫자 로그는 입력 순서대로 한다.  문제 해결문자로 구성된 로그는 코틀린의 sortwith을 활용하여 세부 조건에 맞는 정렬을 하였다. sortwith()이란??Comparator를 지정할 수 있습니다. 즉, Comparator를 변경해 자신이 원하는 조건으로 리스트를 정렬하는 것 입니다.  해결 코드class Solution { fun reorderLogF..

문제https://www.acmicpc.net/problem/2636문제 해결치즈가 공기중에 만나면 녹는다는 설명이 제일 중요하다.공기가 정확히 무엇인지 설명해주지 않아서 유추하느라  시간이 많이 걸렸다..여러 가설끝에 찾아낸 정답을 설명해보겠다. 아래 그림을 보면 c가 다음 시간에 녹는 치즈들을 표시해둔 것으로,하얀색 부분이 공기라 맞닿은 면이 녹는건가? 라는 생각을 했다.하지만 그렇게 가정하면 빨간색 화살표로 표시된 곳의 하얀색 부분도 공기인데맞닿은 면들이 녹는 표시가 없으므로,하얀색 면은 빈 공간이라 공기가 있을수도 있지만치즈로 둘러쌓인 하얀색 면은 치즈 안쪽이라 공기가 없구나 라는 생각을 하게 되었다.   그렇다면 항상 치즈 바깥에 있는 빈 공간 에서부터, 하얀색 면들을 bfs로 전부 탐색한 후 ..

간단한 팰린드롬 문제를 무작정 구현하려다 많이 고생하여서팰린드롬을 만드는 알고리즘을 이해하고자 블로그 글을 작성합니다.1. 팰린드롬이란?거꾸로 읽어도 똑같은 문장이나 단어를 말한다.예를틀면 eye,hannah, AABCBAA 같은 단어가 있다.좌우대칭이라고 생각하면 좋다.2. 팰린드롬이 될 수 있는 단어의 조건은?-> 문자의 개수가 홀수인 문자는 하나 이하여야 한다.팰린드롬은 좌우 대칭이어야 하므로 홀수개인 문자는 하나만 중앙에 둘 수 있다.예를 들어 eye는 e는 2개, y가 1개로 홀수인 문자가 y 뿐이라 팰린드롬이지만eyde면 e는 2개, y는 1개, d도 1개로 홀수인 문자가 2개나 있어서문자의 배치를 바꿔도 팰린드롬이 될 수 없다. 3. 입력한 단어를 팰린드롬으로 바꾸자!1.개수가 홀수인 문자는..

문제https://www.acmicpc.net/problem/16926문제 해결배열을 조건에 맞게 한칸씩 반시계 방향으로 돌리는 문제이다.가로와 세로의 길이 중 작은값은 항상 짝수라는 조건이 있어서 가로 세로가 둘다 홀수일때의 예외처리를 해주지 않아도 되어서 좋았다.만약 둘 다 홀수인 아래의 그림(N=5,M=7) 보면, 17~19까지 반시계로 회전을 할 수 없게 된다.   구조 설계많은 변수와 함수가 필요하다고 생각되어 하나씩 설계해 나갔다.초기의 배열을 의미하는 nums ,회전 후 정답 배열을 의미하는 ans 를 구성하였고,가로와 세로의 길이가 각자 다를 수 있으므로,x와 y가 배열을 순회할때 가능한 시작점과 끝점을 의미하는x_min, x_max 와 y_min, y_max 변수를 만들었다.그 후 위의 ..

문제https://www.acmicpc.net/problem/17413문제 해결구현문제를 누가 봐도 이해가 가게 깔끔하게 풀기위한 연습문제로 선택하였다.처음엔 쉽게 시작한답시고 고른 실버3 문제인데 생각보다 고생을 많이했다.. 좋은설계를 위해 우선 노트에 구현해야할 구조들과  예시코드를 작성하였다. 근데 글씨를 너무 못써서 따로 타이핑하여 작성하도록 하겠다.노트는 맨 아래에 있으니 참고하실 분은 참고...    구조 설계 기본 설계입력받은 문자열(string)에  인덱스 0번부터 마지막까지 반복하는 반복문을 작성한다. -> while idx반복하며 만나는 인덱스 별 문자들은 덱(deque) 에다가 append한다. 세부 설계1. '(in_tag)를 True로 전환한다.2. '>'이 보이면 덱의 길이만큼 ..