본문 바로가기

반응형

IT/Algorithm Test

(5)
[C] 백준(BOJ) - 1193 분수찾기 이번 포스트는 처음으로 Python이 아닌 C로 풀어보는 문제이다. 원래 필자는 임베디드 개발로 개발을 시작했기 때문에 C가 주언어였고, 처음 백준을 접했을 때에는 C로 문제를 풀었다. 하지만 취업을 위한 코딩 테스트 준비에서 C의 비효율성(시간복잡도나 CS적 측면이 아닌 문제 풀이를 위한 비생산성)의 문제로 Python으로 갈아타게 되었다. 그래서 이번에는 어떤 문제를 풀까, 하다가, 옛날에 C로 풀었던 규칙성 문제를 찾게 되어 C 코드를 올릴까 한다. 한 번 바로 살펴보도록 하자. 소스 코드 //BOJ 1193 분수찾기 #include int main() { int i = 1, j = 2, k = 1, tmp = 0, cnt = 1, n = 0, m = 0; scanf("%d", &i); while ..
[Python] 백준(BOJ) - 1260 DFS와 BFS (인접 리스트) 이번에는 지난 번에도 풀었던 백준 1260번의 DFS와 BFS다. 지난 번에 파이썬의 딕셔너리 자료형으로 풀어서 332ms의 실행 시간이 나왔는데, 이번에는 전통적인 C/C++ 스타일로 인접 리스트를 만들어서 풀어보았다. 과연 결과는? 소스 코드 #BOJ 1260 DFS와 BFS - Adjecent Index from collections import deque import sys input = sys.stdin.readline def dfs(_graph, _start): visit = list() s = list() s.append(_start) while s: node = s.pop() if node not in visit: visit.append(node) if _graph[node] == None..
[Python] 백준(BOJ) - 1260 DFS와 BFS (Dictionary) 이번 문제는 DFS와 BFS 기초이다. 그러나 정답률은 30.604%로 꽤나 저조한데... 그 자세한 이유는 실제로 풀어보면 알겠지만 생각보다 난해한 부분이 생긴다. 그러나 기초는 기초일 뿐. Python3로 풀면 특히 쉽다. 보통은 Node로 그래프를 그려서 풀겠지만, 이번에는 Python의 Dictionary 자료형을 활용하여 해결해보았다. 한 번 바로 살펴보도록 하자. 소스 코드 #BOJ 1260 DFS와 BFS from collections import deque import sys input = sys.stdin.readline def dfs(_graph, _start): visit = list() s = list() s.append(_start) while s: node = s.pop() if..
[Python] 백준(BOJ) - 1931 회의실배정 필자는 거의 항상 코딩 테스트, 혹은 알고리즘 문제 풀이를 파이썬으로 한다. 대체로 코딩 테스트는 C++로 하라고 하지만... 필자가 일하고자 하는 직무가 인공지능, 빅데이터 쪽이기도 하고, C, C++은 임베디드 하면서도 자주 접하기 때문에 지식의 반경을 넓히고자 하는 욕심도 있기 때문이다. 이번 알고리즘 풀이 첫 문제는, 백준 온라인 저지의 1931번 문제 회의실 배정이다. 이 문제는 그리디 알고리즘의 대표격 문제이지만, 정답률은 28% 정도로 조금 낮은 편이다. 그 이유는 바로 끝나는 시간과 시작하는 시간이 겹칠 수 있다는 특수성 때문에 그럴 것이다. 지난 5567번 문제에서도 그랬지만 이 포스트에서 그리디 알고리즘에 대한 이론 설명은 하지 않겠다. 이는 따로 "이론 카테고리"에서 정리할 예정이다...
[Python] 백준(BOJ) - 5567 결혼식 필자는 거의 항상 코딩 테스트, 혹은 알고리즘 문제 풀이를 파이썬으로 한다. 대체로 코딩 테스트는 C++로 하라고 하지만... 필자가 일하고자 하는 직무가 인공지능, 빅데이터 쪽이기도 하고, C, C++은 임베디드 하면서도 자주 접하기 때문에 지식의 반경을 넓히고자 하는 욕심도 있기 때문이다. 이번 알고리즘 풀이 첫 문제는, 백준 온라인 저지의 5567번 문제 결혼식이다. 정답률도 41% 정도의 쉬운 문제지만, 이 문제를 처음으로 올리는 이유는, 필자가 처음으로(부끄럽다...) 랭크에 올라봤기 때문이다. 한 번 바로 살펴보자. 소스 코드 #BOJ 5567 결혼식 (Graph) import sys input = sys.stdin.readline n = int(input()) m = int(input()) ..

반응형