본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

전체 글580

[동적계획법, 난이도 중하] 백준 1003번 피보나치 함수 피보나치 함수 fibonacci(n) 의 리턴값은 fibonacci(n-1)+fibonacci(n-2) 이다. fibonacci(0)은 0을 출력하므로 0이 1회 출현한다고 보고 fibonacci(1)은 1을 출력하므로 1이 1회 출현한다고 본다. 그렇다면 fibonacci(2)는 fibonacci(1)과 fibonacci(0)을 리턴하기 때문에 0,1이 1회씩 출현한다고 할 수 있다. fibonacci(3)까지 해보자. fibonacci(3)은 fibonacci(2)와 fibonacci(1)을 리턴하기 때문에 0은 1회, 1은 2회 출현한다고 할 수 있다. 자세히 나타내면 이렇다. fibonacci(2) -> 0 1회, 1 1회 fibonacci(1) -> 0 0회, 1 1회 fibonacch(3) 총.. 2020. 8. 15.
[동적계획법, 난이도 중하] 백준 9095번 1,2,3 더하기 1,2,3 이 3개의 정수의 덧셈으로 n을 표현해야 하기 때문에 1,2,3 을 표현하는 방법은 미리 구해놓자. 1 -> (1) 1가지 2 -> (1+1),(2) 2가지 3 -> (1+1+1), (2+1), (1+2) , (3) 4가지 n=4일때부터 순차적으로 DP를 진행해야 하는데 동적계획법은 이전에 계산 했던 값들을 가지고 현재 정보를 계산하는 알고리즘이다. 이전 값은 이렇게 응용하면 된다. 3을 1,2,3의 합으로 표현하는 방법은 -> (1+1+1), (2+1), (1+2) , (3) 총 4가지 인데 이 4가지 그룹에서 각각 1을 더해주면 4가 나오지 않을까? 그리고 2를 1,2,3의 합으로 표현하는 방법은 -> (1+1),(2) 총 2가지 인데 이 2가지 그룹에서 각각 2을 더해주면 4가 나오지 않.. 2020. 8. 15.
[SCC, 난이도 중상] 백준 9466번 텀 프로젝트 원래 알고리즘 분류상 DFS에 들어가 있던 문제인데, 강한 결합요소(SCC) 유형이라고 보는게 더 좋을 것 같아서 그래프 카테고리에 포스팅 한다. 강한 결합요소 알고리즘도 DFS를 쓴다. 강한 결합요소 알고리즘을 간단하게 설명하자면 이렇다. 일단 아래 그림은 9466번 예제에서 첫 번째 케이스를 도식화 한것이다. 3번은 자기 자신을 가리킨다는 의미로 동그라미로 감쌌다. 여기서 SCC는 5개다. (1번), (2번), (3번), (4번,6번,7번) , (5번) 여기서 (4번,6번,7번)은 사이클로 되어있으므로 하나의 SCC그룹이라고 하는 것이다. 아래 소스 코드에서 dfs함수가 SCC(강한결합요소) 알고리즘이다. 그런데 여기서 한가지 처리를 해줘야 한다. 서로 선택 받고 있는 그룹은 (3번),(4번,6번,7.. 2020. 8. 15.
[DFS, 난이도 중하] 백준 11403번 경로 찾기 표를 직접 이용하는 방법 보다는 그래프로 도식화해서 해결하는 것이 더 편한 방법 같다. 고로 도식화를 하여 DFS로 해결 하였다. 아래 그림은 예제 입력2 의 인접행렬을 그래프로 도식화 한 것이다. 경로벡터 a에 간선 정보들을 모은 후 각 노드마다 dfs를 수행해주면 된다. dfs의 매개변수는 s, x로 설정했는데 s는 첫 출발 노드고, x는 현재 노드이다. 접근 할 수 있는 노드들을 모두 방문하며 ans[첫출발 노드][현재 노드]를 1로 갱신 해나가는 전략이다. 이 문제가 정답률이 52%로 높은 편인 이유는 예제를 2개나 주었고, 시간 및 노드 제한이 널널해서 인 것같다. 이 소스코드에서 노드별로 dfs를 수행할 때 자신보다 낮은 노드 번호를 가지는 노드의 접근 가능 노드 목록은 이미 계산이 되어 있는.. 2020. 8. 14.
[그리디, 난이도 중] 백준 1931번 회의실배정 첫 그리디 문제풀이 포스팅이다. 다이나믹(동적계획법) 알고리즘과 그리디(탐욕) 알고리즘의 차이는 이 포스팅에서 다루었다. https://kimcoder.tistory.com/32 [동적계획법, 난이도 중] 백준 1463번 1로 만들기 첫 번째 동적계획법 문제풀이 포스팅이니, 동적계획법이 뭐하는 알고리즘인지 설명이 필요할 것이다. 동적계획법은 간단하게 말하면 바로 해답을 구하는 것이 아니고, 이전에 계산했던 값을 활 kimcoder.tistory.com 여러 회의들의 시작 시간, 끝 시간을 알아내어 최대한 많은 회의를 하는 경우를 계산해야 하는 문제이다. 회의가 끝나는 시각이 이른 순으로 정렬하고, 끝나는 시각이 같다면 시작 시각이 늦은 순으로 추가 정렬을 해준다. 이 문제의 정답률이 28%인 이유는 아마.. 2020. 8. 14.
[BFS, 난이도 중상] 백준 2146번 다리 만들기 본인은 두 Step으로 나눠서 문제를 해결하였다. 큐는 각각 q,q2 이라는 이름의 큐 총 2개를 사용하였다. Step1에서는 q를 이용해 아래 그림과 같이 나라별로 숫자로 분류하였다. Step2에서 BFS를 수행하면서 어떤 나라를 만났을 때, 그게 자신의 나라인지 남의 나라인지 구별하는 과정을 거칠 것이기 때문이다. 이 과정 때문에 개인적으로 이 문제의 난이도는 중상으로 평가한다. Step2에서는 q2로 모든 지도를 탐색하여 방문하지 않은 바다 좌표를 만날 때마다 큐에 넣고, 방문 처리를 한다. 만약 탐색한 나라가 출발한 나라와 다를 경우, 구조체 node 에서 다리의 길이를 의미하는 depth 를 found 변수에 넣고 최솟값을 업데이트 해나갔다. g -> 나라 번호 depth -> 다리 깊이 x,y.. 2020. 8. 13.
[동적계획법, 난이도 중] 백준 1463번 1로 만들기 첫 번째 동적계획법 문제풀이 포스팅이니, 동적계획법이 뭐하는 알고리즘인지 설명이 필요할 것이다. 동적계획법은 간단하게 말하면 바로 해답을 구하는 것이 아니고, 이전에 계산했던 값을 활용하는 알고리즘이다. 해답을 바로 구하는것은 그리디(탐욕) 알고리즘이다. 동적 계획법은 대부분 점화식을 요한다. 그런데 해답을 바로 구하는 것이 아니라는 말이 무슨말인가 이해가 안될 수 있다. 이번 문제가 이를 설명할 좋은 예가 될것이다. 예제 입력2 에서 입력값으로 10을 줬을 때 3이 출력되는데 아래 사진이 접근 과정이다. s배열=save배열 식을 보면 인덱스 0부터 순차적으로 계산해나가며 이전에 계산했던 값을 활용하고 있다. 다르게 말하면 입력값 10까지의 경우를 모두 계산했다는 말도 된다. 이러한 방식으로 접근하는 알.. 2020. 8. 13.
[DFS, 난이도 중상] 백준 1987번 알파벳 DFS 첫 문제부터 조금 욕심을 내서 정답율 30%인 문제를 골랐다. 한 번만에 성공해서 되게 좋았다. DFS는 주로 스택이나 재귀 함수를 이용하는데, 개인적으로 재귀 함수가 훨씬 편한 것 같다. 제일 먼저 node라는 이름을 가진 구조체를 선언하였다. BFS 문제들을 풀면서, 탐색 문제에는 구조체를 활용하는것이 효과적이라는 사실을 깨달아서 바로 활용해 본 것이다. 구조체 안의 변수는 깊이,좌표 정보들로 구성시켰다. 시작점은 1행 1열이므로 좌표는 (0,0), 깊이는 1인 구조체 node를 맨 처음dfs 매개변수에 넣으며 시작했다. 상하좌우를 탐색하며 현재까지 처음 마주보는 알파벳만 그 좌표를 방문처리 하고 재귀함수를 호출했다. 그리고 재귀함수에서 나왔을 때 방문처리는 취소했다. dfs문 중간에서 -65.. 2020. 8. 12.
전 세계 CSS 인기 속성 통계 약 121만개의 웹 사이트에 대한 통계 자료이다. 지금은 사이트에 들어가도 이 그래프를 볼 수 없지만 이미지 자료는 남아있다. 글자 크기, 색, 공백, 여백, 선 같이 웹 design에 빼놓을 수 없는 속성들이 상위 랭크를 차지하였다. 테두리가 아닌 단일선도 주로 border을 이용하는 듯 하다 2020. 8. 11.

티스토리툴바