yeony's story

https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 이분 탐색으로 풀려다 실패하고 결국 다이나믹 프로그래밍으로 푼 문제다 ^0^ 사실 이것도 구글링...해서 겨우 이해한 문제ㅜㅜㅜ power=max(a,b) 이 부분이 이해가 되지 않아서 애를 먹었다. a에 들어가는 건 j번째 -> i번째로 이동할 때 쓰여지는 힘 b에 들어갈 건 j번째까지 탐색을 진행했을 때 구해진 최소의 힘이다. 앞에서..

> 이분 탐색 https://www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 이분 탐색 문제를 풀 때마다 헷갈렸던 거! left, right 값에 인덱스를 넣어야할 때도 있고, 0,max(array)처럼 0과 배열의 최댓값을 넣어줘야 풀리는 문제도 있었다. 근데 언제 인덱스를 넣어야하는지, 최댓값을 넣어줘야하는지 기준이 잡히지 않아서 헤맸던 문제다. 1. 문제에서 값을 구하라고 하는 문제 > 배열의 최댓값을 right에 넣어줌. l..

> 이분탐색 https://www.acmicpc.net/problem/1654 k, n = map(int, input().split()) array = [int(input()) for _ in range(k)] left = 1 right = max(array) result=0 while left [2792] 보석상자 in python > 이분탐색 평소에는 이분탐색을 풀 때 cnt==n일때, cnt cnt>n일때 각각 조건을 나눠 계산을 진행해줬다. 그러나 이번 문제처럼 최솟값이나 혹은 최댓값을 구할 땐 위 방식보다는 아래 코드와 같이 eboong.tistory.com

> 벨만포드 알고리즘 다익 스트라 : 모든 간선의 비용이 양수일 때 최단 경로를 구할 수 있다. 심지어 음수간선이 포함되어 있더라도 해당 간선이 순환되는 구간이 없으면 된다. https://youtu.be/Ppimbaxm8d8 그러나 음수 간선이 순환되는 경우에는 다익스트라는 사용할 수 없고, 벨만 포드 알고리즘을 사용해야한다. 1. 출발 도시 설정 2. 최단 거리 테이블 무한으로 초기화 3. 벨만 포드 알고리즘 시행 3.1. 다음 과정을 n-1번 반복한다. 3.2. 만약 dist[a]의 값이 무한이 아니고, dist[b]의 값이 dist[a]+c값보다 크면? dist[b]에 dist[a]+c, 최단경로를 넣어준다. 3.3 만약 현재 i가 n인데도 갱신이 이뤄졌다면? -> 음수..

> dfs dfs 개념을 다시 짚고 넘어가자.. 갑자기 막 헷갈림 ㅠㅠ (1) 재귀함수를 이용한 dfs 구현 방문처리는 함수 맨 첫줄에...! 방문하지 않은 노드가 있다면 재귀함수만 호출시킴. def dfs(node): visited[node]=False # 현재 노드 방문처리 for i in array[node]: # 현재 노드와 연결된 노드들중에 if not visited[i]: # 방문하지 않은 노드가 있다면 dfs(i) # dfs(i) 재귀함수 호출 (2) stack을 이용한 dfs 구현 방문처리는 while문 안에서..! 방문한 노드가 아닐 경우의 조건문 안에서! def dfs_iteration(graph, root): visited = [] stack = [root] while(stack): ..

> 깊이 우선 탐색 > 그래프 탐색 아래와 같이 코드를 작성해서 제출했더니 재귀 관련 오류가 났다. n, r, q = map(int, input().split()) tree = [[] for _ in range(n + 1)] for i in range(n - 1): a, b = map(int, input().split()) tree[a].append(b) tree[b].append(a) query = [int(input()) for _ in range(q)] def check(node): count[node] = 1 for child in tree[node]: if not count[child]: check(child) count[node] += count[child] return count[node] ..

> bfs 문제 최소 경로를 출력해야한다길래 max로 매번 경로횟수를 체크해줘야하나 생각했으나 1칸씩 이동할때마다 +1씩 증가시키고 도착점에 도착하면 현재 횟수를 출력한다. 큐에 cnt 횟수까지 넣으면 메모리초과 남.. from collections import deque n = int(input()) r1, c1, r2, c2 = map(int, input().split()) # 1~6번 순으로 dx = [-2, 0, 2, 2, 0, -2] dy = [1, 2, 1, -1, -2, -1] def bfs(): queue = deque() queue.append((r1, c1, 1)) visited = [[False for _ in range(n)] for _ in range(n)] visited[r1][..

> 문자열 예시는 s= abab 1번째 생각) s = s + s[0] 위 식은 위 예시에만 성공적 2번째 생각) s=qwerty s=s+s[len(s)-1::-1] qwerty + trewq = qwertytrewq 위 예시에서는 성립. 하지만 abab + aba abababa 똑같이 역으로 해도 똑같은 값이 나오긴 하지만 가장 짧은 팰린드롬을 만드는 방법은 아니다. 3번째 생각) s = abdfhdyrbdbsdfghjkllkjhgfds 위 예시에서 2번째 방법을 대입했더니 53이 나옴 나와야하는 답은 38... 그래서 다시 살펴봄 문자열 내 부분 문자열이 팰린드롬일 경우를 생각해줘야한다. 만약 팰린드롬이 문자열 끝부분에 위치해있다면? 2번째 방법을 사용하면 가장 짧은 팰린드롬을 구할 수 없게 된다. s..

> 이분탐색 평소에는 이분탐색을 풀 때 cnt==n일때, cntn일때 각각 조건을 나눠 계산을 진행해줬다. 그러나 이번 문제처럼 최솟값이나 혹은 최댓값을 구할 땐 위 방식보다는 아래 코드와 같이 작성을 해야한다. if cnt > n: left = mid + 1 else: # cnt [2805] 나무 자르기 in python >> 이분 탐색 >> 정렬 처음에는 left, right의 값은 인덱스 값이 아닌 현재 톱날의 높이에 기준을 맞춰 지정해주어야 한다. sorted를 하고 array[n-1]로 최댓값을 구하는 것보다 max(array)로 하는게 실행속 eboong.tistory.com

>> 이분 탐색 >> 정렬 처음에는 left, right의 값은 인덱스 값이 아닌 현재 톱날의 높이에 기준을 맞춰 지정해주어야 한다. sorted를 하고 array[n-1]로 최댓값을 구하는 것보다 max(array)로 하는게 실행속도를 더 빠르게 한다! n, m = map(int, input().split()) array = list(map(int, input().split())) left = 0 right = max(array) while left

1. .gitignore 파일 생성하기. 새로 만든 프로젝트를 깃허브 원격 저장소에 올리게 되면 불필요한 파일이나 폴더가 같이 올라가는 걸 확인할 수 있다. 예를 들면 .build 폴더나 .gradle , .idea 와 같이 원격 저장소에서 관리할 필요가 없는 폴더들 말이다. 따라서 지금부터 저 불필요한 폴더들을 깃허브 원격 저장소에서 숨겨보려고 한다. 그러려면 .gitignore 파일이 필요한데, 간단하게 운영체제, 사용언어 등만 작성해주면 간단하게 파일을 만들어주는 사이트가 있다. https://www.toptal.com/developers/gitignore gitignore.io Create useful .gitignore files for your project www.toptal.com 위와 같..

git push 를 할 때 자주 마주치는 에러라서 기억하기 위해 기록함. 에러 메세지와 함께 뜨는 힌트 메세지 푸쉬를 하기 전 pull 을 먼저 진행하라고 해서 pull 을 진행했다. 그랬더니 해결되지 않은 충돌 상황이 발생했다고 Pull is not possible because you have unmerged files 에러 메세지가 뜨면서 pull 명령어도 먹히지 않았다. 찾아보니 로컬 저장소와 원격 저장소에 똑같은 파일이 있는데 그 로컬 저장소에서 아직 merge가 안 된 상태라서 오류가 발생한 것이다. 같은 파일이 2개가 있는 상황이라 오류가 난 듯 하다. git status를 쳐보면 아래와 같은 메세지가 출력된다. 위에서 언급했던 대로 아직 머지되지 않은 파일이 있는 상황이다. 따라서 git ..

> 수학 > 구현 > 정렬 시간 초과가 나서 input() -> readline()으로 바꿈. 1. 산술평균 처음에는 아래와 같이 작성했다. 그러나 바로 직전에 풀었던 문제가 떠올랐다.. 부동 소수점 문제가... 여기서도 어쩔 수 없이 소수가 나오기 마련이다. 그리고 round 함수는 우리가 알고 있는 반올림과는 큰 차이가 있다. 예시를 들어보자. 1.5를 반올림하면 -> 2 2.5를 반올림하면 -> 3 위 같은 결과가 나와야한다. 하지만 round 함수를 쓰면 1.5는 -> 2 2.5도 -> 2 위 같은 결과가 나온다. 띠용(?!) 우리가 알고 있는 방식은 "사사오입 방식"이라고 한다. 즉 0.5, 0.6처럼 절반 이상일 땐 반올림을 진행하고 그 이외엔 버리게 되는 형식이다. 그러나 round 함수는 ..

> 이분탐색 > 수학 1. 수학적인 공식을 이용하여 푼 방법 * 틀린 코드 * 아래 코드와 같이 했는데, 90% 가까이 성공하다 틀렸습니다 파티가 일어났다.. 왜지? 왜 안되는거지?라는 의문을 가지고 질문 게시판을 뒤적인 결과 부동소수점 오차 문제 때문이란다.. f,e=0,int(input())**.5 if e-int(e)==0: print(e) else: print(int(e)+1) 일단 컴퓨터가 실수를 표현하는 방식에 대해 알아야한다. 컴퓨터는 모든 수를 2진수(0과 1)로 표현한다. 정수는 표현이 간단하지만, 실수는 그리 간단하지 않다. 실수 표현 방식에는 두 가지 방식이 존재한다. 1. 고정 소수점 방식 2. 부동 소수점 방식 (1) 고정 소수점 방식 실수를 정수부와 소수부로 나눈다. 소수부의 자..

> 수학 1) 반복문을 이용하는 방법 수들의 합을 구하는 공식은 N * (N+1) / 2 = S 문제에서 주어진 값은 수들의 합 N의 값을 구해야한다. 처음에는 While문을 이용했다. 1부터 시작해서 수들의 합이 S를 넘기 직전까지 돌리고 해당 값을 출력해준다. 실행시간 88ms s = int(input()) answer = 0 i = 1 while i * (i + 1) //2 이렇게 해주면 된다. 물론 Math 라이브러리의 sqrt를 이용해도 구할 순 있음. 세제곱근을 구하려면 8**(1/3) 이런식으로 작성하면 됨.

1. 이미 push한 commit 취소하기 (1) 강제 푸쉬를 통해 해결 (*주의: 개인 브랜치에서만 사용할 것*) 1번 과정 : 최신 커밋을 취소하여 내가 원하는 곳까지 취소하기 git reset 명령어 > 진행된 커밋 이전의 커밋으로 HEAD가 이동함. # 1. mixed # 작업 디렉토리 유지, 인덱스만 HEAD와 함께 되돌림. git reset --mixed # == git reset # 2. hard # 작업 디렉토리 ,인덱스 모두 되돌림. # 따라서 작업하던 내용 모두 정리할 때만 사용 ** git reset --hard # 3. soft # 작입 디렉토리, 인덱스 모두 유지, # 커밋만 취소할 경우 사용 git reset --soft https://mylko72.gitbooks.io/git/..

해당 오류는 git pull 을 먼저 진행해서 원격 저장소와 로컬 저장소의 버전을 맞춰준 뒤 다시 git push를 진행하면 해결되는 문제! 나는 위 방법으로 해결했지만, 만약 안 먹힌다면 원격 저장소를 다시 추가한 후 시도하라고 한다. git remote add 저장소_주소

1. 아래 링크 접속 https://start.spring.io 2. 세부 설정 Project -> gradle Language -> java Spring Boot -> 2.6.4 Project Metada Group -> 프로젝트명 Artifact -> core? or another name Packaging > Jar Java > 11 GENERATE 버튼 클릭! 3. 인텔리제이로 프로젝트 띄우기! Artifact 에 적었던 이름을 기준으로 zip 폴더가 다운로드 폴더에 생성된다. zip 압축을 풀고, 해당 폴더에 들어간 뒤, Build.Gradle를 클릭하여 인텔리제이로 열어준다 (프로젝트로) > 이렇게 해야 하는 이유! 프로젝트명.core > CoreApplication이 생성되어야 파란 재생버튼..

1. 로컬 브랜치 조회 git branch 2. 원격 브랜치 조회 git branch -r 3. 모든 브랜치 조회 (로컬 + 원격) git branch -a 4. 원격 브랜치 참조 업데이트 git remote prune origin 5. 로컬 브랜치 참조 업데이트 git fetch -p

> dfs > bfs 실행시간 약 112ms 해당 좌표의 위치가 집인지 그리고 해당 좌표에 방문했었는지 안했는지에 대한 조건이 중요했던 문제 from collections import deque n = int(input()) array = [[] for _ in range(n)] for i in range(n): for j in list(input()): array[i].append(int(j)) # 상,우,하,좌 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] answer = [[0 for _ in range(n)] for _ in range(n)] cnt = 1 def bfs(i, j): queue = deque() queue.append((i, j)) global cnt if a..

> BFS 처음에 떠올렸던 생각은 다이나믹 프로그래밍 근데 지나야하는 최소의 칸 수를 구해야하므로 BFS로 풀었음. 문제에서 주어진 예제 2번의 과정을 풀어보았음. 그림이 좀 지저분하긴 한데.. 일단 노란색 형광펜으로 쳐져있는 길로 가야 최소의 이동칸 수를 구할 수 있다. 오른쪽에 써있는 작대기 + 숫자는 -> 이동순서 여기서 현재 위치란 nx,ny (x,y에서 이동한 값) 1. 만약 길이라면? 1.1 방문한 적이 없는 경우라면? 1.1.1 큐에 현재 위치 append 1.1.2 현재 위치 방문처리 1.1.3 answer 리스트의 현재 위치 부분에 +=1 해주기 1.2 방문한 적이 있는 경우라면? --> *** 이 부분이 중요 *** 1.2.1 answer[nx][ny]의 값과 answer[x][y]+1..

> 자료구조 > 스택 > 재귀 https://www.acmicpc.net/problem/1662 이 문제를 풀 때 스택을 생각해내지 못하고 빡구현으로 하려고 시도했으나 처참하게 실패했다. 문자열 스택!! 문자열 문제에서 스택이 자주 쓰였던 것 같은데 왜 항상 까먹는지 이번 기회에 기억해두길.. 이 문제를 풀 때 길이가 아니라 문자열 자체를 저장해두다보니 메모리초과가 발생했다. words = input() answer = '' temp = '' stack = [] for idx in range(len(words)): if words[idx] != ')': stack.append(words[idx]) else: while True: x = stack.pop() if x != '(': # 숫자 temp+=x ..

> Dp 처음에 떠올렸던 알고리즘은 dfs였다. 그런데 dp로 풀게 되면,, 조건을 처리해주는 부분이 매우 까다로울 것 같아서 힌트를 봣더니 역시나 틀린 방법을 .. ㅎ 이 문제는 다이나믹 프로그래밍 기법을 이용하여 풀어야한다. D분 후 위치해있어야하는 곳은 정보과학관이다. 초기값은 정보과학관 전산관 미래관 신양관 한경직기념관 진리관 형남공학관 학생회관 초기값 (0분) 1 0 0 0 0 0 0 0 1분 후 정보과학관에서 전산관으로 가는 방법은 1가지 정보과학관에서 미래관으로 가는 방법은 1가지 정보과학관 전산관 미래관 신양관 한경직기념관 진리관 형남공학관 학생회관 초기값 (0분) 1 0 0 0 0 0 0 0 1분 후 0 1 1 0 0 0 0 0 2분 후 정보과학관 전산관 미래관 신양관 한경직기념관 진리관..

> 정렬 처음에 이 문제를 보고 묶음이 여러개 있어도 된다는건가?라는 생각과 함께 묶음이 짝수인 경우 묶음 안에 있는 호반우를 품질을 기준으로 정렬했을 때 (묶음개수/2+1)번쨰 호반우를 중앙값으로 정의해야한다는 글을 보고 묶음 개수가 배열에서 내가 정한 묶음의 개수를 의미하는건가..라는 생각과 함께 한참 헤매고 있었다. 그런데 묶음의 개수가 이 의미가 아니었다. 만약 배열이 [2,4,8,9]라고 가정하자. 그러면, 지금 내가 2랑 9를 묶으면 이 묶음의 총 길이는 2이다. 짝수이므로 중앙값은 2/2+1 = 2가 되니까 배열의 2번째 값인 9가 중앙값이 되는 것이다. 만약 내가 [2,4,9]라고 묶었다고 가정하면 총 길이는 3이다. 홀수이므로 중앙값은 3+1/2=2이고 우리는 최대 이익을 만들어야하기 때..

> DFS set()을 이용해 중복을 잡아냈다. 실행시간은 약 94ms array=[list(map(int,input().split())) for _ in range(5)] result=set() # 상,우,좌,하 dx=[-1,0,0,1] dy=[0,1,-1,0] def dfs(i,j,answer): if len(answer)==6: result.add(answer) return answer+=str(array[i][j]) for k in range(4): nx=i+dx[k] ny=j+dy[k] if 0