본문 바로가기

전체 글

 (23)
2021 NYPC 개최가 2일 남았습니다! 안녕하세요 코딩 새싹 페놀입니다. NYPC를 참여하게 되었는데, 본선 갈 확률은 0.000001%를 향하고있고 예선 특별상을 노리려고합니다. 오늘 연습문제가 공개되었고 연습문제는 만점을 맞았는데, 예선은 어떻게 될지 모르겠네요(전 대회 점수를 뛰어넘는게 목표입니다) 대회 모두 끝나면 풀이를 공유하겠습니다.
[PS일지]백준 11657번 타임머신, 벨만-포드 알고리즘 전에 배웠던 다익스트라는 치명적인 결점이 있었다... 바로 음수간선에는 제대로 된 최솟값을 찾지못한다는 것이다! 그리고 무엇보다 음의 사이클(음수가 포함된 회로)를 찾지 못한다. 음의 사이클이 존재하는 그래프에서는 어떤 알고리즘도 정확하게 최솟값을 찾기가 불가능하다 예를 들어 보자 1번에서 2번으로 가는 것의 가중치가 1이고 2번에서 3번으로 가는 것의 가중치가 -10이고 3번에서 1번으로 가는 것의 가중치가 1이라 하자 이의 최단경로는 구할 수 없다. 음의 무한대이기 때문이다. 1번-2번-3번-1번-2번-3번- .... 순으로 가면 음의 무한대가 된다... 이러한 문제들을 해결하는 아주 좋은 도구인 벨만-포드 알고리즘을 배울 것이다. 벨만-포드 알고리즘의 원리는 생각보다 간단하다. W(u, v)를 u-..
[PS일지]백준 1753번 최단경로, 다익스트라기초 DFS, BFS를 배운 뒤 최단경로관련 알고리즘을 배우기 시작하게 되었다. 다익스트라, 벨만-포드, 플로이드-와셜 등 가중치가 없었을 때는 BFS의 아주 좋은 성질로 쉽게 풀 수 있었지만, 가중치(돈, 거리, 시간 등등)가 있는 그래프에서는 BFS를 적용하기 힘들다. 가중치가 있는 곳에서 최단경로를 찾기위해 BFS와 비슷한 방식을 사용하는 알고리즘이 있는데, 그것이 다익스트라 알고리즘이다. 기초적인 연습문제를 풀기 전에 다익스트라 알고리즘에 대해 배워보자 다익스트라 알고리즘은 네덜란드의 전산학자 에츠허르 데이크스트라가 고안한 알고리즘이다 이분은 튜링상까지 받은 매우 유명한 분이다.(수학에서 필즈상으로 보면 된다.) BFS에서 인접한 정점을 모두 방문하듯이 다익스트라 알고리즘은 우선순위큐(priority ..
1달 코딩 공부 후기 본격적으로 코딩 공부를 한지 1달이 지났다. 이전에 비하면 많은 실력 상승이 있었고 문제를 풀면서 있는 시행착오를 겪으며 성장한 것 같다. 이대로 열정을 잃지않고 1년을 간다면 더욱 성장할 수 있다고 예상해본다. 우물 안에 갇혀있었던 내가 교만하지않고 밖으로 한걸음 내딛은 계기가 된 것 같다. 어떤 넓은 공부세상이 있을지 기대되기도 하고 긴장되기도 한다.
[PS일지]위상정렬(백준 2252기초, 줄세우기) 오늘 종만북에서 DFS와, 위상정렬, DFS 스패닝 트리 등등... 을 배웠다. 이 시간에 블로그를 쓰다니... 다른 굇수분들의 비해서는 많이 초라하지만 골드 2 기초 위상정렬 문제인 단계별로 풀어보기에 있는 백준 2252번 풀이를 올릴까한다. 어쨌든 나는 닉값하는 코딩 새싹이라 많이 못한다. 잡다한 이야기는 각설하고 일단 문제 분석 들어가자 우리가 구해야할 것은 학생이 줄을 서는 순서이다. 무언가 거창한 알고리즘을 써야할 것 같지만 굳이 그런 것은 아니다. 위상정렬이라는 것을 쓰면 된다. 위상정렬이란 순서를 만드는 거라고 보면 된다. 당신이 프린터기로 사진을 인쇄한다고 생각해보자 1. 잉크를 체운다. 2. 종이를 체운다. 3. 콘센트를 꼿는다. 4. 인쇄버튼을 누른다. 대충 이런 순서로 배열되어있다고 ..
제 블로그를 소개합니다 보통 고인물분들을 보면 PS 블로그를 많이 쓰시더라고요 저도 한번 ㅋㅋ... 만들어봤습니다 바보입니다 많이 부족할 수 있어요 제가 학습할 겸 블로그를 만들어보았습니다. 잘 부탁드립니다! NYPC나 백준 같은 잡다한 후기를 남길예정입니다. 생초보예요 귀여워해주세요(?) 사실 갓직히 현재 골드 4밖에 안되서 별로 안올릴 듯 하네요 아마 플레될때까지 썩혀놀거같습니다 ㅋㅋㅋ
[PS일지]큐, 스택, 덱 "코딩 초보 페놀"의 PS일지 종만북 2권에서 큐와 스택 덱을 배웠다. 셋 다 간단한 자료구조지만 그만큼 쓸모가 많다고 생각이 들었다. 스택은 후입선출로, 나중에 들어간게 먼저 나오는 자료구조이다. 간단하게 생각해보자 1부터 5까지의 숫자공을 바닥이 열리지 않는 상자에 넣어보자 바닥-1-2-3-4-5 뺄때는 5부터 빼내야한다 이것이 바로 스택의 후입선출이다 빼는 연산을 POP이라한다. 상자에 공을 넣는 연산을 PUSH라한다. 사실, C에는 없지만 (C++만세) C++에는 stack 헤더파일을 제공한다. 자세한 내용은 STL stack으로 구글링하면 많은 설명이 있다. 그럼 대체 이 stack을 어디에 이용하는가? 바로 괄호이다. "("은 ")"와 짝을 맺어야한다. (((((((((() 이라는 괄호식이 있..

티스토리툴바