For Programmer

SSAFY 7기 1년이 끝이 났다. 내가 싸피를 어떻게 들어갔고 왜 들어갈려고 했는지 인생을 한번 적어볼까 한다. 어렸을 때부터 컴퓨터를 잘하고 싶다는 생각을 했었다. 게임을 하면 항상 불법프로그램을 사용하는 상대에게 지는게 분했다. 항상 생각했다. 내가 이러한 프로그램을 만들면 어떨까? 내가 만들어서 모든 상대를 이길 수 있다면 나는 컴퓨터 게임을 매일 재밌게 할 수 있지 않을까? 하지만 어린 나에게 복잡한 영어와 컴퓨터 언어는 도저히 접근할 수 있는 분야가 아니었다. 그렇게 막연한 꿈만 가진채 아무런 목표없이 학교 공부를 하게 되었고 재수 끝에 이공계열이 아닌 건국대 경영대학에 진학을 한다. 그렇게 경영학과를 진학하게 되었지만 영어를 상당히 못했다. 특히 듣기 말하기를 아주 못했는데 토익 토스 점수가..

https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 문제에서 요구한 대로 해시와 정렬만 잘하면 쉽게 풀 수 있는 문제이다. 설명은 주석으로 달아놨다. function solution(genres, plays) { const gernes_hash = {} //장르별 최대 플레이 횟수를 저장할 해시 const gernes_cnt = {} // 장르별 각각의 플레이 횟수를 리스트로 저장할 해시 for (let i =..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 간단히 0의 위치를 저장후 3개를 뽑는다 그 3개를 1로 바꾸고 바꾼상태에서 bfs를돌려 바이러스를 잠식하게 한다. 그 후 0의 개수를 세어 가장큰값을 찾으면 된다. from collections import deque N, M = map(int, input().split()) map_ = [list(map(int, input().split())) for _ in range(N)] brr = [] zero =..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net N = int(input()) arr = list(map(int, input().split())) ans = [-1] * N # 초기 정답을 -1로 설정 stack = [0] # 첫 인덱스 0을 넣어준다. for i in range(1, N): # 만약 스택의 마지막 인덱스의 arr값이 해당 비교하고자 하는 값보다 작다면 # 그 값보다 클때까지 해당 값을 오른쪽의 큰 수로 설정해준다. while stack ..

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 상당히 어려운 문제이다.. 아무리 풀어도 시간초과가 나길래 풀이힌트를 보았다. 해결방법은 다음과 같다. 어차피 대각선끼리만 영향을 주니 dfs를 돌 때 반씩 나눠서 돌자는 것이다. 즉, 최대 O(2^100) 인 시간복잡도를 O(2^25) * 2 로 줄일 수 있다는 것이다.(6700만 정도) 단, 한부분만 신경을 잘써야하는데 바로 N이 짝수일때와 홀수일때 열과 행의 계산이 달라진다는 점이다. 자세한 코드는 ..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 해당 문제 처음에 연결요소 개수 찾는 문제인지 알고 풀었으나 당연히 아니였다... 그래서 생각을 조금 더 해보니 다음과 같은 구조를 발견할 수 있었다. 1. 이미 방문처리된 그룹과 연결된다면(이미 설치했으므로) 굳이 safe-zone을 설치할 필요가 없다. 2. 아직 방문처리 되지않은 그룹과 연결되었는데 더이상 갈곳이 없다면 그때 개수를 1개 증가시켜준다. 3...

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 해당 문제 굉장히 어려웠다... (알고나면 쉬운데 모르면 어려운 문제) 문제 해결은 단순하다. 1. 붙어 있는 0끼리 딕셔너리로 그룹을 매긴다. 그리고 각 그룹마다 0의 개수를 저장해놓는다. 2. 그 후 1의 위치만 찾아서 위 아래 좌 우 4방향으로 한번만 이동하면서 각각의 그룹에 저장되어있는 0의 개수만 더해주면 된다. from collections import deque ..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net O(n^2) 에 해결할 수 있기 때문에 잘생각해보면 리스트 전체의 각 지점을 반복문을 돌면서 한점을 기준으로 잡고 바로 오른쪽을 시작점 마지막 인덱스를 끝지점으로 투포인터를 돌리면 되는 간단한 문제이다. 세개의 점을 찾아야하기 때문에 투포인터의 응용버전이라 조금 생소할 수도 있지만 이기회에 잘 익히자. (참고로 N^2 임에도 불구하고 아주큰수의 + 연산때문에 파이썬3에서는 시..